Course Slides
Course Slides
“Pre-lecture” are sets to be reviewed before class; they will normally be incomplete (or rather, abridged), with tricky/open questions for you to give it a try beforehand.
During the class, a more complete set of slides will be used, hopefully answering all the open issues with the pre-lecture slides, and these will be posted as “post-lecture” slides.
Slides for next lecture
For convenience, you'll always have the link to the slides for the upcoming class (so that you don't need to keep scrolling — more and more as the course progresses):
Slides and related reading
| Pre-lecture | Post-lecture | Related reading (optional) |
| N/A | 2012-01-04 — Introduction | -- |
| 2012-01-06 | Math review (some details fixed) | Mark Allen Weiss' Section 1.2 |
| 2012-01-09 | Mathematical Induction | Mark Allen Weiss' Section 1.2.5
Wikipedia's page on Mathematical Induction |
| 2012-01-11 | Mathematical proofs | Wikipedia's page on Mathematical Proofs |
| 2012-01-13 | Asymptotic analysis (a few details fixed, 2012-01-17) | CLRS – Chapter 3
Mark Allen Weiss' Chapter 2 |
| 2012-01-16 | Asymptotic analysis (cont'd) (a few details added, 2012-01-17) | CLRS – Chapter 3
Mark Allen Weiss' Chapter 2 |
| 2012-01-18 (12:30) | Algorithm analysis | Mark Allen Weiss' Chapter 2
CLRS – Section 2.2 |
| 2012-01-18 (4:30) | Containers and relations (couple of details added, 2012-01-19)
and typo fixed (2012-01-20) |
Wikipedia: Total Order, Partial Order, Equivalence Relations, Strict Weak Ordering |
| 2012-01-20 | Sequential containers | Mark Allen Weiss' Chapter 3 (Sections 3.1, 3.2, 3.6, 3.7)
CLRS – Section 10.1 |
| 2012-01-23 | Sequential containers (cont'd) | Mark Allen Weiss' Chapter 3 (Sections 3.2, 3.5, and optionally 3.3)
CLRS – Section 10.2 |
| 2012-01-25 | Hash tables | Mark Allen Weiss' Chapter 5 (chapter 5 covers all the material that we'll cover over the next three classes)
CLRS – Chapter 11 (same comment as above) |
| 2012-01-27 | Hash tables (cont'd) | Mark Allen Weiss' Chapter 5; CLRS – Chapter 11 |
| 2012-01-30 | Hash tables – Linear probing | Mark Allen Weiss' Chapter 5; CLRS – Chapter 11 |
| 2012-02-01 (12:30) | Hash tables – Double hashing | Mark Allen Weiss' Chapter 5; CLRS – Chapter 11 |
| Not necessary | 2012-02-01 (4:30) – Trees (intro) | Mark Allen Weiss' Chapter 4 |
| 2012-02-03 | 2012-02-03 – Tree implementations and traversals (typo fixed, 2012-02-03-8:30PM) | Mark Allen Weiss' Chapter 4 |
| 2012-02-06 | 2012-02-06 – Binary trees | Mark Allen Weiss' Chapter 4 |
| 2012-02-08 | 2012-02-08 – Binary search trees | Mark Allen Weiss' Chapter 4; CLRS – Chapter 12 |
| Not necessary | 2012-02-10 – Case-studies (expression trees, data compression) + if we have enough time, we'll look at some preliminaries on balancing binary search trees | Mark Allen Weiss' Section 4.2.2 for Expression trees; http://en.wikipedia.org/wiki/Huffman_coding (if you're curious about Huffman coding and data compression — not part of the course material!) |
| 2012-02-13 | Balanced BSTs / AVL Trees | Mark Allen Weiss' Section 4.4 |
| Not necessary | 2012-02-15 – AVL Trees + example/case-study | Mark Allen Weiss' Section 4.4 |
| N/A | Review and information/tips for the midterm | PLEASE SEE NOTE AT THE BEGINNING (AT THE TOP) OF THIS PAGE! |
| N/A | 2012-03-05 – M-Way and B-Trees | Mark Allen Weiss' Section 4.7; Professor Harder's slides on B-Trees |
| 2012-03-07 (12:30) | Sorting algorithms (intro) | Professor Harder's course notes: Intro to sorting, Insertion sort, Merge sort |
| 2012-03-07 (4:30) | Priority queues and Heaps | Professor Harder's course notes: Priority queues, Binary heaps |
| 2012-03-09 | Heap sort | Professor Harder's notes: Heap sort |
| 2012-03-12 | Quick sort | Complete quick sort example (copy-n-pasted directly from Prof. Harder's slides Prof. Harder's course notes |
| Notice that for all the sorting algorithms and Heaps topics, you have the relevant sections on Mark Allen Weiss textbook and also on CLRS. | ||
| Not necessary | 2012-03-14 – Graphs (intro) | Mark Allen Weiss' section 9.1 |
| 2012-03-16 | Topological sort | Mark Allen Weiss' section 9.2 |
| 2012-03-19 | Dijkstra's algorithm | Mark Allen Weiss' section 9.3.2 |
| 2012-03-21 | Minimum spanning trees | Mark Allen Weiss' section 9.5 |
| 2012-03-26 | Graphs – implementation tips | -- |
| 2012-03-28 | NP-completeness | -- |
| 2012-03-30 | Algorithm design techniques | -- |
| 2012-04-02 | Review and tips for the final |