Fundamental Algorithms CSCI-GA.1170.001 -- Spring 2018

Final Exam

May 14, 5:10 p.m. - 7:00 p.m. Silver 405 (our regular classroom)

The Final Exam will be cumulative -- it will include material from the entire course. No notes, nor calculators, will be allowed.

More information will be placed here as the date approaches.

There will be NO office hours on Tuesday, May 8

Ojas will have special office hours Sunday, May 13, 1:00 p.m. - 3:00 p.m. in wwh 1302.

There will be special office hours, May 14, 10:00 a.m. - 11:00 a.m. in room wwh705.

There will be special office hours, May 11, 1:45 a.m. - 2:45 p.m. in room wwh829.

The exam will include something (not saying how much!) on: (i) Sorting (ii) NP (iii) A mathematical argument underlying an algorithm.

The Agarwal, Kayal, Saxena algorithm can be used -- but you need to say explicitly what it does and how it is used.

Here is an old final exam postscript LaTeX pdf and its solutions postscript LaTeX pdf

Spencer Award

The Spencer Award is given to a student whose enthusiasm and energy make NYU such an exciting place to be.

This year's winner is Yixiang Luo. Congratulations Yixiang!


Click here postscript LaTeX pdf for syllabus and more info.

When and Where

Monday, 5:10-7:00 p.m., Silver 405


Prof. Joel Spencer

Office: ciww 829

Email: {lowercaselastname}

Office Hours: Tuesday 9:30-11:00 a.m., ciww 829


Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein


Ojas Deshpande. Thursday 8:10-9:00 p.m., ciww 109

Ojas Office Hours: Wednesday, 2:30-4:00, ciww412


Project Special Rules: You may work in a group with at most 3 students and you may (unlike the assignments) hand in a single report for all of you. The report will NOT get a grade. A bad report cannot hurt your final grade, a good report can help. No specific percentages are given to the effect of the report on your grade. But please note that this is not considered a major project and you should limit the amount of time you devote to it.

You will NOT be judged on the quality of your programming. (But, of course, if your program doesn't work that is no good!) You WILL be judged on the quality of the display of your data. Make sure that any displays of data -- e.g., graphs -- are clearly and fully explained. Make sure you describe clearly just what you did -- while you can append the program this is NOT enough!

This OPTIONAL project is due on April 30. Electronic submission directly to Prof. Spencer is prefered, but hard copy submission is also acceptible.

Topics: You need pick ONE of the following topics.

Quicksort postscript LaTeX pdf

Hashing postscript LaTeX pdf

Games (April 9 class) postscript LaTeX pdf

Basic Information

There will be a final exam and a midterm.

There will be assignments to be handed in pretty much every week.

The assignments to be submitted at the start of the next Recitation Section.

Mailing List

All students registered for this course have been added to the Google Group: *Csci_ga_1170_001_sp18*.

This is a private group meant only for discussions related to the class.

You can use the group email address to easily share content but refrain from spamming everyone.

If you haven't been added to the group, please send an email to and we can add you to the group.

Midterm Exam

Here is the exam postscript LaTeX pdf and its solutions postscript LaTeX pdf


As a courtesy assignments are often posted on Sunday or Monday before class.

HOWEVER, please check back on this website on Tuesday.

Occasionally there will be changes in which case the assignment will be marked revised.

Assignment 1 (This is NOT to be submitted!) postscript LaTeX pdf

Assignment 2, Due February 1 postscript LaTeX pdf

Assignment 3, Due February 8 postscript LaTeX pdf

Assignment 4, Due February 15 postscript LaTeX pdf

Just for Fun postscript LaTeX pdf

Assignment 5, Due March 1 postscript LaTeX pdf

Assignment 6, Due March 8 postscript LaTeX pdf

Assignment 7, Due March 22 postscript LaTeX pdf

Assignment 8, Due April 5 postscript LaTeX pdf

Assignment 9, Due April 12 postscript LaTeX pdf FigA pdf FigB pdf FigC pdf

Assignment 10, Due April 19 postscript LaTeX pdf

Assignment 11, Due April 26 postscript LaTeX pdf

Assignment 12, Due May 3 postscript LaTeX pdf

Assignment 13, Not to be Submitted postscript LaTeX pdf


Assignment 1 (This is NOT to be submitted!) postscript LaTeX pdf

Assignment 2 postscript LaTeX pdf

Assignment 3 postscript LaTeX pdf

Assignment 4 postscript LaTeX pdf

Assignment 5 postscript LaTeX pdf

Assignment 6 postscript LaTeX pdf

Assignment 7 postscript LaTeX pdf

Assignment 8 postscript LaTeX pdf

Assignment 9 postscript LaTeX pdf

Assignment 10 postscript LaTeX pdf

Assignment 11 postscript LaTeX pdf

Assignment 12 postscript LaTeX pdf

Assignment 13 postscript LaTeX pdf


Send me an email: {lowercaselastname}


Karatsuba's Algorithm (Feb 12 class) postscript LaTeX pdf

Rod Cutting (Mar 5 class) postscript LaTeX pdf

Why is it called Dynamic Programming? strangeanswer

Text Alignment (April 2 class) postscript LaTeX pdf

Union Find (April 16 class) postscript LaTeX pdf

Euclid Algorithm (April 23 class) postscript LaTeX pdf

Just In Case

academic integrity policies