Textbook(s) - ALl Optional

	Competitive Programming, 3rd edition, Steven Halim, Felix Halim, optional
	Programming challenges : the programming contest training manual Steven S. Skiena, Miguel A Revilla, accessible through NYU Libraries
	Guide to competitive programming : learning and improving algorithms through contests, Antti Laaksonen, accessible through NYU Libraries
	Principles of Algorithmic Problem Solving, Johan Sannemo, preliminary draft of the book, available through the author's site
	Algorithmic problem solving, 2011 Roland C. Backhouse, accessible through NYU Librarires

Useful Resources

• Java API 17 documentation
• CPP Reference
• CPlusPlus
• Source code examples for the CP3 book - collection of zip files for the third edition of the book
• GitHub Repository with the code for the book, updated for the next edition of the book

Prerequisites

• Passing CSCI.UA.0201 with a grade of C or better.
• Passing CSCI.UA.0310 with a grade of C or better. (talk to me if you did not complete this course)
• Strong familiarity with either Java or C++ or both. (You will not be able to program in Python.)
• (You are expected to also know and remember the material from CSCI.UA.0101 and CSCI.UA.0102 courses.)
• But, most importantly, interest in solving problems, learning about different approaches and designs, and curiosity.

Topics Covered (exact list of topics will depend on how quickly or slowly we will go through the material)

• programming basics: I/O, variable types and ranges
• time/space complexity analysis: estimate the execution time of a program
• fundamental data structures: array, linked list, stack, queue, binary search tree, hash table, heap/priority queue,
• tree data structures: union-find, trie
• problem solving strategies: complete search, greedy, binary/ternary search, divide-and-conquer
• decomposition and range queries: square-root/binary decomposition, segment tree, Fenwick tree, sparse table,
• graph algorithms: shortest path, topological sort, minimum spanning tree, Eulerian path/cycle, strongly connected components, articulation points & bridges
• dynamic programming (DP): subset sum, weight balancing, knapsack, longest common subsequence (LCS), edit distance, longest increasing subsequence (LIS), Hamiltonian path/cycle, DP state design and transition formulation
• string matching: Rabin-Karp, polynomial string hashing, KMP
• mathematics: prime, sieve of Eratosthenes, combinatorics, probability and expected value

Grading

Your course grade will be based on:

• two paper exams, 35% (15% each)
• three coding exams (10% each)
• weekly problem sets 10%: problem set with 5 problems each week (see Gradescope verdicts for how the scores are computed)
• video presentation of an assigned problem 10%: recorded 20-25 minute problem presentation
• regular in-class activities, polls, pop-quizzes, 10%
• online Codeforces contest participation, 10%

The letter grades will be determined using the following scale:

    A   95-100
    A-  90-95
    B+  87-90
    B   83-87
    B-  80-83
    C+  76-80
    C   72-76
    D   65-72
    F   less than 65

The grade of Incomplete is reserved for students who, for legitimate and documented reason, miss the final exam. The grade of Incomplete will not be given to student who started falling behind in class or missed earlier exams or assignments. Those students should withdraw from the class or switch to Pass/Fail option.

Paper Exams

There will be two paper based exams. All exams are cumulative, timed and synchronous. You are expected to write algorithms (in a programming language independent fashion) and apply given algorithms (no coding).

Missing a paper exam: If you miss the exam 1, the exam 2 score will count for both. If you miss the exam 2, you will receive a grade of incomplete in the course and you will need to take the exam 2 during the first week of the spring semester.

Coding Exams

There will be three coding exams: two during the regular lecture time and the third during the time allocated for the final exam. These will be timed and synchronous exams and you will have to code in a controlled environment with limited access to resources other than your own knowledge.

Missing a coding exam: If you miss the exam 1, or the exam 2, the score will be replaced by exam 3. If you miss the exam 3, you will receive a grade of incomplete in the course and you will need to take the exam 3 during the first week of the spring semester. You cannot miss more than one of the coding exams.

Weekly Problem Sets

Each week you will have a problem set to solve (several problems of varying difficulty). You should expect 12 problem sets with 5 problems each. (These numbers may be adjusted if there are significant changes to the course scheduling.) Fifty highest scoring problems will count towards your course grade. There will be no late submissions on problem sets for any reason (this is why we will be dropping ten lowest scores). We will try to avoid having due dates that conflict with major holidays, but it is not always possible. The only late submissions will be allowed at the start of the semester to accommodate students who may be joining the class after the due date for a problem set.

Video Presentation

For each problem set, there will be several students who will need to submit a video presentation of their solution for one of the week's problems. These will be graded on completeness and clarity of the explanation, and consistency of the explanation with the submitted code. Each week we will randomly pick a number of students to submit such a video. If you wish, you can volunteer for a given week, but we will restrict the number of volunteers.

If you are not satisfied with the score that you receive for your video submission, you can submit another video for a different problem (assigned to you in the later time). The second grade will count towards your course grade.

In-class Activities, Polls, and Pop-Quizzes

There will be a number of paper-based pop-quizzes, polls and other types of activities during the regular lectures. We will drop one quarter of these grades to account for any absences.

Online Contests

You need to participate in one or more of the regular contests hosted on Codeforces. You need to submit passing solutions to five different problems (in a single contest or in multiple ones). Your solutions need to be submited while the contest is active, not after the contests concludes. Think of this as practice of your skills in the real world.

More details on which contests and problems qualify will be provided later.

Check the calendar of contests on Codeforces site for upcoming contests. There are contests added on a regular basis.

Generative AI Policy

The rise of generative AI tools like Gemini, ChatGPT, Copilot, and many others is fundamentally changing the landscape of computer science and beyond. Given their ubiquity, it is increasingly difficult to avoid their use. In this class, we will not ban these tools; instead, we hope that you will use them to your benefit rather than to your detriment.

Using AI to do all of your coding work for you will be a detriment to your learning. This approach will leave you unable to perform on exams, succeed in technical interviews, or be a reliable contributor on projects where you are expected to be an expert. True mastery in this field comes from a deep, hands-on practice and understanding of the material, not from effective prompting.

Instead, we encourage you to use AI as a learning partner, leveraging its capabilities in the following ways:

• AI as a Feedback Generator: Use AI to review your code and offer suggestions for improvement, just as a peer would. You can ask it to identify potential bugs, simplify complex sections, or suggest alternative approaches (but make sure to document such assistance, make sure that the suggested changes are correct and that you understand them).
• AI as a Personal Tutor: When you're stuck on a concept, use AI to explain it in different ways. You can ask it to break down a difficult topic, provide more examples, or clarify why a particular solution works. Remember, however, that AI can "hallucinate" incorrect information; you are responsible for critically evaluating and verifying any information it provides. Sometimes it may be wiser and safer to visit instructors' office hours or tutoring hours to get help rather than relying purely on AI for such help.

Keep in mind that exams and other assessments in this class will be given with no access to AI tools, so you need to be able to write complete programs, implement parts of given programs, answer questions and suggest solutions to problems on your own without the help of any tools.

Further resources:

• Provost’s Guidance on Student Learning with Generative AI

Academic Integrity Policy

This course follows the university and departmental policies on academic integrity:

• Academic Integrity for Students at NYU
• CS Department Academic Integrity

Our main philosophy is that you need to be honest and fair to yourself, other students in the class and the instructional stuff.

We know that interactions with your classmates can facilitate deeper understanding of the subjects and provide invaluable lessons. But to benefit from those lessons you need to be a participant in the team and not just a taker.

All your work that is submitted for grading in this class has to be your own, unless otherwise specified. You need to acknowledge any help that you receive on the assignments in your submissions.

Here are examples of fair and not fair actions that a student may take. This is not an exhaustive list and should serve as examples of behaviors rather than a complete definition.

Fair Actions

• Working and solving a weekly problem set with other students AND writing the actual program on your own (you should acknowledge the names of all those involved in discussions)
• Discussing problem sets and assignments with the instructional stuff and acknowledging such discussions in your submission.
• Incorporating a short fragment of code (a few lines) that you find in the course suggested resources or other online resources and acknowledging it in your submission.
• Sharing code with others (possibly your classmates) that illustrates concepts and techniques discussed in this course as long as this code is not a solution (or a partial solution) to one of the assigned problems. (An example of such code would be routines that handle reading from and writing to standard intput/output streams.)

Not Fair Actions

• Making your solutions available to others (publicly or privately). (This includes posting solution on a discussion forum, in a public repository, etc.).
• Asking a classmate to see their solutions prior to the last date at which submissions are accepted (this may be different than the due date).
• Failing to acknowledge any form of help in the submission.
• Finding or generating solutions to problems online and using them for your own submissions.
• Asking anybody (other than the instructional stuff) for help during an exam.
• Looking at another student's work during an exam.

Academic Email Etiquette

• Check the school email address on a regular basis. You can simply forward its content to another email account that you use regularly.

• Use your school's email account to send emails to professors, instructors, TA's, graders, administrators, etc. OR make sure that your email address contains your true name, not "frabjous@gmail.com", "BabyGurl@yahoo.com" or some other cool alias.

• Start your email with proper salutations! Use the correct titles (Professor, Dr., etc.) and spell first and last names correctly. If you are on the first name basis with your instructors, use their names, not "Hey". For example: "Dear Professor Drummer" or "Dear Robert", not "Hey Bob".

• Sign your name under the body of your email, otherwise you expect people to read emails from anonymous.

• Do not write everything in upper-case letters. Do not write everything in lower-case letters.

• Make sure you included everything you wanted before hitting send. Don't send three emails one after another because you forgot something in the first one.

• Proofread the text in your email before sending it. Most of the email clients check for typos, but they cannot tell if your email makes much sense. Read it, before you send it.