Course Information
Description
This course is about Algorithms: procedures for solving problems.
The goal of this course is to help you:
- Acquire essential analytical skills necessary for understanding the efficiency and correctness of algorithms
- Learn how to construct high-level abstractions for problems and how to design algorithms to solve them
- Develop the ability to clearly and coherently communicate algorithmic designs and prove why they work
-
Prepare for tech interviews??
We will study various algorithms for classical problems such as:
- Sorting
- Graph Problems
- Data Structures
We will also learn some general techniques for designing algorithms, such as:
- Divide & Conquer
- Greedy
- Dynamic Programming
Disclaimer: This is a class about theoretical computer science. You will be expected to understand and write proofs. While we will write extensive pseudocode, there will be no programming component.
Prerequisites
Data Structures (CSCI-UA 102); Discrete Mathematics (MATH-UA 120); and either Calculus I (MATH-UA 121) or Mathematics for Economics I (MATH-UA 211).
Resources
Textbook: Introduction to Algorithms, 4th Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. Available online via NYU Libraries.
Supplemental Text: Algorithm Design by Jon Kleinberg and Eva Tardos. See also the corresponding Lecture Slides by Kevin Wayne.
Have Questions? The best way to reach us for any question on any topic, large or small, public or private, is by posting on Campuswire. The teaching team will not respond to questions sent through emails.
Homework
There will be 11 written homework assignments, roughly on a weekly basis. Homeworks will be due at 10:00 PM ET on the specified deadlines.
Submission
Homeworks should be submitted in PDF form on Gradescope. We prefer homework submissions typeset in LaTex. If you are not familiar with LaTex, it is a great skill to learn. Overleaf provides a simple web interface for writing and compiling LaTex (as well as extensive documentation). For each homework assignment, we will provide the LaTex source file for you to edit from. You are encouraged to insert scanned figures or illustrations where appropriate. Scanned handwritten submissions will only be graded if perfectly legible. If you are unsure about your handwriting, I strongly suggest you type up your solutions.
Collaboration
We strongly encourage you to discuss assignments with your peers, but you must (a) list the names of your discussion partners on your submission, and (b) write up your solution on your own. You may not look at the written solutions of any other student before submitting your own solution. If you do not list the names of your collaborators, you will be penalized.
Regrade Requests
We do our best in this course to grade as accurately and as thoroughly as possible. We understand how important it is for your grades to be fair and correct. If there is an error, you're encouraged to submit a regrade request on Gradescope. Regrade requests must be submitted at most three days after that assignment/exam's grades are released. Regrade requests that are not polite or that take issue with the rubric design (as opposed to misapplication of the rubric as it is) may be closed without comment.
Late Policy
Late submissions of homework solutions will be graded with a 20% penalty per day of late submission. Solutions will not be graded if they are submitted more than two days after the specified deadline. To accommodate unforeseen personal circumstances, your two lowest homework scores will be dropped. No further extensions or accommodations will be granted, except under very rare circumstances.
External Resources
I encourage you to consult outside resources to deepen your understanding both of material we cover in class, and the many things we will (regrettably) not have time to cover. You must explicitly acknowledge any external resources consulted in your homework.
However, you are not allowed to consult any resource for the purpose of finding homework solutions. For example, you may not consult homework solutions for a previous version of this class. Violations to this policy is plagiarism and will not be tolerated.
Exams
There will be one in-class midterm exam and one final exam. Their time and location are as follows:
- In-Class Midterm is Thursday, October 24, 9:30-10:45 AM in WWH 312.
- Final Exam is Thursday, December 19, 8:00-9:50 AM location TBA.
Both exams will be closed-book and closed-notes. For the midterm, you are allowed one double-sided 8.5''x11'' page of note. For the final, you are allowed two double-sided 8.5''x11'' pages of note. The final exam will be cumulative, but with a slight focus on the materials covered in the second half of the semester. A practice exam will be released one week before each exam date.
Grading
Final placement in the class will be determined by the following formula:
0.3 H + 0.3 M + 0.4 F
where H is your average score on the homework assignments after dropping the lowest two, M is your midterm exam score, and F is your final exam score.
Applicable University Policies
Academic Integrity
Your work should be your own. Students should be aware of the CS Department's Policy on Academic Integrity. Violations of academic integrity will not be tolerated.
Religious Observance
As a nonsectarian, inclusive institution, NYU policy permits members of any religious group to absent themselves from classes without penalty when required for compliance with their religious obligations. The policy and principles to be followed by students and faculty may be found in the University Calendar Policy on Religious Holidays.
Disability Disclosure
Academic accommodations are available to any student with a chronic, psychological, visual, mobility, learning disability, or who is deaf or hard of hearing. Students should please register with the Moses Center for Students with Disabilities.
