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.

Table of contents

  1. Introduction and review
  2. Algorithm analysis
  3. List, stacks and queues
  4. Trees and hierarchical orders
  5. Ordered trees
  6. Search trees
  7. Priority queues
  8. Sorting algorithms
  9. Hash functions and hash tables
  10. Equivalence relations and disjoint sets
  11. Graph algorithms
  12. Algorithm design
  13. Theory of computation
  14. Other topics
  15. 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
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 - - - - W D -