# CSPP 55001: Algorithms Autumn 2013

announcements | general information | organization | homework

### Announcements

Homework 9 is posted

Problem session: Sunday at 2:00 pm in Ryerson 276

Office hours: Monday 4:00–5:00 pm & 8:30–9:30 pm in Ryerson 162

Textbook: Introduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN 978-0-262-03384-8) = CLRS

The course grade will be determined using the following weights:

• ( 5%) Homework assignments
• (20%) Quizzes
• (25%) Midterm examination
• (50%) Final examination

Homework Collaboration Policy: You are allowed and encouraged to discuss course material and homework assignments with each other, but you must work out and write up the solutions to the homework assignments on your own. Exchanging solutions to homework problems or sharing solutions is strictly prohibited. Solutions to homework problems must reflect YOUR understanding of the ideas and must be YOUR own work. DO NOT COPY a solution from a written source, from the internet, or from another person. Copied solutions obtained from a written source, from the internet, or from another person will receive zero credit.

### Schedule of lectures

October 1
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, sections 4.1–4.2
Review: CLRS chapter 3 (asymptotic notation, common functions); chapter 4, sections 4.3–4.5 (methods of solving recurrences).
October 8
Lecture 2: Quicksort; median and order statistics
Randomized algorithms
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapters 5, 7, and 9
October 15
Lecture 3: Dynamic programming
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 15, sections 15.1–15.4
October 22
Quiz 1
Lecture 4: Dynamic programming
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 15, sections 15.1–15.4
October 29
Quiz 2
Lecture 5: Graph traversal: breadth-first search
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 22, sections 22.1–22.2
November 5
Midterm exam
5:30–7:00 pm in Ryerson 251
Lecture 6: Graph traversal: depth-first search
7:15–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 22, sections 22.3–22.4.
November 12
Lecture 7: Strongly connected components
Shortest paths: Dijkstra's algorithm
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS CLRS chapter 22, section 22.5; chapter 24, section 24.3.
November 19
Lecture 8: Shortest paths: Bellman-Ford algorithm; shortest-paths in DAGs
Minimum spanning trees
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 23; chapter 24, section 24.1–24.2.
November 26
Quiz 3
Lecture 9: NP-complete problems
5:30–8:30 pm in Ryerson 251
December 3
Quiz 4
Lecture 10: Hashing and other topics
5:30–8:30 pm in Ryerson 251
December 10
Final exam
5:30–8:30 pm in Ryerson 251

## Organization

### Staff

• Instructor

Office hours: Monday 7:00 pm to 9:00 pm and by appointment
Office: Ryerson 165A
Email: brady at cs dot uchicago dot edu

• Teaching Assistants:

Pooya Hatami
Email: pooya at cs dot uchicago dot edu
Office hours: Monday 8:30 to 9:30 pm in Ryerson 162

Negar Mirsattari
Email: mirsattari at uchicago dot edu
Office hours: Monday 4:00 to 5:00 pm in Ryerson 162
Online office hours: Sunday at 8:00 pm

### Lectures

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

### Problem session

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

brady at cs dot uchicago dot edu