Lecture Materials

If you wish, you can read through a seven-page course description. A 21-page topic summary is also available: Algorithms and data structures—topic summary.

This is a collection of PowerPoint (pptx) slides ("pptx") presenting a course in algorithms and data structures. Associated with many of the topics are a collection of notes ("pdf"). Some presentations may be associated with videos ("V") and homework questions ("Q"), possibly with answers ("A"). Some topics also links to corresponding Wikipedia page ("W"), entries in the NIST Dictionary of Algorithms and Data Structures (DADS) ("D"), and references to cplusplus.com ("C").

You will note that the section numbering in the notes is paralleled in the top left corner of the slides; thus, anyone watching the slides can follow along in the notes.

Spanish notes translated by Christian von Lücken.

Introduction and review
Algorithm analysis
List, stacks and queues
Trees and hierarchical orders
Ordered trees
Search trees
Priority queues
Sorting algorithms
Hash functions and hash tables
Equivalence relations and disjoint sets
Graph algorithms
Algorithm design
Theory of computation
Other topics
Concluding remarks

S e c t i o n	Topic	S l i d e s	N o t e s	V i d e o	Q u e s t i o n s	A n s w e r s	Comments	Links
S e c t i o n	Topic	S l i d e s	N o t e s	V i d e o	Q u e s t i o n s	A n s w e r s	Comments	W i k i p e d i a	D A D S	C + +

1. Introduction and review

1.1	Introduction	pptx	-	-	-	-		W	-	-
1.2	Mathematical review	pptx	pdf	-	Q	A		W	-	-
1.3	C++	pptx	-	-	-	-	See the C++ tutorial	W	-	C
1.4	Mathematical induction	pptx	pdf	-	Q	A		W	-	-

2. Algorithm analysis

2.1	Containers, relations, and abstract data types (ADTs)	pptx	pdf	-	Q	A	W	-	C
2.2	Data structures and algorithms	pptx	pdf	-	-	-	W	-	C
2.3	Asymptotic analysis	pptx	pdf	-	Q	A	W	-	-
2.4	Algorithm analysis	pptx	pdf	-	Q	-	W	-	-

3. Lists, stacks, and queues

3.1	Lists	pptx	-	-	-	-	Also see string	W	D	C
3.2	Stacks	pptx	pdf	-	Q	A		W	D	C
3.3	Queues	pptx	pdf	-	Q	A		W	D	C
3.4	Deques	pptx	pdf	-	Q	-		W	D	C
3.5	Linked lists	pptx	-	-	-	-	Required for Project 1	W	D	C
3.6	Node-based storage with arrays	pptx	-	-	-	-	Optional	-	-	-

4. Trees and hierarchical orders

Before we proceed with looking at data structures for storing linearly ordered data, we must take a diversion to look at trees. At first glance, it appears as if trees are most appropriate for storing hierarchically ordered data; however, we will later see how trees can also be used to allow efficient storage of linearly ordered data, as well.

4.1	Introduction to trees	pptx	pdf	V	Q	-		W	D	-
4.2	Abstract trees	pptx	pdf	V	Q	-		W	-	-
4.3	Tree traversals	pptx	pdf	V	Q	-		W	D	-
4.4	Parental trees	pptx	-	-	-	-	Optional	W	-	-
4.5	Forests	pptx	-	-	-	-	Optional	W	-	-
4.6	The mechanism of recursion, part 1	pptx	-	-	-	-	Optional	W	-	-

5. Ordered trees

A general tree is appropriate for storing hierarchical orders, where the relationship is between the parent and the children. There are many cases, however, where the tree data structure is more useful if there is a fixed number of identifiable children. This topic looks at binary trees as well as perfect and complete binary trees, N-ary trees, the concept of balance, binomial trees, and left-child right-sibling binary trees (a technique for storing general trees as binary trees).

5.1	Binary trees	pptx	pdf	-	Q	A		W	D	-
5.2	Perfect binary trees	pptx	pdf	-	Q	A		W	D	-
5.3	Complete binary trees	pptx	pdf	-	Q	A		W	D	-
5.4	N-ary trees	pptx	pdf	-	Q	A		W	D	-
5.5	Balanced trees	pptx	pdf	-	Q	A		W	D	-
5.6	Binomial trees	pptx	-	-	-	-	Optional	W	D	-
5.7	Left-child right-sibling binary trees	pptx	-	-	-	-	Optional	W	D	-

6. Search trees

This topic looks at storing linearly ordered data in search trees. The focus is to ensure that operations on individual elements stored in the tree run in Θ(ln(-)) time.

6.1	Binary search trees	pptx	pdf	-	Q	A		W	D	-
6.2	AVL trees	pptx	-	-	-	-		W	D	-
6.3	In-order traversals	pptx	pdf	-	Q	A		W	D	-
6.4	Multiway search trees (was M-way trees)	pptx	pdf	-	Q	A		-	D	-
6.5	B+ trees	pptx	-	-	-	-		W	D	-
6.6	Red-Black trees	pptx	-	-	-	-	Optional	W	D	-
6.7	k-d trees	pptx	-	-	-	-	Optional	W	D	-
6.8	BB[α] trees	pptx	-	-	-	-	Optional	-	D	-
6.9	Splay trees	pptx	-	-	-	-	Self study	W	D	-
6.10	Average depth of random binary trees	pptx	-	-	-	-	Optional	W	-	-

7. Priority queues

A priority queue stores linearly ordered data based on the priority; however, by restricting the operations, those operations can be optimized.

7.1	Priority queues	pptx	pdf	-	Q	-	Español	W	D	C
7.2	Binary heaps	pptx	pdf	-	Q	-	Español	W	D	-
7.3	d-ary heaps	pptx	-	-	-	-	Optional	W	D	-
7.4	Leftist heaps	pptx	-	-	-	-	Optional	W	D	-
7.5	Skew heaps	pptx	-	-	-	-	Optional	W	-	-
7.6	Binomial heaps	pptx	-	-	-	-	Optional	W	D	-

8. Sorting algorithms

8.1	Introduction to sorting	pptx	pdf		Q	-		W	D	C
8.2	Insertion sort	pptx	pdf	-	Q	-		W	D	-
8.3	Bubble sort	pptx	pdf	-	Q	-		W	D	-
8.4	Heap sort	pptx	pdf	-	Q	-		W	D	-
8.5	Merge sort	pptx	pdf	-	Q	-		W	D	-
8.6	Quicksort	pptx	pdf	-	-	-		W	D	-
8.7	Bucket sort	pptx	pdf	-	-	-		W	D	-
8.8	Radix sort	pptx	-	-	-	-		W	D	-
8.9	Inversions	pptx	pdf	-	-	-	Optional	W	-	-
8.10	External sorting	pptx	pdf	-	-	-	Optional	W	D	-

9. Hash functions and hash tables

Note that previously I used to teach linear probing and double hashing; however, it has been brought to my attention that quadratic hashing is better—especially when we consider the effects of caching and the additional cost of cache misses.

9.1	Introduction to hash tables	pptx	pdf	-	-	-		W	D	-
9.2	Hash functions	pptx	pdf	-	Q	-		W	D	-
9.3	Mapping down to 0, ..., M − 1	pptx	pdf	-	Q	-		W	-	-
9.4	Chained hash tables	pptx	-	-	Q	-		W	D	-
9.5	Scatter tables	-	-	-	-	-		-	-	-
9.6	Open addressing	pptx	-	-	Q	-		W	D	-
9.7	Linear probing	pptx	-	-	Q	-		W	D	-
9.8	Quadratic probing	pptx	-	-	-	-		W	D	-
9.9	Double hashing	pptx	-	-	Q	-	Optional	W	D	-
9.10	Poisson distribution	pptx	-	-	-	-	Optional	W	-	C

10. Equivalence relations and disjoint sets

10.1	Disjoint sets	pptx	-	-	-	-	Self study	W	D	-
10.2	Trees and forests as disjoint sets	pptx	-	-	-	-		-	-	-
10.3	Partition refinement	-	-	-	-	-		W	D	-

11. Graph algorithms

11.1	Introduction to graph theory	pptx	-	-	-	-		W	D	-
11.2	Graph data structures	pptx	-	-	-	-	Required for Project 5	-	-	-
11.3	Graph traversals	pptx	-	-	-	-	Optional	W	-	-
11.3a	Connectedness	pptx	-	-	-	-	Optional	-	-	-
11.3b	Single source unweighted path length	pptx	-	-	-	-	Optional	-	-	-
11.3c	Identifying bipartite graphs	pptx	-	-	-	-	Optional	-	-	-
11.4	Topological sort	pptx	-	-	-	-	Español	W	D	-
11.5	Minimum spanning tree algorithms	pptx	-	-	-	-		W	D	-
11.5a	Prim's algorithm	pptx	-	-	-	-	Español	W	D	-
11.5b	Kruskal's algorithm	pptx	-	-	-	-	Optional	W	D	-
11.6	Single-source shortest path algorithms	pptx	-	-	-	-		W	D	-
11.6a	Dijkstra's algorithm	pptx	-	-	-	-		W	D	-
11.6b	A* search algorithm	pptx	-	-	-	-	Optional	W	-	-
11.6c	Bellman-Ford algorithm	-	-	-	-	-	Optional	W	D	-
11.7	All-pairs shortest path	pptx	-	-	-	-	Optional	W	D	-
11.7a	Floyd-Warshall algorithm	pptx	-	-	-	-	Optional	W	D	-
11.7b	Johnson's algorithm	-	-	-	-	-	Optional	W	D	-
11.8	Maximum flow algorithms incl. Ford-Fulkerson and Edmonds-Karp	pptx	-	-	-	-	Optional	W W W	D D	-
-

12. Algorithm design

12.1	Introduction to algorithm design techniques	pptx	-	-	-	-		W	-	-
12.2	Greedy algorithms	pptx	-	-	-	-		W	D	-
12.3	Divide-and-conquer algorithms	pptx	-	-	-	-		W	D	-
12.4	Dynamic programming	pptx	-	-	-	-		W	D	-
12.5	Backtracking algorithms	pptx	-	-	-	-		W	D	-
12.6	Branch-and-bound algorithms		-	-	-	-	Optional	W	D	-
12.7	Stochastic algorithms	pptx	-	-	-	-		W	D	C

13. Theory of computation

13.1	Theory of computation	pptx	-	-	-	-	W	D	-
13.2	Turing completeness	pptx	-	-	-	-	W	D	-
13.3	Decidability and the halting problem	pptx	-	-	-	-	W	D	-
13.4	NP completeness	pptx	-	-	-	-	W	D	-

14. Other topics

14.1	Sparse matrices	pptx	-	-	-	-	Optional	W	D	-
14.2	Searching algorithms	pptx	-	-	-	-	Optional	W	D	-
14.3	Standard Template Library (STL) summary	pptx	-	-	-	-	Optional	W	-	-

15. Concluding remarks

15.01

Summary and conclusions

pptx