CSCI-GA.1170-003 Basic Algorithms , Spring 2013

CSCI-UA.0310-001 Basic Algorithms , Spring 2013

Lecturer: Esther Ezra , my first name at cs.nyu.edu, (212) 998-4859, room 416, WWH. Office hour: Wednesday 3:15--4:15PM
Meeting Time/Place: M/W 2:00--3:15PM, WWH 202 WWH.
Recitation Time/Place: Thur 3:30--4:45PM, WWH 202, WWH.
Graders: Wen Xing .
Midterm: TBA Final: TBA
Mailing list: To subscribe to the class list follow instructions at

http://www.cs.nyu.edu/mailman/listinfo/csci_ua_0310_003_sp13

To post a message to all the list members, send email to csci_ua_0310_003_sp13@cs.nyu.edu. Please, post only messages interesting to everybody taking the class. Specific class-related questions and most of your other correspondence should be directed to the instructor.
Course Homepage: http://cs.nyu.edu/courses/spring13/CSCI-UA.0310-003/index.html

Brief Course Description:

This is an introductory course in algorithms. This course covers the design and analysis of combinatorial algorithms. The curriculum is concept-based and emphasizes the art of problem-solving. The course features weekly exercises designed to strengthen conceptual understanding and problem solving skills. Students are presumed to have adequate programming skills and to have a solid understanding of basic data structures and their implementation in the programming languages of their choice. Although some mathematical sophistication would be helpful for this course, the necessary mathematics is contained within the curriculum. Because of the emphasis on problem solving, students are expected to attend the Thursday recitation sessions. Be sure that you register for the recitation (section 003) as well as the class (section 001/002).

Course Topics

Algorithmic analysis: Correctness. Worst-case running time asymptotic analysis. Big Oh notation. CLRS, chaps. 1-3. Siegel, chap. 1, chaps 2 through section 2.3.
Divide-and-conquer Recurrence equations. CLRS chap. 4. Siegel, section 2.4 pp. 52-66.
Sorting algorithms: N² sorts, Heapsort, Mergesort, Quicksort, CountingSort, Radix sort. Lower bound. CLRS chaps. 6-8. Siegel, chap. 7.
Sets: Lists. Hash tables. Binary search trees. 2-3-trees/B-trees. CLRS chap. 10, 11, 12, 18. Siegel Chapter 6 through 6.4.7.
Directed graphs: Implementation. Depth-first search. DAGS, Topological sort. Shortest paths. All pairs shortest paths CLRS chaps. 22,24,25. Siegel, chaps. 7, 8 through 8.4. 8.3.6 is optional.
Undirected graphs: Minimum spanning tree. Max flow, Union-find algorithm. CLRS chaps. 21, 23. Siegel, sections 8.6 and 9.4
Algorithmic techniques: Dynamic programming.

Textbook:

1. An Introduction to Algorithms: their methods and madness, by A.R. Siegel, available at NYU Copy Central 547 LaGuardia Place.

2. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press.
You can get either the THIRD EDITION or the SECOND EDITION.

Grading:

There will be one in-class midterm and a final exam, in addition to approximately weekly homework assignments. Tentative grade split is 30% homework, 30% midterm and 40% final exam.

Students can increase their total grade by up to 5% by doing well in self-grading their homework, as explained in class. Please make sure you make a copy of your homework before handing it in.

Homework:

There will be approximately 12 written homework assignments. Some of the homework exercises will be routine, but others will be more challenging. I do not expect you to solve all of the homework problems, but I hope that you will benefit from working on the more difficult ones. Homework will be assigned on Monday, and will be due the following Monday. No late homework will be accepted. Self-graded homework will be due one week from the assignment due date. It will not be returned to the students.

An advice about the homework assignments:

Start early. Most problems will not be hard, but others will be. Such more difficult problems are not typically solved in one sitting. Start early and let the ideas come to you over the course of a few days.
Be rigorous. Each problem has a (sometimes unwritten) requirement that you prove your algorithm correct and analyze its running time. To obtain full credit for a problem, it is necessary to fulfill these requirements. We expect real proofs and real analysis, not "proof by hand waving."
Be concise. Express your algorithms at the proper level of detail. Give enough details to clearly present your solution, but not so many that the main ideas are obscured. English is often a good way to express an algorithm; pseudocode is good for communicating complex control structure.
Collaboration? You are encouraged to solve all the homework questions on your own, but are permitted to brainstorm difficult problems in small groups, as long as each of you writes the solutions individually and honestly acknowledges the cooperation. Needless to say, if you work with others but never come up with the solution on your own, you may do OK in the homework component of your grade, but you will suffer on exams, so be careful.