Fundamental Algorithms

CSCI-GA.1170-001

Summer 2012

**Instructor**

Aditya Dhananjay

Office
Hours: Mondays 7:30pm – 8:30pm at WWH 328

**Recitation
Leader**

Zhao (Joan) Jin

Office Hours: Wednesday 7:00pm – 8:00pm at WWH
328

**Grader**

** **Zhuoheng Yang

Office
Hours: Wednesday 7:00pm – 8:00pm at WWH 328 (Combined office hours for
the grader and recitation leader)

**General
Information**

**Lecture: **Tuesday
6:00pm – 8:20pm at WWH 517

**Recitation: **Thursday
6:00pm – 7:00pm at WWH 517

**Class Mailing List: **All students who register for the class should sign up here.

**Course
Description**

This
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
these solutions.

While
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.

We
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
trees, heaps

-- Algorithmic Techniques: Greedy, divide-and-conquer,
dynamic programming

-- Network Flow: Max flow – min cut,
Ford-Fulkerson algorithm, applications thereof

-- Non-determinism, NP completeness, simple reductions

-- A few special topics

**Course
Materials**

While
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)

**Assignments**

Problem
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.

Each
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.

Finally,
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)

Problem
Set 2: Download here.
(Due June 7, 2012)

Problem
Set 3: Download here.
(Due June 14, 2012)

Problem
Set 4: Download here.
(Due June 21, 2012)

Problem
Set 5/6: Download here.
(Due July 5, 2012)

Problem
Set 7/8: Download here.
(Due July 17, 2012)

Problem
Set 9 : Download here.
(Due July 24, 2012)

Problem
Set 10: Download here.
(Due July 31, 2012)

É

**Supplementary
Notes**

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
below:

**Exams**

Midterm: June 26, 2012. 6pm at WWH 517

Finals:
August 7, 2012. 6pm at WWH 517

**Grade**

The
grade is determined using the following criteria:

--
Problem sets (35%)

--
Midterm (15%)

--
Finals (40%)

--
Class Participation (10%)

**Cheating**

You
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.