Algorithms and Data Structures - Spring 2020

Lectures and Material

• Feb 18: Course introduction: course organization and policies; Example of the Fibonacci sequence: a bad algorithm and a good algorithm; implementation-independent behaviors and algorithmic complexity.
  Material: slides used in class
• Feb 20: Complexity under the RAM model. Asymptotic growth of functions: big-O, Omega, and Theta notations.
  Book ref.: CLRS 2.2, 3. Material: slides used in class
• Feb 25: Basic elements for the analysis of algorithms: complexity and correctness of insertion-sort; worst-, best-, and average-case complexity; loop invariants.
  Book ref.: CLRS 2. Material: slides used in class
• Mar 5: Divide and conquer strategy: binary search, merge, merge sort, recursive multiplication, median and k-smallest selection.
  Book ref.: CLRS 9.1, 9.2. Material: slides used in class
• Mar 12: Quick-sort. Heaps and heap-sort.
  Book ref.: CLRS 6.1-4, 7.1-3. Material: slides used in class
• Mar 17: In-class programming assignment.
  a collection of exercises, priority_queue.py
• Mar 24: Elementary data structures and hash tables.
  Book ref.: CLRS 10, 11-11.2,11.4. Material: slides used in class; programming exercise: queue.py
• Apr 7: Binary search trees. Randomized binary search trees.
  Book ref.: CLRS 12. Material: print_binary_tree.py, slides used in class
• April 9: Review or binary trees. Height of a BST in the average case: simulation and visualization.
• Apr 23: Midterm exam.
• Apr 30: Red-Black trees: introduction.
  Book ref.: CLRS 13-13.3. Material: slides used in class
• TBD: Review of BST deletion. Red-black trees: deletion. Exercises. (OPTIONAL)
  Book ref.: CLRS 13.4.
• May 5: B-Trees. Data structures in secondary storage: modeling disk access. Structure, search, and insertion in B-trees. Relation with red-black trees.
  Book ref.: CLRS 18-18.2. Material: slides used in class
Note: Slide sets and other links below are from the last edition of the course.

---

• TBD: Radix-search. Tries, and ternary search tries. Exercises. (OPTIONAL)
  Book ref.: CLRS p.304.
• TBD: Exercises from past exams.
• TBD: Convex hull: ordering the points, analogy with sorting. (OPTIONAL)
  Book ref.: CLRS 33.3
• TBD: Randomized Algorithms: randomized variants of already-seen deterministic algorithms, Monte Carlo and Las Vegas algorithms, examples. (OPTIONAL)
  Book ref.: CLRS 7.3.
• May 7: Graphs: representation and elementary algorithms.
  Book ref.: CLRS 22-22.4. Material: slides used in class; programming exercise: there is an error in this implementation of DFS: bfs_dfs.py. Fix it!
• TBD: Minimal spanning trees; Disjoint sets. (BASICS)
  Book ref.: CLRS 23. Material: slides used in class
• TBD: Dijkstra's Algorithm.
  Book ref.: CLRS 24.3. Material: slides used in class
• TBD: Greedy algorithms: general strategy, activity selection, Huffman codes.
  Book ref.: CLRS 16.2-16.3. Material: slides used in class
• TBD: Dynamic programming: examples, and general strategy.
  Book ref.: CLRS 15.3. Material: slides used in class
• TBD: Basic elements of complexity theory: polynomial-time algorithms and problems; the P complexity class; the NP class; polynomial-time reduction and NP-completeness; satisfiability.
  Book ref.: CLRS 34. Material: slides used in class
• TBD: Exercises.
• TBD: Superficial introduction to string matching: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm. (OPTIONAL)
  Book ref.: CLRS 32-32.1; 32.4.