PROBLEM SETS

Below are links to the problem sets. You will submit the problem sets via our electronic submission system.

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 solution turns out to be 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 clean 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.

• If you don't know the answer, then write I don't know, for which you will be awarded 20% of the available credit. You will receive no credit for a deeply flawed answer. It is better to acknowledge that you are stumped than to pretend that a bogus solution is correct.

Submission policy.  You must submit your solutions electronically via the Dropbox submission system. Your solutions should be carefully organized and neatly typeset in LaTeX using the COS 423 LaTeX template (and the pdf output). If you're new to LaTeX, here is a brief LaTeX guide (and the tex source file). Please follow these guidelines:

• Submit one tex file and one pdf file for each 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 login, and the problem number at the top of every page.

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

You will need to type your Princeton netID and password for authentication. You can resubmit and unsubmit files as needed up until the submission deadline. Any files submitted at grading time will be graded as is.

Lateness policy.   Problem sets are due at 11pm on the date specified, with a 3-hour grace period. Late submissions are assessed a penalty of 10% of the total points for that problem set per day or partial day: 0–3 hours late (no penalty), 3–24 hours late (10%), 24–48 hours late (20%), and so forth. Your first 4 late days are automatically waived. No additional lateness days will be waived without the recommendation of a Dean or a letter from McCosh Health Center.

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 you may consult 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 out 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 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 staff member.

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

This policy supplements the University's academic regulations, making explicit what constitutes a violation for this course. Princeton Rights, Rules, Responsibilities handbook asserts:

The only adequate defense for a student accused of an academic violation is that the work in question does not, in fact, constitute a violation. Neither the defense that the student was ignorant of the regulations concerning academic violations nor the defense that the student was under pressure at the time the violation was committed is considered an adequate defense.