Syllabus Help Center Learn more.

Note: the syllabus may undergo minor revisions throughout the course.

Abbreviations in suggested readings refer to the following textbooks:
  • CLRS - Cormen, Leiserson, Rivest, and Stein, Introdution to Algorithms (3rd edition)
  • DPV - Dasgupta, Papadimitriou, and Vazirani, Algorithms
  • KT - Kleinberg and Tardos, Algorithm Design
  • SW - Sedgewick and Wayne, Algorithms (4th edition)

Week 1 (May 5-11)


Topics

  • Introduction
  • Merge Sort
  • Asymptotic Notation
  • Guiding Principles of Algorithm Analysis
  • Divide & Conquer Algorithms


Homework

  • Due May 18:
  • Problem Set #1: Divide & Conquer / Asymptotic Analysis
  • Programming Assignment #1: Counting Inversions!


Suggested Readings:

  • CLRS: Chapter 2, 3, and 4 (through Section 4.2), and Sections 28.1 and 33.4
  • DPV: Sections 0.3, 2.1, 2.3, 2.5
  • KT: Sections 2.1, 2.2, 2.4, 5.1, and 5.3-5.5
  • SW: Sections 1.4 and 2.2

Week 2 (May 12-18)


Topics

  • Master Method
  • QuickSort


Homework

  • Due May 25:
  • Problem Set #2: QuickSort and the Master Method
  • Programming Assignment #2: Counting Comparisons in QuickSort


Suggested Readings:

  • CLRS Chapter 4 (Sections 4-6) and Chapter 7
  • DPV Section 2.2
  • KT Sections 5.2 and 13.5
  • SW Section 2.3

Week 3 (May 19-25)


Topics

  • Final Thoughts on Sorting & Searching
  • Introduction to Graph Algorithms : Graph Representations & Mininum Cuts in Graphs


Homework

  • Due June 1
  • Problem Set #3: Randomized Selection & Minimum Cuts in Graphs
  • Programming Assignment #3: Karger's Minimum Cut Algorithm


Suggested Readings:

  • CLRS Chapter 9, 22 (Only 22.1)
  • DPV Chapter 3 (only 3.1)
  • KT Chapter 13, Sections 13.2,13.5
  • SW Chapter 4, Section 4.1

Week 4 (May 26-June 1)


Topics

  • Graph Search: Breadth-First Search, Depth-First Search
  • Applications: Topological Sort, Connected Components


Homework

  • Due June 8
  • Problem Set #4: Graphs, BFS, DFS, Topological Sort
  • Programming Assignment #4: Computing SCCs


Suggested Readings:

  • CLRS Chapter 22
  • DPV Chapter 3
  • KT Chapter 3, Section 3.5, 3.6
  • SW Chapter 4, Section 4.1,4.2

Week 5 (June 2-June 8)


Topics

  • Dijkstra's Shortest-Path Algorithm
  • Data structures and how to use them
  • Heaps
  • Binary Search Trees
  • Balanced BSTs


Homework

  • Due June 15
  • Problem Set #5: Dijkstra, Heaps, Search Trees
  • Programming Assignment #5: Dijkstra's Algorithm


Suggested Readings:

  • CLRS Chapter 6,11,12,13 24 (Sections 3,4)
  • DPV Section 1.5
  • KT Section 4.4
  • SW Section 3.3, 3.4, 4.4

Week 6 (June 9-15)


Topics

  • Hash Tables: Applications and Implementation
  • Bloom Filters


Homework

  • Due June 22
  • Problem Set #6: Hashing, Bloom Filters
  • Programming Assignment #6: Data Structure Applications


Suggested Readings:

  • CLRS Chapter 11
  • KT Chapter 13 (Section 13.6)
  • SW Section 3.5

Final Exam (June 16-29)

Created Sun 11 Mar 2012 9:18 PM CET
Last Modified Sun 20 Apr 2014 6:49 PM CEST