Relevant Algorithm Animations/Visualizations (in Java)

This collection of links to animations/visualizations of algorithms:

• is based on the textbook "Algorithms in C++" by Robert Sedgewick, Addison Wesley and Benjamin Cummings (nå: Pearson), 1992.
• do only cover those parts of the textbook relevant to the curriculum for the students at HiG.
• tries to cover a lot of different concepts within the area of "Computer Algorithms".
• do not claim to be complete in any sense, they are selected from the best ones the lecturer knows so far.
• are immediately runable (without any further installation of software packages) inside your browser (provided the use of a Java enabled browser)

Thanks to everyone that made these good/excellent animations available  ! ! !
(I hope they will be maintained, for the pleasure of the rest of us ....) Do You know about any interesting, relevant, or good animations ? Please, let me know .....
 

---

 

Collections (pages with a LOT of good animations):

1. Algoritmik: Animering af algoritmer
2. Animal Animations Collection
3. Computer Science Tutorial Page
4. Web Data Structures and Algorithms
5. TRAKLA2 - Exercises   (NOTE: Remove one of the "/exercises" in all the pages linked to!)
6. Sorting Algorithm Animations   (All sorting methods in the curriculum. See/use the options at the first line!)
7. The Sort Algorithm Animator V1.0   (All sorting methods in the curriculum)
8. Vivo Animations   (requires Vivio ActiveX Player installed!)
9. hatful of hollow - Visualising Sorting Algorithms   (a different approach .....)

 

Chapter 3: Elementary Data Structures

	Link/URL:	Keywords:	Page:	Comments:
1	Java Applets Centre: Linked List		17-22
2	Linked List		17-22
3	Java Applets Centre: Stack		25-26
4	Stack		25-26
5	Stack Operation Demonstration Program		27	Reads and calculates a postfix-expression.
5B	TRAKLA2 - Postfix evaluation		27	Calculates Postfix-expression (both demo ("Model answer") and self-test).
6	Infix, Postfix, Prefix Parser	URL not found!	28	See the program code in the textbook.
7	Java Applets Centre: Queue		30-31
8	Java Applets Centre: Cyclic Queue		30-31
9	Circular Queue		30-31
10	Train Sorting with Stacks			Practical "fun" use of stacks.

 

Chapter 4: Trees

	Link/URL:	Keywords:	Page:	Comments:
1	An Expression Tree Builder and Evaluator		40-43
2	Expression Tree Demonstration Program		40-43
3	Postfix Enumeration Demonstration Program		42
4	Java Applets Centre: Binary Tree Traversal		44-49
5	Interactive Data Structure Visualizations		44-49	Choose "Trees - Traversals" in the upper left corner.
6	Binary Treesome - The Applet		44-49	Choose "Tree: Standard" and "Insert", Build Tree,   Choose "Iteration", Practice!

 

Chapter 5: Recursion

	Link/URL:	Keywords:	Page:	Comments:
Textbook Relevant:
1	The Fibonacci Numbers and the Golden section			A lot of fun stuff about Fibonacci-numbers.
2	Fibonacci Interactive			Shows the recursive "call tree". Use the "arrows" in the upper left corner.
Theory Basics:
1	Introduksjon til rekursjon			Source: http://www.ifi.uib.no/undervisning/iv132/forel/f02.ppt
2	Lecture3; Linked Lists; Recursion			Go to "Recursion" - 40% from the bottom of the page.
3	Lecture 3 - Recursion
4	Tom Kelliher's Lectures:                 * Introduction to Recursion                 * Recursion, Concepts and Examples                 * More Recursion                 * Recursion, Searching, and Efficiency                 * Recursion as a Problem Solving Technique
Specific:
1	The Animation of Recursion			Money Collector, Factorial, String Reversal, Quicksort, see exercise 6 and 9.
2	Dynamic Programming: Towers of Hanoi			See exercise 6.
3	Towers of Hanoi			See exercise 6.
4	Tower of Hanoi History & Instructions			See exercise 6.
5	The Tower of Hanoi			See exercise 6.
6	Towers from Hanoi			See exercise 6.
7	Java Applets Centre: Tower of Hanoi			See exercise 6.
8	Java Applets Centre: N-Queens Problem			See exercise 9.
9	The Eight Queens Problem			See exercise 9.
10	"The Eight Queens Problem"			See exercise 9.
11	Backtracking: The Queens Problem			See exercise 9.
12	Generate Solutions to n-Queens Problem			See exercise 9.
13	Rat In a Maze			See Exam of 12.12.1995 number 4.
14	MazeWorks - MazeGen			See Exam of 12.12.1995 number 4.
15	Church's Thesis			Some mathematical.
16	Recursion and Graphics			Pictures and program code (in Lisp).
17	Chris Hruska's Stupid Recursion Tricks			Entertainment .....
Permutation:
1	Information on Permutations
2	Generate Permutations
3	Permutations			Follow links in the text, and at the end of the document.
Fun:
1	Recursive Painting

 

Chapter 8: Elementary Sorting Methods

	Link/URL:	Keywords:	Page:	Comments:
1	Animation of Sorting Algorithms	Selection	URL not found!	Tickmark "Selection".
2	Visual Sorting	Selection, Insertion, Bubble	URL not found!	Choose method in the middle at the bottom.
3	The xSortLab Applet	Selection, Insertion, Bubble		Choose "Selection", "Insertion" or "Bubble".
4	Sorting Algorithms	Selection, Insertion, Bubble, Shell		Choose Sorting method at the bottom left of the first window.
5	Sorting Algorithms in C++	Selection, Insertion, Bubble, Shell		Choose Sorting method at the top and which array to be sorted.
6	Animation of Sorting Algorithms	Selection, Insertion, Bubble, Shell	101-102 and 111	Covers all seven sorting methods in the textbook,   but choose here one of the four relevant methods.   (alternatively use: dmh2000 - Sorting Dynamics (Bubble and Shell))
7	Animation of Sort Algorithms	Selection, Insertion, Bubble, Shell		Press the button at the top of the page.   Choose sorting method under "Algorithms" at the top.
8	The Animator	Selection, Insertion, Bubble, Shell		Choose method in the lower right corner.
8B	Sorting Out Sorting (ver 2.0 - Demo)	(Linear) Insertion, Bubble, Shell		Choose method(s) at upper left, click "Add" and "Run Playlist".
9	Java Applets Centre: Selection Sort	Selection
10	Example of Sorting Algorithm's Animation	Selection
11	Java Applets Centre: Insertion Sort	Insertion
12	Data Structures and Algorithms: Sorting	Insertion		Press the "Run the Animation"-button in the middle of the page.
13	Example of Sorting Algorithm's Animation	Insertion
14	Java Applets Centre: Bubble Sort	Bubble
15	Bubble	Bubble
16	Example of Sorting Algorithm's Animation	Bubble
17	Bubble Sort	Bubble
18	Bubblesort-Animation	Bubble		"Fun".
19	Bubble Sort Program	Bubble		Note: Increasing sorting, and not decreasing   (as in the textbook).
20	Shell Sort	Shell
21	Shell Sort Animation	Shell
22	Java Animations of Shellsort and variants	Shell		Choose "Increment Sequence" at the bottom right.
23	AIA: Shellsort	Shell		guest / gjovik     Choose "Shellsort".
24	AIA: Distribution Counting	Distribution Counting		guest / gjovik     Choose "Distribution Counting".   Note: Last for-loop is increasing, and not decreasing   (as in the textbook).
25	YouTube: What different sorting algorithms sound like.	Insert, Bubble, Selection, Merge, Gnome		Fun.

 

Chapter 9: Quicksort

	Link/URL:	Keywords:	Page:	Comments:
1	AIA: Quicksort
2	The xSortLab Applet			Choose "Quicksort".   NOTE: Uses the left one as partition element.
3	Sorting Algorithms in C++			Choose "Quicksort" at the top and which array to be sorted.
4	The Animation of Recursion - Quicksort			NOTE: Uses the left one as partition element.
5	Sorting Algorithms			Choose "Quicksort" at the bottom left of the first window.
6	Visual Sorting	URL not found!		Choose "Quicksort" in the middle at the bottom.   NOTE: Uses the middle one as partition element and moves it to the front.
7	Animation of Sorting Algorithms	URL not found!		Tickmark "Quicksort".
8	Sorting - Quicksort	???		Choose "Quicksort" in the window at the bottom.
9	The Animator			Choose "Quicksort" in the lower right corner.
9B	Sorting Out Sorting (ver 2.0 - Demo)			Choose "Quicksort" at upper left, click "Add" and "Run Playlist".   NOTE: Uses the left one as partition element.
10	Quicksort
11	Java Applets Centre: Quick Sort
12	Quicksort-Animation			"Fun".
13	Animation of Sorting Algorithms		125	Covers all seven methods in the textbook, but choose here "Quicksort".   (alternatively use: dmh2000 - Sorting Dynamics)

 

Chapter 11: Priority Queues / Heaps

	Link/URL:	Keywords:	Page:	Comments:
1	Interactive Data Structure Visualizations		148-154	Choose "Trees - Priority Queue" in the upper left corner.
2	Heaps		148-154	Press the button "Run The Animation" at the bottom.
2b	Java Applets Centre: Priority Queue		148-154	Note:Smallest number as the root/at the top!
3	A Priority Queue Tester	URL not found!		Build your own Heap 1
4	Animation of Sorting Algorithms	URL not found!	156-159	Tickmark "Heapsort".
5	Data Structures and Algorithms: Heap Sort		156-159	Press the button "Run Heap Sort" at the bottom.
6	AIA: Heapsort		156-159
7	Interactive Data Structure Visualizations		156-159	Choose "Sorting - Heap Sort" in the upper left corner.
8	Sorting Algorithms		156-159	Choose "Heapsort" at the bottom left of the first window.
9	Sorting Algorithms in C++		156-159	Choose "Heapsort" at the top and which array to be sorted.
9B	Sorting Out Sorting (ver 2.0 - Demo)		156-159	Choose "Heapsort" at upper left, click "Add" and "Run Playlist".
10	Heapsort		156-159	Press the button "ANIMATION" at the bottom.
11	Heap sort visualization: Java applet		156-159	Note: Downheaps already when inserting (backwards)!
12	Animation of Sorting Algorithms		158-159	Covers all seven methods in the textbook, but choose here "Heapsort".   (alternatively use: dmh2000 - Sorting Dynamics)
13	YouTube: Heapsort audibilization.			Fun.

 

Chapter 12: Mergesort

	Link/URL:	Keywords:	Page:	Comments:
1	Merge Example (of two arrays)		164
2	MergeSort demo with comparison bounds		165-166	See in the middle of the page/document.
3	Java Applets Centre: Merge Sort		165-166
4	Mergesort		165-166
5	Sorting - Mergesort	???	165-166	Choose "Mergesort" in the window at the bottom.
6	The Animator			Choose "Mergesort" in the lower right corner.
7	The xSortLab Applet			Choose "Mergesort". Note: Operates a little different from the textbook !
8	Sorting Algorithms in C++		165-166	Choose "Mergesort" at the top and which array to be sorted.
9	Animation of Sorting Algorithms		172-174	Covers all seven methods in the textbook, but choose here "Mergesort".   (alternatively use: dmh2000 - Sorting Dynamics)

 

Chapter 14: Elementary Searching Methods

	Link/URL:	Keywords:	Page:	Comments:
1	Java Applets Centre: Linear Search		195	Unsorted array.
2	Java Applets Centre: Binary Search		198-201	Sorted array.
3	Java Applets Centre: Binary Search Tree (Search)		203-205
4	Java Applets Centre: Binary Search Tree (Insert, Delete)		205-211
5	Binary Treesome - The Applet		203-211	Choose "Tree: Sorted" and "Insert", Practice Adding/Deleting/Searching Nodes!
6	Animated Binary Tree		203-211	Build your own Binary Tree 1
7	Binary Search Trees	URL not found!	203-211
8	Interactive Data Structure Visualizations		203-211	Choose "Trees - Search Trees" in the upper left corner.
9	Binary Search Tree Program		203-209
10	Binary Search Tree	???	203-209
11	Standard Binary Search Tree		203-209

 

Chapter 15: Balanced Trees

	Link/URL:	Keywords:	Page:	Comments:
1	Top-Down 2-3-4 Trees / Red-Black Trees	URL not found!	215-229	Note: Maximaze the windows for the animation !
1B	Graphical 2-3-4 Tree		215-219
2	AIA: 234 Tree		215-229
3	Red/Black Tree Demonstration		220-229
4	Data Structures and Algorithms: Red-Black Trees		220-229	Press the "Run Red-Black Tree Animation"-button at the bottom.
5	Topic #18: Red-Black Trees		220-229
6	Red-Black Trees		220-229
7	AIA: Red Black Tree		220-229	guest / gjovik     Choose "Red Black Tree".
8	Binary Search Tree (AVL)		220-229	Open "Options" in upper left corner - choose from menu.
9	Binary Search Trees (Stromceky)		220-229	Choose "Red-black tree" from upper menu.
10	Red-Black Tree Animation		220-229	Shows split and rotation in a good way.
11	dmh2000 Red-Black Trees		220-229
12	Red-Black Binary Search Tree	???	220-229
13	Rotation Tutorial	URL not found!		Only about rotation of trees.

 

Chapter 16: Hashing

	Link/URL:	Keywords:	Page:	Comments:
1	Separate-Chaining Hash Table	Separate Chaining	234-236
2	Hash Table Demonstration - Separate Chaining	Separate Chaining	234-236
3	Linear-Probe Hash Table	Linear Probing	236-239
4	Data Structures and Algorithms: Hash Tables	Linear Probing	236-239	Press the "Run the Animation"-button at the bottom.
5	Hash Table Demonstration - Linear Probing	Linear Probing	236-239
6	Double/Quad Hash Table	Double/Quad Hashing	239-242
7	Hashing Animation Tool	Several .....

 

Chapter 22: File Compression

	Link/URL:	Keywords:	Page:	Comments:
1	Huffman Compression Applet	URL not found!	324-330	Write in your own text to compress!
2	Huffman Encoding		324-330	Press the button "Run The Animation" at the bottom.
3	Huffman Coding		324-330	Shockwave demo.
4	Practical Huffman Coding		324-330
5	Adaptive Huffman Compression		324-330
6	Lossless Data Compression (Huffman / Lempel-Ziv)		(324-330)	Animation of Lempel-Ziv in the middle of the page.
7	LZW		(324-330)	Press the button almost at the bottom of the page.
Compression Resources:
1	Mitsuharu ARIMURA's Bookmarks on Source Coding/Data Compression			Huge list of compression resources.
2	Compression Pointers	URL not found!
3	DataCompression.info	???		See escpescially the "Huffman Coding" and its   "Tutorials, Reference, Presentations"-section at the bottom.
Lectures:
1	Introduction to data compression			This article is curriculum in our course!
2	Michael Dipperstein's Page O'Stuff			See comprehensive Compression-links in the upper left corner.
3	Compression Algorithms			A lot of good theory material.
4	Huffman Coding			"Long" detailed explanation!
5	LZW Data Compression			"Long" detailed explanation with commentary!
FAQs:
1	Compression FAQ (HTML)			Official FAQ.   ASCII-/TXT-version
2	PKWARE: FAQs (on PKZip)			FAQs about PKZIP for different platforms/OS.

 

Chapter 29-33: General (Terms) About Graphs

	Link/URL:	Keywords:	Page:	Comments:
1	Graph Theory Tutorial - Glossary of Terms
2	Graph Theory Tutorial - Graph Terminology			Two pages. Se also two "Here"-links at the second page.
3	JGraphEd			Excellent General Tool for Graph-drawing/-testing.   Download here.
4	Java-Graph-Editor	URL not found!		Very comprehensive. Press the button "Show Java-Graph-Editor".
5	Programs for Graph Algorithm Package (IAPPGA)			Plain, Weighted and/or Directed graphs. Excellent page!
6	Games on Graphs
7	Mathmania Graph Theory	URL not found!

 

Chapter 29: Elementary Graphs Algorithms

	Link/URL:	Keywords:	Page:	Comments:
1	Class notes CS251B - Winter 1997: Graphs		415-423	See especially the animation near the bottom.
2	Interactive Data Structure Visualizations - Categorizing   (Connected?, Cycles?, Tree?)		417	Choose "Graphs - Categorizing" in the upper left corner.
3	Interactive Data Structure Visualizations - Representation   (Adjacent Matrix)		418-421	Choose "Graphs - Representation" in the upper left corner.
4	Graph Theory Tutorial - Graph Representation   (Adjacent Matrix, Adjacent List, Trees)		418-423	Three pages.   See especially the last "Here"-link at the first page.
5	Interactive Data Structure Visualizations - Searches (DFS/BFS)		423-433	Choose "Graphs - Searches" in the upper left corner.
6	BFS and DFS	Search Forest	423-433
7	Java Applets Centre: Graph Traversal (DFS/BFS)		423-433
8	Class notes CS251B - Winter 1997: DFS		423-428	See especially the animation at the bottom.
9	Example of Graph Algorithm's Animation - Depth-First-Search		423-428
10	Graph Algorithms Animation - DFS		423-428	Choose "Depth-First-Search" from "Select Menu".
11	Class notes CS251B - Winter 1997: BFS		431-433	See especially the animation at the bottom.
12	Example of Graph Algorithm's Animation - Breadth-First-Search		431-433
13	Graph Algorithms Animation - BFS		431-433	Choose "Breadth-First-Search" from "Select Menu".
14	Wire Routing (Using Queues) - BFS			Practical "fun" use of BFS/Queue.
15	BFS/DFS Animations		433	Shows the difference in a clear way.

 

Chapter 30: Connectivity

	Link/URL:	Keywords:	Page:	Comments:
1	Tutorial on Connected Components		437-438
2	Sets Union/Find Demonstration Program		441-449	The demo shows Union with Path Compression (without Weight Balancing)   over the edges: 01, 43, 23, 56, 14, search(3), 89, 86, 37,   search(5), search(6), 75, search(6).
3	Graphical Union-Find Structure		441-449	Build yourself Union(-Find) (without Path Compression and Weight Balancing).
4	Union/Find Algorithm Visualization		441-449	Union with Path Compression.

 

Chapter 31: Weighted Graphs

	Link/URL:	Keywords:	Page:	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	Class notes CS251B - Winter 1997: Minimum Spanning Tree		452-458	See especially the animation at the bottom.
2	Graph Theory Tutorial - Minimum Spanning Tree	URL not found!	452-458
3	Minimum Spanning Tree Demonstration Program		452-458
4	Graph Algorithms Animation - Minimum Spanning Tree		452-458	Choose "Minimum Spanning Tree" from "Select Menu".   Increase the delay also.
5	Prim/Kruskal/Dijkstra's Algorithm		454-467	Choose "Prim", "Kruskal" og "Dijkstra" Algorithm.
6	5.7.1 Dijkstra Algorithm		461-465
7	Data Structures and Algorithms: Dijkstra's Algorithm		461-465	Press the button "Run the Animation" at the bottom.
8	Shortest Path Problem: Dijkstra's Algorithm		461-465	Follow the link "Java Applet Demos" along the left margin.
9	Dynamic Programming: The Shortest Path Module		461-465
10	Dynamic Programming: Dijkstra's Algorithm Module		461-465
11	Dijkstra's Shortest Path Algorithm Animation in Java	URL not found!	461-465	Build your own graph and test!
12	Shortest Path Algorithm		461-465
13	Class notes CS251B - Winter 1997: Shortest Path		(461-465)
14	Graph Algorithms Animation - Shortest Path		461-465	Choose "Shortest Path" from "Select Menu".
15	Dijkstra's Shortest Path Algorithm		461-465	Build your own graph and test!

 

Chapter 32: Directed Graphs

	Link/URL:	Keywords:	Page:	Comments:
1	Depth First Search		472-473
2	Breadth First Search
2B	Application programs - Transitive Closure (Warshall's Algorithm)		473-476	See the second half of the page, and the animation at the bottom.
3	All Pairs Minimum Routes Problem (Floyd's Algorithm)		476-478
4	All Pair Shortest Paths (Floyd's Algorithm)		476-478
5	Floyd-Warshall All-Pairs-Shortest-Path Algorithm		476-478
5B	Applet Floyd-Warshall		476-478
6	Class notes CS251B - Winter 1997: Directed Acyclic Graphs (Dag)		479-481	See especially the animation at the bottom.

 

Chapter 33: Network Flow

	Link/URL:	Keywords:	Page:	Comments:
1	Graph Theory Tutorial - Flow Problems	URL not found!
2	Max Flow min cut Example	URL not found!	487-489
3	Max-Flow Problem: Ford-Fulkerson Algorithm		487-489	Follow the link "Java Applet Demos" along the left margin.
4	Max Flow Applet Home		487-489
5	Maximum Flow Algorithm Applet	URL not found!	487-489
6	Network Flow			Build yourself !
7	Max Flow (of Ford-Fulkerson Method)		487-489	Build yourself !
8	Maximum Flow Algorithms Applet		487-489	Build yourself !

 

Finite State Machine (NOT in the textbook):

	Link/URL:	Keywords:	Comments:
1	DynaLab Finite State Automation Applet	?????	Code: See number 2 below.
2	FSM Animator	?????	Press the red "Show Program Animator"-button at the bottom.   Figure: See number 1 above.
3	The Finite State Machine Explorer	URL not found!	Build your own FSM.   See in the middle of the page.
4	State Machine Simulator		Build your own FSM.
5	Finite State Machine	URL not found!	Build your own FSM.
6	Finite State Machine Drawing	URL not found!
7	Finite-State Machine Simulator
8	reAnimator: Regular Expression FSA Visualizer		Click pink text, or write your own expression (by clicking "edit" in upper left corner).   Write input text inside pink field along upper margin.
Theory:
1	Wikipedia: FSM
2	FSM (by Dr.Matt Stallmann)
3	Contemporary Logic Design		See chapter 8-10.
4	Google Search: lang:"C++" FSM