Fundamental Algorithms

CSCI-GA.1170-001

Summer 2012

Instructor

Aditya Dhananjay

aditya@courant.nyu.edu

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

Recitation Leader

Zhao (Joan) Jin

zj284@nyu.edu

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

Grader

Zhuoheng Yang

zhuoheng.yang@cs.nyu.edu

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:

Download Slides

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.