Lectures

RSA lecture in HTML.

Assignments

The next assignment is the final exam. It will be made available shortly. Prior assignments can also be found on the mailing list archives.

Addresses

Brook Conner, @nyu or @home. His office hourse are 5-6 TW in WWH 501.

Aris Tsirigos, the TA. His office hours are 3:30-5:30 T in WWH 422.

The course mailing list.

G22-1170-001: Fundamental Algorithms

This course is an introduction to the design and implementation of efficient algorithms and data structures. It will cover searching, sorting, collections, graphs, computational geometric, and select numerical algorithms. It will also provide a basic introduction to the detailed analysis of algorithms, covering performance (both running time and memory usage), worst-case analysis, amortized costs, and statistical analysis.

While maintaining mathematical rigor, we will consider algorithms from a software engineering viewpoint - rigorous proofs of capabilities can be a great aid during specification and design of complex software systems. Algorithms and data structures will be placed in an engineering context between full frameworks and small design patterns. Frameworks may be broken down into algorithms and data structures, and algorithms and data structures can be broken down into design patterns. Conversely, patterns can be assembled, producing new algorithms, and algorithms can be assembled, producing new frameworks.

Algorithms are often presented in a widely-known procedural programming language, such as Pascal, but we will not ignore the pragmatics of implementation. In particular, we will note places where particular language functionality (such as polymorphism and garbage collection) can dramatically simplify (or conversely, dramatically complicate) the implementation of a particular algorithm.

Syllabus

Texts

The required textbook for the course is Introduction to Algorithms, 2nd Edition, by Cormen, Lieserson, Rivest, and Stein. Addison Wesley, 2002.

If you feel your finite mathematics may be a little rusty, you should consider the recommended text Concrete Mathematics, by Graham, Knuth, and Patashnik. Addison Wesley, 1994.

Assignments

Expect one written assignment each week. Each assignment will consist of three to five questions. Each question will be a proof of a theorem or corrolary, an explanation of the relative merits of various algorithms, or a brief programming problem.