Algorithms and Data Structures - Spring 2021

Lectures and Material

• 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
• 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
• 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
• 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, merge.py, merge_sort.py
• Quick-sort. Heaps and heap-sort.
  Book ref.: CLRS 6.1-4, 7.1-3. Material: slides used in class
• Elementary data structures and hash tables.
  Book ref.: CLRS 10, 11-11.2,11.4. Material: slides used in class; examples: stack.py, queue.py, list.py, list2.py
• Binary search trees. Randomized binary search trees.
  Book ref.: CLRS 12. Material: print_binary_tree.py, bst.py, slides used in class
• Review or binary trees. Height of a BST in the average case: simulation and visualization.
• Midterm exam.
• Red-Black trees: introduction.
  Book ref.: CLRS 13-13.3. Material: slides used in class
• Review of BST deletion. Red-black trees: deletion. Exercises. (OPTIONAL)
  Book ref.: CLRS 13.4.
• B-Trees. Data structures in secondary storage: modeling disk access. Structure, search, and insertion in B-trees. Relation with red-black trees. (OPTIONAL)
  Book ref.: CLRS 18-18.2. Material: slides used in class
• Radix-search. Tries, and ternary search tries. Exercises. (OPTIONAL)
  Book ref.: CLRS p.304.
• Exercises from past exams.
• Convex hull: ordering the points, analogy with sorting. (OPTIONAL)
  Book ref.: CLRS 33.3
• Randomized Algorithms: randomized variants of already-seen deterministic algorithms, Monte Carlo and Las Vegas algorithms, examples. (OPTIONAL)
  Book ref.: CLRS 7.3.
• 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!
• Minimal spanning trees; Disjoint sets. (OPTIONAL)
  Book ref.: CLRS 23. Material: slides used in class
• Dijkstra's Algorithm.
  Book ref.: CLRS 24.3. Material: slides used in class
• Greedy algorithms: general strategy, activity selection, Huffman codes.
  Book ref.: CLRS 16.2-16.3. Material: slides used in class
• Dynamic programming: examples, and general strategy.
  Book ref.: CLRS 15.3. Material: slides used in class
• 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
• Exercises.