This schedule is tentative, and will be updated as the semester progresses.

Week 1

• Topic: Class intro. Warmup with searching (linear and binary) and sorting (bubble sort, insertion sort, selection sort). Analysis: The RAM model. Asymptotic analysis and asymptotic notation. Case studies.
  Notes: L-intro | ex-bubblesort |  ex-selsort |  L-analysis | ex-inssort | ex-analysis1 |  ex-analysis2
• Slides: S-intro.pdf | S-asymptotic.pdf
• Reading Assignment: CLRS 1, 2, 3
• Lab: Lab1 (big-O)

Week 2

• Topic: Summations and recurrence relations. Mergesort.
  Notes: L-summations | ex-sum | L-recurrences | ex-rec1 | ex-rec2 | ex-rec3 | ex-rec4 | ex-rec1-sol
• Reading Assignment: CLRS A, 2.3, 4.4
• Lab: Lab2 (recurrences)

Week 3

• Topic:  More recurrences.  Heaps and heapsort.
  Notes: L-heaps | ex-heaps
• Slides: S-heaps.pdf
• Reading Assignment: CLRS 6
• Lab:  Lab3 (heaps)

Week 4

• Topic: Quicksort.
  Sorting lower bound and sorting in linear time.
  Notes: L-quicksort | ex-quicksort | L-sortlb | ex-linearsort | L-linsort
• Reading Assignment: CLRS 7, 8
• Lab:  Lab4 (quicksort)

Week 5

• Topic: Selection. Divide-and-conquer algorithms (Strassen, maximum sub-array)
  Notes: L-selection| ex-selection |  L-divideandconquer| ex-maxps
• Reading Assignment: CLRS 9, 4.1, 4.2
• Lab: Lab5 (selection)

Week 6

• Topic: Dynamic programming.
  Notes: L-dynprogr | ex-rod
• Reading Assignment: CLRS 15.1
• Lab:  Lab6  (dynamic programming)

Week 7

• Topic: Dynamic programming and greedy algorithms.
  Notes: L-LCS | L-weightedinterval | L-greedy
• Reading Assignment: CLRS 15.4, 16.1, 16.2
• Lab: Lab7 (more dynamic programming and greedy)

Week 8

• Topic: Graphs: BFS, DFS.
  Notes: L-graphbasics | L-bfsdfs | L-basicproblems | L-kevinbacon
• Reading Assignment: CLRS 22.1 – 22.3
  Internet: Lecture slides by Kevin Wayne: graphs-basics (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/03Graphs.pdf)
• Lab:  Lab8 (graphs)

Week 9

• Topic: Graphs: Topological sort. Strongly connected components.
  Notes: L-topsort | L-scc
• Reading Assignment: CLRS 22.4, 22.5
• Lab:  Lab9 (graphs)

Week 10

• Topic: Graphs: Minimum spanning tree (Kruskal and Prim’s algorithms). Union-find structure.
  Notes: L-mst
• Reading Assignment: CLRS 23
  Internet: Lecture slides greedy-algorithms (source:http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsII.pdf) | Kruskal demo demo-kruskal (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04DemoKruskal.pdf) | Prim demo demo-prim (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04DemoPrim.pdf) by Kevin Wayne.
• Lab:  Lab10 (graphs)

Week 11

• Topic: Graphs: Single-source shortest paths (Bellman-Ford and Dijkstra’s algorithms).
  Notes: L-shpaths
• Reading Assignment:  CLRS 24.1-24.3
  Dijkstra demo by Kevin Wayne demo-dijkstra (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04DemoDijkstra.pdf)
• Lab:  Lab11 (graphs)

Week 12

• Topic: Last class: Crash course into NP-completeness.
  Questions from technical interviews.
• Reading Assignment: (CLRS 34)
  Internet: Lecture slides by Kevin Wayne intractability (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/08IntractabilityI.pdf)

Exam 2 will be in-class,  on (check final exam date in polaris).