| Instructor: | Mark Zhandry | |||||||||
| Course Assistants: | Tarun Singh Jun Yu | |||||||||
| Office Hours: |
| |||||||||
| Contact: | cs161-summer2012-staff@lists.stanford.edu | |||||||||
| Piazza: | Piazza for CS 161 | |||||||||
| Lectures: | MWF 2:15-3:30 at Skilling Auditorium | |||||||||
| Textbook: | Algorithm Design by Kleinberg & Tardos | |||||||||
| Important Dates: | First Day of Class: Monday, June 25th Midterm: Wednesday, July 25th in class Last Day of Class: Wednesday, August 15th Final Exam: Friday, August 17th 12:15-3:15PM. Location: Skilling Auditorium |
| Week | Lecture | Date | Topic | Details | Pages | Homework |
|---|---|---|---|---|---|---|
| 1 | 1 | June 25 | Intro/Big Oh | 29-42 | ||
| 2 | June 27 | Data Structures I | Lists, Stacks, Queues, Hash Tables | N/A | HW 1 out | |
| 3 | June 29 | Data Structures II | BSTs, Self-Balancing Trees, Priority Queues | N/A | ||
| 2 | 4 | July 2 | Graph Search I | BFS, DFS, Undirected Connectivity | 73-94 | |
| July 4 | Holiday | HW 2 out | ||||
| 5 | July 6 | Graph Search II | Directed Connectivity, Topological Sorting | 97-104 | HW 1 due | |
| 3 | 6 | July 9 | Greedy Algorithms I | Dijsktra | 137-142 | |
| 7 | July 11 | Greedy Algorithms II | MSTs | 116-157 | HW 3 out | |
| 8 | July 13 | Greedy Algorithms III | More MSTs, Interval Scheduling | HW 2 due | ||
| 4 | 9 | July 16 | Greedy Algorithms IV | Huffman Encoding, Set Cover | 161-177 | |
| 10 | July 18 | Divide & Conquer I | Recurrences, (Matrix) Multiplication, Master Method | 231-234 | ||
| 11 | July 20 | Divide & Conquer II | Merge Sort, Quick Sort, Median | 210-220 | HW 3 due | |
| 5 | 12 | July 23 | Divide & Conquer III | FFT | 234-242 | |
| July 25 | Midterm | In Class | HW 4 out | |||
| 13 | July 27 | Divide & Conquer IV | FFT continued, Multiplication revisited | |||
| 6 | 14 | July 30 | Dynamic Programming I | Weighted Interval Scheduling | 251-260 | |
| 15 | Aug 1 | Dynamic Programming II | Sequence Alignment | 278-284 | HW 5 out | |
| 16 | Aug 3 | Dynamic Programming III | All Pairs Shortest Paths, TSP | 290-307 | HW 4 due | |
| 7 | 17 | Aug 6 | Linear Programming I | Flows | 337-357 | |
| 18 | Aug 8 | Linear Programming II | Reductions | N/A | ||
| 19 | Aug 10 | NP-Complete I | Definitions, SAT, 3SAT | 451-495 | HW 5 due | |
| 8 | 20 | Aug 13 | NP-Complete II | More NP-Complete Problems, Coping with NP-Complete | 499-649 | |
| 21 | Aug 15 | Beyond CS 161 | N/A | |||
| Aug 17 | Final Exam | 12:15-3:15PM, Skilling Auditorium |
This course uses Piazza, which is the main form of communication regarding the class. If you have any questions that may be of interest to other students, please post them on Piazza. The staff checks Piazza regularly, and other students can answer your questions as well. Please do not post any answers to homework problems until solutions have been released.
If your question is personal in nature or of no interest to other students, you can use the staff email: cs161-summer2012-staff@lists.stanford.edu. If you choose to email the staff, please use this address instead of emailing us directly.
There are a total of five homework assignments. Homework assignments will be available on this website each Wednesday, and are due by the start of class at 2:15PM on the following Friday. Exceptions: No homework is due the week of the midterm or the last week of classes.
Late Policy: Every student is allowed one extension of up to 72 hours. In other words, for exactly one homework assignment, you may choose to turn your solutions in by the start of class at 2:15PM on the Monday after the homework was due. Outside of this extension, no late homeworks will be accepted.
Collaboration: You may work on homeworks in groups of up to three students. However, every student must write up their own solutions in their own words. If you choose to collaborate, put the names and Stanford ID numbers of your collaborators on your submission.
Submitting: You have three options for submitting your homework solutions: in class, during office hours, or by emailing cs161-summer2012-submissions@lists.stanford.edu.
Requirements for all homework submissions: Your name and Stanford ID number must be at the top of the first page of your solutions. In addition, all answers to problems and subproblems must be in order.
Requirements for electronic submissions: If you submit an electronic copy of your solutions, it must be typed, preferably in LaTex. Scans of handwritten work will not be accepted. Exception: we understand that many SCPD students cannot make it to class or office hours to turn in their homework physically, so for SCPD students only, emailing a scan of your homework solutions is acceptable as long as we can read it.
Requirements for paper submissions: If you submit a physical copy of your solutions, it is still encouraged but not required that you type up your solutions in LaTex. However, if you write your solutions by hand, your handwriting must be legible. Further, all physical submissions must be stapled as a single document (no paper clips, binder clips, or loose pages).
Submissions failing to meet the criteria above risk receiving no credit.
Regrades: Regrade requests must be made within one week of the homework being returned, with a written explanation. We reserve the right to regrade the entire assignment, which could potentially result in a lower score than the original.
There is one midterm and one final exam. The midterm will be held in class on Wednsday, July 25, and the final will be held on Friday, August 17 from 12:15-3:15PM in Skilling Auditorium. If you have any conflicts with the midterm, let the staff know by the end of the second week of classes, and special arrangements can be made. All students must be present for the final exam.
Exams will be open-book, open-notes, with questions similar in style to the homework assignments.
Grades will be assigned as follows:
| Homeworks: | 50% |
| Midterm: | 20% |
| Final: | 30% |