CSPP 55001: Algorithms
Autumn 2011

Announcements

Dynamic programming practice problems are posted

Final exam is Wednesday December 7

Problem sessions: Saturday December 3 at 2:00 pm in Ryerson 276
                              Sunday December 4 at 2:00 pm in Ryerson 276
                              Monday December 5 at 8:30 pm in Ryerson 276

Office hours: Monday December 5 6:30 to 7:30 pm in Ryerson 162
                       Tuesday December 6 1:30 to 2:30 pm in Ryerson 162
                       Tuesday December 6 4:30 to 5:30 pm in Ryerson 162

The course grade will be determined using the following weights:

• ( 5%) Homework assignments
• (20%) Quizzes: October 19, October 26, November 16, November 30
• (25%) Midterm examination: November 2
• (50%) Final examination: December 7

Schedule of lectures

September 28

Lecture 1: Analysis of algorithms: insertion sort and merge sort
Divide-and-conquer technique

5:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapters 1 and 2; chapter 4, section 4.3

October 5

Lecture 2: Quicksort and heapsort

5:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapters 6 and 7

October 12

Lecture 3: Heapsort; Lower bounds for comparison-based sorting

Dynamic programming I

5:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapters 6, 8, and 15

October 19

Quiz 1

Lecture 4: Dynamic programming II

5:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapter 15

October 26

Quiz 2

Lecture 5: Graph representations; Breadth-first search

Order statistics

5:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapter 22, sections 22.1–22.3; chapter 9

November 2

Midterm exam

5:30–7:15 pm in Ryerson 251

Lecture 6: Graph traversal: Breadth-first search

7:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapter 22

November 9

Lecture 7: Graph traversal; Depth-first search

Shortest paths: Dijkstra's algorithm

5:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapter 24

November 16

Quiz 3

Lecture 8: Shortest paths: Bellman-Ford algorithm

DAG shortest paths

5:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapter 24

November 19

Lecture 9: Minimum spanning trees

10:00 am–1:00 pm in Ryerson 251

Reading assignment: CLRS chapter 23

November 30

Quiz 4

Lecture 10: NP-complete problems

5:30–8:30 pm in Ryerson 251

Reading assignment: CLRS chapter 34, section 34.5

December 7

Final exam

5:30–8:30 pm in Ryerson 251

---

Organization

Staff

• Instructor
  

  Gerry Brady
  Office hours: Tuesday 6:00–9:00 pm
  Office: Ryerson 165A
  Email: brady at cs dot uchicago dot edu

• Teaching Assistants:
  

  Tatiana Orlova
  Email: orlova at cs dot uchicago dot edu
  Office hours: Tuesday 4:30–5:30 pm Ryerson 162
  

  Behnam Tavakoli
  Email: btavakoli at ttic dot edu
  Office hours: Tuesday 1:30–2:30 pm
  

  Jian Yao
  Email: yaojian at ttic dot edu
  Office hours: Monday 8:00 pm Ryerson 162
  
  

Lectures

• Wednesday 5:30–8:30 pm in Ryerson 251

Problem sessions

• Saturday 2:00–4:00 pm in Ryerson 276

• Sunday 2:00–4:00 pm in Ryerson 276

---

brady at cs dot uchicago dot edu