Theory of Algorithms
Course Information |
Problem Sets |
Lecture Slides |
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
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), Θ(n2),
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.
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
Any files submitted at grading time will be graded as is.
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.
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.
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.
Rights, Rules, Responsibilities handbook asserts:
The only adequate defense for a student accused of an academic
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
If you have any questions about these matters, please consult a course
staff member. Violators will be referred to the Committee on Discipline for
review; if found guilty, you will receive
an F as a course grade plus whatever disciplinary action the