Algorithms and Data Structures - Spring 2016

Lectures and Material

• Feb 22: 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 24: 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
• TBD: Representing numbers: space complexity. Adding and multiplying numbers. The simple algorithms and their analysis. Initial idea for a better multiplication algorithm. (OPTIONAL)
• Feb 29: 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 9: Divide and conquer strategy: binary search, merge, merge sort, recursive multiplication, median and k-smallest selection.
  Book ref.: DPV 2.1, 2.3, 2.4; CLRS 9.1, 9.2. Material: slides used in class
• Mar 14: Quick-sort. Heaps and heap-sort.
  Book ref.: CLRS 6.1-4, 7.1-3. Material: slides used in class
• Mar 16: Exercises from past exams.
• Mar 23: Elementary data structures and hash tables.
  Book ref.: CLRS 10, 11-11.2,11.4. Material: slides used in class
• TBD: General divide and conquer strategy and complexity: recurrences. (OPTIONAL)
  Book ref.: CLRS 4.3, 4.4; DPV 2.2.
• Apr 4: Binary search trees. Randomized binary search trees.
  Book ref.: CLRS 12. Material: slides used in class
• Apr 6: Midterm exam.
• Apr 11: Review or binary trees. Height of a BST in the average case: simulation and visualization.
  Material: print_binary_tree.py
• Apr 18: Red-Black trees: introduction.
  Book ref.: CLRS 13-13.3. Material: slides used in class
• Apr 18: Review of BST deletion. Red-black trees: deletion. Exercises. (OPTIONAL)
  Book ref.: CLRS 13.4. Material: slides used in class
• Apr 20: Exercises from past exams.
• Apr 25: 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
• Apr 27: Radix-search. Tries, and ternary search tries. Exercises.
  Book ref.: CLRS p.304. Material: slides used in class
• May 2: 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 4: Graphs: representation and elementary algorithms.
  Book ref.: CLRS 22-22.4. Material: slides used in class
• May 9: Minimal spanning trees; Disjoint sets. (BASICS)
  Book ref.: CLRS 23. Material: slides used in class
• May 11: Dijkstra's Algorithm.
  Book ref.: CLRS 24.3. Material: slides used in class
• May 18: Greedy algorithms: general strategy, activity selection, Huffman codes.
  Book ref.: CLRS 16.2-16.3. Material: slides used in class
• TBD: Exercises.
• May 23: Dynamic programming: examples, and general strategy.
  Book ref.: CLRS 15.3. Material: slides used in class
• May 25: 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: Superficial introduction to string matching: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm. (OPTIONAL)
  Book ref.: CLRS 32-32.1; 32.4.