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 can download the content for the mid-term here: midterm.zip.**

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 | ||
---|---|---|---|---|---|---|---|---|---|---|

W i k i p e d i a |
D A D S |
C + + |

1.1 | Introduction |
pptx | - | - | - | - | W | - | - | |

1.2 | Mathematical review |
pptx | - | Q | A | W | - | - | ||

1.3 | C++ |
pptx | - | - | - | - | See the C++ tutorial | W | - | C |

1.4 | Mathematical induction |
pptx | - | Q | A | W | - | - |

2.1 | Containers, relations, and abstract data types (ADTs) |
pptx | - | Q | A | W | - | C | ||

2.2 | Data structures and algorithms |
pptx | - | - | - | W | - | C | ||

2.3 | Asymptotic analysis |
pptx | - | Q | A | W | - | - | ||

2.4 | Algorithm analysis |
pptx | - | Q | - | W | - | - |

3.1 | Lists |
pptx | - | - | - | - | Also see string | W | D | C |

3.2 | Stacks |
pptx | - | Q | A | W | D | C | ||

3.3 | Queues |
pptx | - | Q | A | W | D | C | ||

3.4 | Deques |
pptx | - | 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 | - | - | - |

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 | V | Q | - | W | D | - | ||

4.2 | Abstract trees |
pptx | V | Q | - | W | - | - | ||

4.3 | Tree traversals |
pptx | 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 | - | - |

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 | - | Q | A | W | D | - | ||

5.2 | Perfect binary trees |
pptx | - | Q | A | W | D | - | ||

5.3 | Complete binary trees |
pptx | - | Q | A | W | D | - | ||

5.4 | N-ary trees |
pptx | - | Q | A | W | D | - | ||

5.5 | Balanced trees |
pptx | - | Q | A | W | D | - | ||

5.6 | Binomial trees | pptx | - | - | - | - | Optional | W | D | - |

5.7 | Left-child right-sibling binary trees | pptx | - | - | - | - | Optional | W | D | - |

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 | - | Q | A | W | D | - | ||

6.2 | AVL trees |
pptx | - | - | - | - | W | D | - | |

6.3 | In-order traversals |
pptx | - | Q | A | W | D | - | ||

6.4 | Multiway search trees (was M-way trees) |
pptx | - | 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 | - | - |

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 | - | Q | - | Español | W | D | C | |

7.2 | Binary heaps |
pptx | - | 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.1 | Introduction to sorting |
pptx | Q | - | W | D | C | |||

8.2 | Insertion sort |
pptx | - | Q | - | W | D | - | ||

8.3 | Bubble sort |
pptx | - | Q | - | W | D | - | ||

8.4 | Heap sort |
pptx | - | Q | - | W | D | - | ||

8.5 | Merge sort |
pptx | - | Q | - | W | D | - | ||

8.6 | Quicksort |
pptx | - | - | - | W | D | - | ||

8.7 | Bucket sort |
pptx | - | - | - | W | D | - | ||

8.8 | Radix sort |
pptx | - | - | - | - | W | D | - | |

8.9 | Inversions | pptx | - | - | - | Optional | W | - | - | |

8.10 | External sorting | pptx | - | - | - | Optional | W | D | - |

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 | - | - | - | W | D | - | ||

9.2 | Hash functions |
pptx | - | Q | - | W | D | - | ||

9.3 | Mapping down to 0, ..., M − 1 |
pptx | - | 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.1 | Disjoint sets |
pptx | - | - | - | - | Self study |
W | D | - |

10.2 | Trees and forests as disjoint sets | pptx | - | - | - | - | - | - | - | |

10.3 | Partition refinement | - | - | - | - | - | W | D | - |

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 | - | - | - | - | - | Optional | W | D | - |

11.8a | Ford-Fulkerson algorithms | - | - | - | - | - | Optional | W | D | - |

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 | pptx | - | - | - | - | Optional | W | D | - |

12.7 | Stochastic algorithms |
pptx | - | - | - | - | W | D | C |

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.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.01 | Summary and conclusions | pptx | - | - | - | - | W | D | - |