Note that the power point slides are from a previous course offering, so some of the information is out of date.

Course Introduction (Lecture 1)

Algorithms and Analysis (Lecture 1, Chapter 2)

Insertion Sort, Review of Loop Invariants (Lecture 1, Chapter 2)

Asymptotic Notation, Functions and Summations (Lecture 2, Chapter 3, Appendix A)

Divide and Conquer (Merge Sort), Recurrence Relations (Lecture 3, Chapter 2.3, 4)

Recurrence Relations (Lecture 4, Chapter 4)

How to Shuffle on a Computer (Lecture 5,6, Chapter 5)

Elementary Sorting Algorithms (Lecture 7)

Heapsort (Lecture 7, Chapter 6)

Quicksort, Recurrence Relations (Lecture 8, Chapter 7; Lecture 4, Chapter 4)

Randomized Quicksort, Probabilistic Analysis of Algorithms, Discrete Probability

(Lecture 8, Chapter 7; Lecture 5,6, Appendix C, Chapter 5)

Exam 1 (Lecture 9)

Lower Bounds for Comparison Sorting, Linear Time Sorting, Hash Tables

(Lecture 10, Chapter 8.1; Lecture 11,12 Chapter 8; Lecture 15, Chapter 11)

Lower Bounds for Comparison Sorting, Linear Time Sorting (better version)

(Lecture 10, Chapter 8.1; Lecture 11,12 Chapter 8)

Skills in demand for programmers

Order Statistics (Selection) (Lecture 13,14, Chapter 9)

Hash Tables (Lecture 15, Chapter 11)

Examples of multiplicative hashing (Lecture 15, Chapter 11)

Example of universal hashing (Lecture 15, Chapter 11)

Hash Tables (Lecture 16, Chapter 11)

Binary Search Trees (Lecture 17, Chapter 12)

Red Black Trees (Lecture 18, Chapter 13)

Animation of red black tree insert (Lecture 18, Chapter 13)

Insertion and deletion in a red black tree (Lecture 18, Chapter 13)

Deletion in a red black tree (Lecture 18, Chapter 13)

Dynamic Programming (Lecture 19, 21, Chapter 15)

Exam 2 (Lecture 20)

Dynamic Programming (Lecture 19,21, Chapter 15)

Dynamic Programming (Lecture 19,21, Chapter 15)

Greedy Algorithms, Minimum Spanning Trees (Lecture 22,23, Chapter 16; Lecture 26, Chapter 23)

Graphs, Breadth First and Depth First Search (Lecture 24, Chapters 22)

Topological Sort, Strongly Connected Components, (Lecture 25, Chapter 22)

Minimum Spanning Trees, Kruskal's Algorithm (Lecture 26, Chapter 23)

Minimum Spanning Trees, Prim's Algorithm (Lecture 26, Chapter 23)

Single Source Shortest Paths (Lecture 27, 28, Chapter 24)