COS423

• Syllabus
• Lectures
• Precepts
• Problem Sets

Problem Sets

Below are links to the problem sets.

#	DUE	PROBLEM SET	COLLABORATION	SUBMIT
1	Wednesday 2/14	Problem Set 1	allowed	Submit!
2	Wednesday 2/21	Problem Set 2	allowed	Submit!
3	Wednesday 2/28	Problem Set 3	no collaboration	Submit!
4	Wednesday 3/14	Problem Set 4	allowed	Submit!
5	Wednesday 4/04	Problem Set 5	allowed	Submit!
6	Wednesday 4/18	Problem Set 6	allowed	Submit!
7	Wednesday 5/02	Problem Set 7	allowed	Submit!
8	Tuesday 5/15	Problem Set 8	no collaboration	Submit!

Submission policy.  Submit your solutions electronically via the TigerFile submission system, using your Princeton NetID and password for authentication. You may resubmit files without penalty up until the submission deadline.

Your solutions should be carefully organized and neatly typeset in LaTeX using the COS 423 LaTeX template. If you're new to LaTeX, here is a brief LaTeX guide (and the corresponding source file). Please follow these guidelines:

• Submit one tex file and one pdf file per problem (along with any accompanying figures), using the naming convention problem1.3.tex and problem1.3.pdf for problem 3 on Problem Set 1.

• Write your name, your Princeton NetID, and the problem number at the top of every page.

• Write the NetID of each of your collaborators at the bottom of the first page.

Late submissions. Problem sets are due at 11pm on Wednesday evenings. If any part of a problem set is submitted late, the entire problem set will be marked late. Once the deadline has passed, we will grade any submitted work as-is. If you wish to submit a problem set late, do not submit any files until you are ready to turn in the entire problem set.

Penalties for late submissions. There is a 59-minute grace period. Late assignments are assessed a penalty equal to 10% of the possible points on the assignment per day or partial day late. The penalties for your first four late days are automatically waived. Additional late penalties will be waived only in the case of a medical or personal emergency, as documented in a note from a Dean or Director of Studies.

Grading policy.  Your code will be graded for correctness, efficiency, clarity, conciseness, and mathematical rigor. It is your responsibility to describe your algorithm clearly and prove that it achieves the specified performance requirements. Partial credit is available for a partially completed problem (or one that does not meet the performance requirements).

Writing up your solutions.  Learning how to write clear, concise, and rigorous solutions is an important component of this course. Vague and sloppy solutions often turn out to have inaccuracies that render them incorrect. You will lose a significant number of points if your solution is imprecise or lacks sufficient explanation, even if the main idea is correct. Here are a few guidelines:

• Some of problem sets contain word problems that consist primarily of an English description of a problem, with little or no mathematical notation. This is intentional. For such problems, you should first extract the essence of the underlying problem and formalize it mathematically, then solve the problem.

• When a problem asks you to design an efficient algorithm, you are expected to provide an efficient algorithm along with both a proof of correctness and an analysis of its running time. Often, it is your job to determine what efficient means in the given context—Θ(n log n), Θ(n²), or something else.

• Typically, the best way to describe your solution is to first explain the key ideas in English, possibly with the use of some clearly-defined notation and some high-level pseudocode. A solution consisting solely of pseudocode and no accompanying explanation will receive little or no partial credit.

• Once you have discovered a solution to the problem, try to simplify it and make it as elegant and clear as possible. This will not only help the grader understand your solution but it will provide you with an opportunity to clarify your thoughts and gain insight into the problem. At this point, you may even be able to improve your algorithm and analysis. Along these lines, we will award bonus points for especially elegant or efficient solutions.

Collaboration policy.   Designing and analyzing an algorithm is an individual creative process much like writing a composition or computer program. You must reach your own understanding of the problem and discover a path to its solution. Each problem set will be designated as either no collaboration or collaboration allowed.

• No collaboration. Collaboration of any kind is a violation of academic regulations. There are two exceptions: you may consult the course staff and the COS 423 course materials. Course materials are limited to the following: the Kleinberg–Tardos textbook, course handouts, lecture slides, your class notes, and your solutions to previous problem sets.

• Collaboration allowed. You are permitted and encouraged to discuss ideas with classmates. However, when the time comes to write your solution, such discussions are no longer appropriate—your solution must be your own work, in your own words.

Academic integrity.   The creative process leading to the discovery of a solution is as important as understanding and being able to present a solution. The following activities are explicitly prohibited in all graded coursework:

• Failing to properly cite your source and collaborators. You must always cite your sources (other than the COS 423 course materials) and the names of any individuals with whom you collaborated (other than COS 423 staff members).

• Copying or paraphrasing another person's solution. This includes adapting solutions or partial solutions from any offering of this course or any other course.

• Possessing another person's solution or partial solution. This includes solutions in electronic, handwritten, or printed form.

• Giving a solution or partial solution to another person. This applies even if you have the explicit understanding that it will not be copied.

• Looking up solutions. This includes searching for solutions from previous offerings of this class or any other class.

• Providing, receiving, or soliciting help to or from another person on a problem set that is designated as no collaboration. The one exception is help from a COS 423 staff member.

• Publishing a solution or partial solution to a problem set. This applies even after the course is over.

Penalties for academic violations.  We refer alleged academic violations (including plagiarism and abetting plagiarism) to the Committee on Discipline. If found responsible, the typical penalty is an F as a course grade plus whatever penalty that the CoD imposes. (The typical CoD penalty for plagiarism is suspension from the University for one year.) Violators of course policies that are not adjudicated by the CoD will receive penalties based on the severity of the violation, ranging from a warning (for violations that are both unintentional and innocuous) to an F in the course (for violations that are both intentional and serious).