Hours: Mondays 7:30pm – 8:30pm at WWH 328
Zhao (Joan) Jin
Office Hours: Wednesday 7:00pm – 8:00pm at WWH
Hours: Wednesday 7:00pm – 8:00pm at WWH 328 (Combined office hours for
the grader and recitation leader)
6:00pm – 8:20pm at WWH 517
6:00pm – 7:00pm at WWH 517
Class Mailing List: All students who register for the class should sign up here.
course is an introductory course for the design and analysis of efficient
algorithms. Students who complete the course will have demonstrated the ability
to: a) argue about the correctness and asymptotic running time of a given
algorithm, b) understand important data structures and algorithmic techniques
used to solve problems, c) apply learned concepts to design solutions to
real-world problems, and d) understand space-time tradeoffs while designing
this is a graduate level course, I strongly encourage interested undergrads to
contact me. Most topics will be covered from the basics, including a review of
the required knowledge on data structures. Please speak with me before
enrolling for the class.
will visit many topics, which include:
-- Algorithmic analysis: Correctness, asymptotic
analysis, recurrence relations, master theorem
-- Sorting: Bubble sort, merge sort, quick sort, radix
sort, heap sort
-- Graphs: Traversal, search, connectivity,
topological ordering, spanning trees, shortest paths, DAGs,
-- Matching, Gale-Shapely Algorithm
-- Trees: Binary search trees, 2-3 trees, Red-black
-- Algorithmic Techniques: Greedy, divide-and-conquer,
-- Network Flow: Max flow – min cut,
Ford-Fulkerson algorithm, applications thereof
-- Non-determinism, NP completeness, simple reductions
-- A few special topics
there isn’t any required textbook, the following are good resources:
“Algorithm Design” by Jon Kleinberg and Eva Tardos
“Introduction to Algorithms” by Cormen, Leiserson, Rivest, and Stein
“An Introduction to Algorithms: Their Methods and Madness” by Alan Seigel (available at the NYU copy shop)
sets should be submitted in class at the beginning of each lecture. If you prefer
to submit electronically, please email them to the grader and the instructor in
PDF format only, before
6:00pm on the due date. Late homeworks are not accepted without prior instructor
approval. If you choose to collaborate with other students, please write all
their names in a list of collaborators on your submitted homeworks.
problem set will consist of a varying number of problems, depending on the
difficulty level. We might also include a few problems for extra credit. And for fun.
please make sure that your answers are legible and clear. We will grade you on
what you write – and not what you meant to write. Much to my dismay, our grader
isn’t a mind reader.
Problem Set 1: Download here. (Due
May 29, 2012)
Set 2: Download here.
(Due June 7, 2012)
Set 3: Download here.
(Due June 14, 2012)
Set 4: Download here.
(Due June 21, 2012)
Set 5/6: Download here.
(Due July 5, 2012)
Set 7/8: Download here.
(Due July 17, 2012)
Set 9 : Download here.
(Due July 24, 2012)
Set 10: Download here.
(Due July 31, 2012)
In the classroom, I will use a combination of slides
and the blackboard. The slides provide just an outline, and therefore shouldn’t
be considered to be reading material. However, since some students find it
useful to have print outs of the slides in the classroom, I’ll try to post the
updated slides the day before the lecture. I will not be posting separate
slides for each lecture; you can find the consolidated slides for all lectures
Midterm: June 26, 2012. 6pm at WWH 517
August 7, 2012. 6pm at WWH 517
grade is determined using the following criteria:
Problem sets (35%)
Class Participation (10%)
may discuss any of the assignments with your classmates, but all work for all assignments
must be entirely
your own. Any sharing or copying of assignments will be considered cheating.
Solutions copied from the Internet and solution books are also considered
cheating. By the rules of the Graduate School of Arts and Sciences, I am
required to report any incidents of cheating to the department. My policy is
that the first incident of cheating will result in the student(s) getting an ‘F’ for the course. The second incident, by GSAS rules,
will result in expulsion from the university.