Algorithm Animations (JavaScript/video)

NOTE: This collection of links/resources/animations is no longer maintained.
              They were used in the earlier/former course "IMT2021 - Algorithmic Methods" (last time lectured: fall 2019).
              For the animations used in the new course (IDATG2102), see the column "Animasjon" here.


The chapters below refers to the book "Algorithms in C++" by Robert Sedgewick:

[ Ch.3 | Ch.4 | Ch.5 | Ch.8-12 | Ch.14 | Ch.15 | Ch.16 | Ch.22 | Ch.29 | Ch.30 | Ch.31 | Ch.32 | Ch.33


Collections (with several parts of the curriculum):

  1. Algorithm Animations and Visualizations
  2. Data Structure Visualizations
  3. Visualgo - visualising data structures and algorithms through animation
  4. Algorithms and Data Structures Animations
  5. Competitive Programming


 

Chapter 3 - Elementary Data Structures:

    Link:   Comments:
  1   Stack (Array Implementaion)  
  2   Stack (Linked List Implementaion) - LIFO  
  3   Queue (Array Implementaion)  
  4   Queue (Linked List Implementaion) - FIFO  
  5   Visualgo: Linked List, Stack, Queue (++)   (+ Doubly Linked List, Deque)
  6   Visualization of singly linked list (LIFO, FIFO, Sorted)   Make/play with different linked lists (LIFO, FIFO, Sorted)
  7   Postfix (Reverse Polish Notation) Calculator   Reads and calculates a postfix expression.
  Type/write a postfix expression step by step.
  8   Postfix Expression Evaluation   See "Algorithm Visualization" just below the middle of the page
  9   Converting Infix to Postfix   See lower white animation in the middle of the page
  10   Infix ↔ Postfix Converter   Converts both ways
  11   Infix → Postfix Converter  

 

Chapter 4 - Trees:

    Link:   Comments:
  1   Expression calculator and Parse Tree   Use an INFIX expression
  2   Binary Tree Visualiser: Binary Search Tree   Use "Random BSTree". Use then "To ...order Array".
  3   Binary Tree Traversals   Use buttons inside the figures down the page
  4   Tree traversal: Preorder - Inorder - Postorder - Level order (Breadth first)   Difference between the different travels. Use "Single Step"-mode.

 

Chapter 5 - Recursion:

  1   The Fibonacci Numbers and the Golden section  
  2   Recursive Factorial   Use 'Pause' and 'Step Forward", or low speed
  3   Recursion Tree: Fibonacci Numbers   Choose 'Fibonacci Numbers in lower left corner. Press 'Run'. Use || (Pause) and |> (Next Step).
     
  4   Towers of Hanoi   Select eg. 5 Discs, 3 Pegs and 3D(!)
  5   Hanoi  
  6   Towers Hanoi   Use 'Single Step' and 'Continue', or 'Continous'
     
  7   Eight Queens  
  8   The 8 Queens Problem   Choose 'Simulation' and 'Slow'/'Moderate'
  9   Recursive N-Queens  
     
  10   Backtracking - Maze   Scroll down to 'Maze Solving', press 'Run'
  11   Backtracking through a maze   Explains/shows solving of and backtracking in a maze. Press 'drive me!'.
  More explanation here.
     
  12   Sudoku   Fill in your own numbers. Press 'Start', and then 'Next' several times.

 

Chapter 8, 9, 11 and 12 - Sorting:

    Link:   Comments:
  1   Sorting.at   Selection, Insertion, Bubble, Shell, Quick, Heap, Merge, +++
  Add sorting method: Click '+'-sign, choose algorithm (size 20) and "Visualize algorithm" ('+'-sign).
  Remove: click 'X'-sign (upper right corner of each sorting animation)
  2   Comparison Sorting Algorithms   Selection, Insertion, Bubble, Shell, Quick, Merge
  NOTE: Shell uses H as 1, 3, 6, 12, 25. Quick uses the left one as pivot.
  3   Algostructure   Selection, Insertion, Bubble, Shell, Quick, Heap(BottomUp), Merge, +++
  NOTE: Shell uses H as 1, 4, 10, 23.
  4   Sorting Demonstrations   Insertion, Bubble, Shell, Quick, Heap, Merge, ++
  NOTE: Shell uses H as 1, 3, 7. Quick works a little bit different from the textbook.
  5   Sorting Algorithms   Selection, Insertion, Bubble, Quick, Heap(BottomUp), Merge
  6   xSortLab   Selection, Insertion, Bubble, Quick, Merge
  NOTE: Selection sorts backwards. Quick uses leftmost element as pivot. Merge different from textbook.
  7   Sorting Out Sorting (ver 2.0 - Demo)   (Linear) Insertion, Bubble, Shell, Quick, Heap
  Choose method(s) at upper left, click "Add" and "Run Playlist".
  NOTE: Quick uses the left one as pivot.
  8   Sorting Algorithms Animations   Compare all sorting algorithms (horizontal). Sort with different input (vertical).
  9   Animated GIFs of Sorting Algorithms   Selection, Insertion, Bubble, Shell, Quick, Heap, Merge
  10   Counting Sort / Distribution Counting  
  11   Binary Heap + Priority Queue  
  12   Algorithm, Heap sort priority queue   NOTE: Heap(TopDown) "sorted" after min value.
  13   Min Heap   Choose "BuildHeap". NOTE: Heap "sorted" after min value.
  14   YouTube: Algorithms - Playlist 1   Selection, Insertion, Bubble, Quick, Heap, Merge
  15   YouTube: Sorting Algorithms - Playlist 2   Selection, Insertion, Bubble, Shell, Quick, Heap, Merge
  16   YouTube: 15 Sorting Algorithms in 6 Minutes   Fun: "What different sorting algorithms sounds like" :-)
  17   Big-O Cheat Sheet: Know Thy Complexities!   Big-O for Sorting Methods

 

Chapter 14 - Elementary Searching Methods:

    Link:   Comments:
  1   Binary Search Animation   Sorted array
  2   Binary Search   Sorted array
  3   BinaryTreeVisualiser: Binary Search Tree  
  4   Algorithm, Binary tree insert delete display   "Delete" works different from the textbook.
  5   VisuAlgo: Binary Search Tree  
  6   Binary Search Tree Visualization  

 

Chapter 15 - Balanced Trees:

    Link:   Comments:
  1   An Animation of B-tree Algorithm   2-3-4 Tree   Choose mode/version: Manual, Automatic or 3D
  2   B-Tree Visualization   2-3-4 Tree (and more). Choose "Max.Degree = 4" and set check mark at "Preemtive Split/Merge".
  NOTE: Equal values are (unfortunately) inserted to the left - and not to the right - as everywhere in our textbook.
  3   B-Tree   2-3-4 Tree.   Choose "Init empty with this M: 2" or "Init simple" (upper right) and then "Insert".
  4   Red-Black Trees and 2-4 Trees   Both 234-Tree and RB-Tree
  5   ngredblacktree.appspot.com: RB-Tree   New value will be added (+). Existing ones will be removed (-).
  6   Red/Black Tree   NOTE: 'Delete' substitutes with nearest predecessor
  7   Red Black Tree Visualization   Use "Single Step"-mode

 

Chapter 16 - Hashing:

    Link:   Comments:
  1   Open Hashing   Separate Chaining
  2   Hash Tables   Separate Chaining. Use the "Collision Solution"-button to choose "Chaining".
  New is added at the end - not in the front (as in the textbook).
  3   Hashing Using Separate Chaining   Separate Chaining. New are added at the end - not in the front.
  4   Closed Hashing   Linear Probing. Select "Linear Probing".
  5   Hash Tables   Linear Probing.
  6   Closed Hashing   Double Hashing. Select "Double Hashing" (not "Quadratic Probing").
  7   Hashing Visualization   Linear Probing and Double Hashing.
  Choose Hashing Function ("Simple Mod Hash"), Collision Resolution Policy ("Linear Probing" or "Double Hashing (Prime)") and Size (16).

 

Chapter 22 - File Compression:

    Link:   Comments:
  1   Huffman Compression   Building the tree, finding code.
  2   Huffman Coding   Only building the tree
  3   Huffman-demo   GIF-file demo
  4   Huffman Tree Generator   Write your own text. Generate the Huffman-tree.
  5   Lossless Data Compression (Huffman / Lempel-Ziv)   Automatic animation of Huffman in the beginning of the page.
  Animation of Lempel-Ziv (LZ(W)) in the middle of the page.
  6   Download LZ.zip   LZW: Extract. See 'readme'-file. Command window: Go to relevant directory, run 'java LZ'.

 

Chapter 29 - Elementary Graph Algorithms:

    Link:   Comments:
  1   Wikipedia: Glossary of graph theory   Terminology
  2   Graph Theory Glossary   Terminology
  3   Visualgo: Adjacency Matrix/List   Click figure to add new nodes. Drag between nodes to create new edges.
  Observe the Adjacency Matrix and List at the bottom.
  4   Depth-First Search   Choose "New Graph" (until satisfied), "Undirected Graph" and "Large Graph".
  Fill in "Start Vertex". "Run DFS". Use "Step Forward". Switch also to "Adjacency ... Representations".
  5   Breadth-First Search   Choose "New Graph" (until satisfied), "Undirected Graph" and "Large Graph".
  Fill in "Start Vertex". "Run BFS". Use "Step Forward". Switch also to "Adjacency ... Representations".
  6   BFS/DFS Animations   Shows the difference between DFS and BFS

 

Chapter 30 - Connectivity:

    Link:   Comments:
  1   Disjoint Sets   Union-Find (with Path Compression and/or Weight Balancing (="Union By Rank - # of nodes"))
  NOTE: "Dad"-array at the lower left works a little bit different from the one in the lecture book.
  2   Union-Find Disjoint Sets   Menu in lower left corner: Use "Examples" or "Initialize" and then "UnionSet".
  Path Compression (but not Weight Balancing).
  3   Union-Find Visualization   Little bit funny to watch .....

 

Chapter 31 - Weighted Graphs:

    Link:   Comments:
      NOTE:The code at page 455 in the textbook is another
  implementation (it uses adjacency list and indirect heap) of Prim's (MST)
  and Dijkstra's (SP) algorithm at page 466 (that uses adjacency matrix and
  an unsorted/unordered array).
  (Kruskal's code at page 460 uses a different/another algorithm for MST.)
  1   Prim Minimum Cost Spanning Tree   MST: Choose "Large Graph", "Start Vertex", "Run Prim", "Pause" and use "Step Forward"
  NOTE: Three columns to the left works a little bit different from the code in the lecture book.
  2   Prim's Algorithm   MST: Choose "demo1-7" along left margin (e.g. demo3 or demo7). Click inside figure.
  3   Prim's Algorithm   MST: "Create a Graph" (drag the nodes to easier to see), "Run the Algorithm".
  4   Example Networks2: MST problem   MST: Oberserve, read (and use buttons)
  5   Algorithm, Prim minimum spanning tree   MST: Use 'Single Step"-mode
  6   Greedy Algorithm for MST   MST: Test yourself!
  7   Dijkstra Shortest Path   SP.   NOTE1: Accesses not necessarily last added/updated edge equal to others weight.
  NOTE2: Three columns to the left works a little bit different from the code in the lecture book.
  8   Dijkstra's Algorithm   SP: Choose "demo1-8" along left margin (e.g. demo4, demo5 or demo8). Click inside figure.
  9   Dijkstra's Algorithm   SP
  10   Graph Algorithms   Choose Prim (MST), Kruskal (MST) or Dijkstra (SP), "Demo"-mode and "Next Step"
  11   tutORial's Shortest Path Module   SP: Use red links in the bullet points almost at the bottom of the page

 

Chapter 32 - Directed Graphs:

    Link:   Comments:
  1   Depth-First Search   Choose "New Graph" (until satisfied), "Directed Graph" and "Large Graph".
  Fill in "Start Vertex". "Run DFS". Use "Step Forward". Switch also to "Adjacency ... Representations".
  2     Transitive Closure (Warshall's Algorithm)
  3   Transitive Closure   Press the button at the bottom
  4   Floyd-Warshall All-Pairs Shortest Path   All Shortest Paths: Choose "New Graph" (until satisfied), "Directed Graph" and "Small Graph".
  "Run Floyd-Warshall". Use "Step Forward". Watch the three nodes in the lower left corner.
  5   The Floyd-Warshall Algorithm   All Shortest Paths: "Create a Graph" (drag the nodes to easier to see), "Run the Algorithm".
  6   Topological Sort (DFS)  

 

Chapter 33 - Network Flow:

    Link:   Comments:
  1   Max-Flow Problem: Ford-Fulkerson Algorithm   Choose "demo1-5" along left margin (e.g. demo2, demo3 or demo5).
  Upper figure most relevant. Click inside it.
  2   Ford-Fulkerson Max Flow  
  3   Example Networks3: Maximum Flow and Minimum Cut Problem   Oberserve, read (and use buttons)