Textbook(s)

	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 11 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.
• 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.)

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

For detailed schedule, see the Daily tab of this page.

Grading

Your course grade will be based on:

• exams, 20%
• homework / weekly problem set, 40%
• online contest (4 problems), 15%
• problem presentation, 15%
• participation and progress, 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. Those students should withdraw from the class or switch to Pass/Fail option.

Exams

There will be a midterm and a final exam. All exams are cumulative, timed and synchronous.

Missing an exam: There will be no make-up exams. Failure to take an exam counts as a zero grade on that exam. The only exception to this rule is for students who have a legitimate medical or personal emergency (documented). These students need to talk to the instructor as soon as possible (trying to excuse an exam absence a week after it happened will not work).

Homework / Weekly Problem Sets

Each week you will have a problem set to solve (4-5 problems of varying difficulty). Each problem set is weighted equally.

Online Contests

Throughout the semester we will let you know about various online contests. You need to participate in one or more and submit passing solutions to four different problems (in a single contest or in multiple ones).

Problem presentation

Once during the semester you will need to make a presentation of a problem and its solution. The details of this will be discussed at the start of the semester.

Participation

You are expected to actively participate during the lectures, recitations and on the discussion forum.

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