Basic Algorithms -- Spring 2021 -- CSCI-UA.0310-005/6


Final Exam

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

The FINAL EXAM will be May, 14, 2021, 8:00am-9:50am ONLINE (Note: New York Time!!) Like the midterm, it will be open book and open notes.

It will be cumulative, covering the entire term, with somewhat more emphasis on material after the midterm. There will be (tentatively) 11 problems for a total of 155 points. There will be at least one question on MST, at least on on recursion, at least one on the P,NP chapter, at least one of Number Theory.

Meeting ID 94330532421 -- please log in a few minutes before the exam!

FINAL EXAM OFFICE HOURS

Ben Jakubonski Final Exam Office Hours: Wednesday, May 12th from 8:00-9:15AM.

Jianyu Zhang Final Exam Office Hours Thursday, May 13th from 4:15 AM - 5:30AM (NYC time!).

Prof Spencer: Final Exam Office Hours, Thursday, May 13 from 8:00- 9:15 AM, meetingID 94330532421

Optional Project

All students are invited to try their hand on an OPTIONAL project, which includes creating a program. Here are the general rules: postscript LaTeX pdf

Here is a project on Game Analysis postscript LaTeX pdf

Here is a project on QuickSort variants postscript LaTeX pdf

Here is a project on hashing variants postscript LaTeX pdf

Here is a project on Graph components postscript LaTeX pdf

Here is a project to solve a Chess endgame postscript LaTeX pdf

Zoom Link

All registered students should automatically get the zoomlink but, just in case, it is 976 5675 1248 (for Prof. Spencer's classes, all term.)

Basic Information

There will be a final exam and a midterm.

The midterm will be during a regularly scheduled class time.

The FINAL EXAM will be May, 14, 2021, 8:00am-9:50am ONLINE (Note: New York Time!!)

Tentatively, both the final exam and midterm will be Open Book and Open Notes.

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

Special Note: Collaboration on Weekly Assignments is encouraged.
Each student must submit in a separate file with results written in their own words
and must note any students with whom there has been collaboration.
Click here (modified April 29!) postscript LaTeX pdf for syllabus and more info.

Zoom

Hopefully all registered students will automatically receive information and access to classes and office hours. If a password is requested, use "algorithm".

When and Where

Lecture: Tuesday Thursday, 8:00 a.m. -9:15 a.m. , Place: Hyperspace

Recitation(New York): Wednesday, 8:00a.m. -9:15 a.m., Place: Hyperspace, Ben Jakubowski buj201@nyu.edu

Meeting ID 99680580323

Also: recurring Zoom meeting on NYUClasses at 4:30PM on Mondays. The Zoom meeting ID is 927 0529 8581.

Recitation (Shanghai) Jianyu Zhang

*Time:* 1/28/2021 - 5/10/2021 4:15 PM - 5:30 PM Friday (shanghai time)

*Location: *999 South Pudong Road, Rm 2906, Shanghai (sinmay building)

Instructor

Prof. Joel Spencer

Office: Hyperspace

Office Hours: Monday 10-11 a.m.

Email: {lowercaselastname}@cims.nyu.edu

Teaching Assistant

Benjamin Jakubonski, buj201 (New York)

Jianyu Zhang, jianyu@nyu.edu (Shanghai)

Text

Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein

Questions?

Send me an email: {lowercaselastname}@cs.nyu.edu

SUBMISSION OF ASSIGNMENTS

We will NOT be using gradescope! Rather, send you assignment (.pdf or .jpg or .jpeg) to our grader:

Jingshuai Jiang, jj2903@nyu.edu,

Be sure to mark your name clearly on all pages of your assignment!

CLASS NOTES

Jan 28 1 2 3 4 5 6 7

Feb2 1 2 3 4 5 6 7 8

Feb4 1 2 3 4 5 6 7

Feb 9 1 2 3 4 5

Feb11 1 2 3 4

Feb16 1 2 3 4 5 6

Feb23 1 2 3 4

Feb25 1 2 3 4

March 2 1 2 3 4 5

March 4 1 2 3 4 5

March 9 1 2 3 4 5

March11 1 2 3 4 5 6

March15 1 2 3 4 5 6

March17 1 2 3 4 5 6

March23 1 2 3 4 5

March 30 1 2 3 4

April 1 1 2 3 4

April 6 1 2 3 4 5

April 8 1 2 3 4 5 6 7 8 9

April 13 1 2 3 4 5

April 15 1 2 3 4 5 6 7 8 9

April 20 1 2 3 4 5 6

April 22 1 2 3 4

April 27 1 2 3 4 5

April 29 1 2 3 4 5 6

May 4 1 2 3 4

Assignments

Assignments are mandatory! They are to be submitted to Jingshuai Jiang, jj2903@nyu.edu, by the start of the Wednesday recitation. (8a.m. NYTime)

NOTE: Assignments are often posted early as a courtesy. It is suggested that you check this page on, say, Saturday to see if there have been any last minute changes in the assignment.

Assignment 1. postscript LaTeX pdf

Assignment 2. Due Wed 8 a.m., Feb 10 postscript LaTeX pdf

Assignment 3. Due Wed 8 a.m., Feb 17 postscript LaTeX pdf

Assignment 4. Due Wed 8 a.m., Feb 24 postscript LaTeX pdf

Assignment 5. Due Wed 8 a.m., March 3 postscript LaTeX pdf

Assignment 6. Due Wed 8 a.m., March 10 postscript LaTeX pdf

Assignment 7. Due Wed 8 a.m., March 17 postscript LaTeX pdf

Assignment 8. NOT TO BE SUBMITTED! postscript LaTeX pdf

Assignment 9. Due Wed 8 a.m. April 7 postscript LaTeX pdf figa figb figc

Assignment 10. Due Wed 8 a.m. April 14 postscript LaTeX pdf

Assignment 11. Due Wed 8 a.m. April 21 postscript LaTeX pdf

Assignment 12. Due Wed 8 a.m. April 28 postscript LaTeX pdf

Assignment 13. Due Wed 8 a.m. May 5 postscript LaTeX pdf

Solutions

Posted after assignments are submitted

Assignment 1. 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

Midterm

The exam is HERE postscript LaTeX pdf and here is the exam with solutions postscript LaTeX pdf

Assorted Stuff

QS/BST recursion analysis postscript LaTeX pdf

Rod Cutting (15.1) postscript LaTeX pdf

Text Alignment postscript LaTeX pdf

Fast Fourier Transform (Integer Mult) postscript LaTeX pdf

Games Computers Play postscript LaTeX pdf

April 6: Last Finishing postscript LaTeX pdf

April 8: Union-Find (for Kruskal MST) postscript LaTeX pdf

April 15: Notes on Euclid's Algorithm postscript LaTeX pdf



Just in case: Academic Integrity Policies