[ Announcements |
Administrative Basics |
Schedule and Homeworks |
Exams |
Grades Database ]
Course Description
This course is about the art of designing efficient
algorithms for a wide range of fundamental computational tasks and
the science of proving the correctness of such algorithms and
formally analyzing their time complexity.
The course will introduce the following basic design paradigms:
divide-and-conquer, greedy algorithms, dynamic programming, amortized
analysis, and randomization. The computational tasks studied will
span several domains. These include sorting and order statistics,
computing with integers and number-theoretic algorithms, algorithms
on graphs, and geometric algorithms.
Writing mathematical proofs will be required throughout this course.
Students are expected to have previous experience with writing
proofs. Taking CS 30
will provide this experience.
Students will be expected to be experienced programmers before
taking this course, so that they are able to reason about
algorithms/code at a high level without seeing actual lines of code in
front of them. Taking the CS
1 – CS 10
sequence will provide this experience.
Announcements
- [May 29] The final exam has been posted. See the bottom of the schedule
table below.
- [May 18] Slides on Fibonacci heaps have been posted. See table below.
- [Apr 10] Details of the exams have just been announced.
- [Apr 9] If you have not done so yet, please send the instructor an
email stating your first and last name (omit middle initials and suffixes)
and a chosen password for this course's grades database.
Administrative Basics
Important! Please also read and familiarize yourself with the
administrative details not covered in the
outline below. Pay special attention to the section that describes
how the honor code applies to this
course; violations of the honor code
will be treated
seriously.
Lectures
|
LSC 205 | 10 hour | Mon-Wed-Fri 10:00-11:05, X-hr Thu 12:00-12:50
|
Instructor
|
Amit Chakrabarti
Sudikoff 107 | 6-1710 |
Office hours: Mon 1:30–2:30, Fri 11:15–12:15, or by appointment
|
Teaching Assistants
|
Hanh Nguyen
Sudikoff 114 |
Office hours: Sun 2:00–4:00, or by appointment
Elaine Levey
Sudikoff 114 |
Office hours: Mon 3:00–5:00, or by appointment
|
Textbook
|
Required:
"Introduction to Algorithms", Third Edition.
Cormen, Leiserson, Rivest, and Stein.
Suggested additional:
"Algorithm Design",
Kleinberg and Tardos.
|
Prerequisites
|
Both CS 10 and CS 30.
The reasons are explained in the Course Description.
You must meet the professor in person to request a prerequisite waiver.
|
Work
|
One homework per week. [20 points]
Two in-class quizzes. [20 points]
Two in-class evening midterms. [30 points]
One take-home final exam. [30 points]
Please take note of the late
homework policy. It will be enforced, strictly.
|
Schedule, Homeworks, Exams
This is a work in progress. The dates for the quizzes, the evening
midterms and due dates for the homework sets and the final exam are now
fixed as shown below. This schedule will be updated frequently. Please
check back often, and please remember to RELOAD to get the latest
schedule.
The schedule is subject to change, with minimal notice. Especially,
greyed-out entries should be considered tentative.
Please be sure to read and understand the Homework Grading Guidelines and the
Late Submission Policy.
Official solutions to homeworks and exams (hard-copy only) will be given
out when graded work is returned.
Lecture Number
and Date |
Textbook
Sections |
Homework
Due |
Topics Covered in
This Lecture |
| |
Week
1 |
1 |
Mar 25 |
— |
— |
Welcome; Administrivia; Historical examples: Euclid, Gauss, Gale-Shapley
|
|
| 2 |
Mar 27 |
2.1, 2.2 |
— |
Basic analysis: bubble sort and insertion sort;
Mathematical induction |
| 3 |
Mar 28 (X-hr) |
2.2, 3.1, 3.2 |
— |
RAM model; Asymptotic notation |
| 4 |
Mar 29 |
2.3 |
— |
Merge sort and analysis; More mathematical induction |
| |
Week
2 |
5 |
Apr 1 |
— |
— |
Divide-and-Conquer; Binary search; Inversions; Majority
|
| 6 |
Apr 3 |
4.2 |
HW1 |
Karatsuba integer multiplication; Strassen matrix multiplication
|
| 7 |
Apr 4 (X-hr) |
4.3–4.6 |
— |
Master theorem; Akra-Bazzi theorem
|
| 8 |
Apr 5 |
9.3 |
— |
Selection
|
| |
Week
3 |
9 |
Apr 8 |
33.4 |
— |
Closest pair
|
| 10 |
Apr 10 |
16.1, 16.2 |
HW2 |
Greedy algorithms: interval selection |
| 11 |
Apr 11 (X-hr) |
— |
— |
Formal proof of correctness for greedy interval selection |
| 12 |
Apr 12 |
22.1 |
— |
Graph, trees, and their representations |
| |
Week
4 |
12 |
Apr 15 |
23.1, 23.2 |
— |
Kruskal MST
[Evening Midterm #1, 5:00–7:00 in LSC 200]
|
| 13 |
Apr 17 |
23.1, 23.2 |
HW3 |
Kruskal proof of correctness; Importance of data structures
|
| |
Apr 18 (X-hr) |
— |
— |
Not used |
Video homework:
Lecture 5 "GRAPH SEARCH & DIJKSTRA'S ALGORITHM"
|
| 14 |
Apr 19 |
22.2, 24.3 |
— |
DFS; BFS; Dijkstra
|
| |
Week
5 |
15 |
Apr 22 |
Ch. 6 |
— |
Heaps; Heap sort; Priority queues
|
| |
Apr 24 |
— |
HW4 |
|
| |
Apr 25 (X-hr) |
— |
— |
[Quiz 1, in class]
|
| 16 |
Apr 26 |
— |
— |
Heap sort; Correctness of Dijkstra
|
| |
Week
6 |
17 |
Apr 29 |
23.2, 24.1 |
— |
Prim MST; Bellman-Ford
|
| 18 |
May 1 |
Ch. 25 |
HW5 |
Dynamic programming: weighted interval selection; Floyd-Warshall
|
| 19 |
May 2 (X-hr) |
15.2, 15.3 |
— |
Matrix chain product
|
| 20 |
May 3 |
15.4 |
— |
Longest common subsequence (LCS)
|
| |
Week
7 |
21 |
May 6 |
7.1 – 7.3 |
— |
Randomization; Quicksort and Selection
[Evening Midterm #2, 5:00–7:00 in LSC 200]
|
| 22 |
May 8 |
9.2 |
HW6 |
Conditional expectation; Analysis of Selection
|
| 23 |
May 9 (X-hr) |
7.4 |
— |
Linearity of expectation; Analysis of Quicksort
|
| 24 |
May 10 |
— |
— |
Min cut; Karger's algorithm
|
| |
Week
8 |
25 |
May 13 |
17.1--17.3 |
— |
Amortized analysis: multi-pop stacks, binary counters
|
| 26 |
May 15 |
19.1--19.3 |
HW7 |
|
| |
May 16 (X-hr) |
— |
— |
[Quiz 2, in class]
|
| 27 |
May 17 |
19.4, 21.1 |
— |
Fibonacci heaps (continued); Union-find; Path compression
|
| |
Week
9 |
28 |
May 20 |
21.2--21.4 |
— |
Analysis of path compression
|
| 29 |
May 22 |
— |
|
Max flow; Ford-Fulkerson
|
| |
May 23 (X-hr) |
— |
— |
Not used
|
| 30 |
May 24 |
— |
HW8 |
Analysis of Ford-Fulkerson; Edmonds-Karp
|
| |
Week
10 |
|
May 27 |
— |
— |
Memorial Day
|
| 31 |
May 29 |
— |
— |
Review and discussion of unresolved Homework problems
|
| Deadline Jun 3 |
Take-home 48-hour final exam, due at 5:00pm sharp
The final exam website is now closed.
|
About the Exams
Quizzes will be held in class. They will be closed-book and
closed-notes. Students must not consult any sources at all when working on a
quiz.
Evening Midterms will be held from 5:00 to 7:00 p.m. on the days
and at the locations marked in the above schedule. These will be open book and
open notes. A student may consult the official textbook, any materials handed
out in class, his or her own notes, and his or her own graded
homework and previous exams/quizzes. No other sources may be consulted. Pay
attention to the honor code.
The Final Exam will be available on this website (login required)
on the last day of classes. It will be a take-home exam and must be submitted
within 48 hours of downloading (very specific instructions will be included in
the exam). This exam will be open book and open notes. A student may consult
the official textbook, any materials handed out in class, his or her
own notes, and his or her own graded homework and previous
exams/quizzes. No other sources may be consulted. Pay attention to the honor code.
Grades Database
If you are a registered student, you may verify your grades as
entered in our database using the form below.
