This page contains all the programming assignments for this course. In addition to the assignment specifications, you will also find checklists that are designed to offer potential starting points, clarifications, test data, and hints for each assignment. The assignment FAQ answers common questions about assignment submissions, programming style expectations, and the required readme.txt files.

1 Monday
Estimate the percolation threshhold using Monte Carlo simulation and union–find.
(checklist, testing)
2 Monday
Deques and Randomized Queues
Implement two collection data types using arrays and linked lists.
(checklist, testing)
3 Monday
Find all terms beginning with a given prefix, sorted by weight.
(checklist, testing)
4 Monday
8 Puzzle
Solve a slider puzzle using the A* search algorithm.
(checklist, testing)
5 Monday
Implement kd-trees, supporting range search and nearest neighbor search.
(checklist, testing)
6 Monday
Meaure the semantic relatedness of two nouns using the WordNet digraph.
(checklist, testing)
7 Monday
Seam Carving
Implement a content-aware image resizing algorithm.
(checklist, testing)
8 Monday
Burrows Wheeler
Implement the Burrows–Wheeler data compression algorithm.
(checklist, testing)

Submission policy.  Submit your solutions electronically via the Dropbox submission system, using your Princeton NetID and password for authentication. Include your name, NetID, and precept number at the top of every file you submit. You may resubmit files without penalty up until the submission deadline.

Submitting with a partner.  If you are working with a partner, only one partner (with the other partner present) submits the code and readme.txt; the other partner submits neither the code nor readme.txt.

Check all submitted files.  Clicking the Check All Submitted Files button checks the header, compiles your files, runs a battery of unit tests, and reports the results. If you do not follow these instructions, you risk losing a substantial number of points. You may click this button at most 10 times per assignment (after which you will receive only limited feedback). If you are working with a partner, this limit applies to the group.

Late submissions. Assignments are due at 11pm on Monday evenings. If any part of an assignment is submitted late, the entire assignment will be marked late. To submit an assignment late, mark the checkbox on our online submission system, Dropbox, that indicates that your work is incomplete. If the deadline has passed and the checkbox is not marked, we will grade any submitted work as-is.

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.

Classwide competitions.  On some assignments, you may (optionally) submit your code to a classwide competition. We will time your programs and display the results in a public leaderboard. To enter the competition, submit your code along with a file nickname.txt. Whatever you put in nickname.txt will be used as your alias in the leaderboard. There is no official reward for doing well in the competition; however, you are welcome to use it as a guide for evaluating the performance of your program.

Coursera policy.  You are not permitted to use the Coursera autograders from Algorithms, Part I or II. Countermeasures are in place.

Grading policy.  Your code will be graded for correctness, efficiency, clarity, and style (including comments). It is your responsibility to describe how you have completed the assignment, not ours to glean this information from your code. Partial credit is available for a partially complete assignment; just explain the situation in your readme.txt file. Graded work is available via codePost.

Collaboration policy.  This course permits many forms of collaboration, including with from course staff, classmates, and lab TAs. However, you must be careful to collaborate only as authorized below. Here is an executive summary.

activity your partner course staff COS 226 grads clasmates other
discuss concepts with ...
acknowledge collaboration with ...
expose solutions to ... no no
view solutions from ... no no no no
plagiarize code from ... no no no no no

Your solutions.  You must individually compose all of your solutions. The term solutions refers to any of the products created when completing a programming assignment, such as source code (including comments) and the readme.txt file. It includes both finished and unfinished products, regardless of correctness or completeness.

These rules continue to apply even after the semester is over.

Collaboration with course staff.  You are welcome to discuss your solutions with course staff members (instructor and preceptors) in office hours or via private Piazza posts. Do not post or email us your code; instead, submit it via the course submission system.

Collaboration with classmates.  We encourage you to discuss common concerns with classmates either privately via personal interactions or publicly in the Piazza course forum. These discussions must be kept at a general level, without exposing your solutions.
For example, you may discuss: But, you may not:
  • How to use a feature in DrJava, Terminal, or Command Prompt. For example, “How do I copy text from the Terminal?”
  • The definition of a piece of Java syntax. For example, “How do I implement the Iterable interface?”
  • Clarifications for the lecture videos, lecture slides, textbook, old exam questions, or the assignment specifications.
  • Look at another classmate’s solutions.
  • Show another classmate your solutions.
  • Lead a classmate step-by-step through any part of the assignment
  • Allow a classmate to lead you step-by-step through any part of the assignment.

Collaboration with COS 226 graduates (including lab TAs and peer tutors).  You are permitted to show your solutions to anyone who has successfully completed COS 226. So, for example, you may receive help from lab TAs in debugging your code. Of course, you must still individually compose your solutions. So, for example, you may not allow another individual to write, type, or dictate code; lead you step-by-step through any part of the assignment; or communicate solutions (including their solutions from a previous offering). Other individuals may help you under these same conditions, provided they are not taking COS 226 now and never will in the future.

Collaboration with a partner.  On those programming assignments designated as partner, the collaboration policy is relaxed to permit working with a classmate, subject to the following rules:

Both partners are responsible for understanding all parts of the submitted assignment and receive the same grade.

Collaboration with yourself.  If you took COS 226 (or Algorithms, Part I or II from Coursera) during a previous offering, you may look at your old work but you may not look at the feedback we gave you on your old work. What’s more, you may not look at your old work on assignments where: you previously partnered; or you are partnering this time; or you were previously found responsible for plagiarism by the Committee on Discipline. In our experience, students who re-do all of the assignments from scratch are much more likely to succeed in the course, so this is what we strongly recommend.

Collaboration acknowledgement.  You must acknowledge all collaboration in the readme.txt file for that week’s assignment.

Outside sources and citations.  Copying or adapting code that is not yours is permitted only if it comes from the course materials (i.e., the course textbook, companion booksite, programming assignment specifications, checklists, lecture slides, lecture videos, and precepts). If you do so, you must cite any code that you copy or adapt (with the exception of code that is included with the assignment). However, you do not need to cite any code included in either the assignment specification or checklist.

Plagiarism.  Programming is a creative work and the academic regulations that apply to plagiarizing prose also apply to plagiarizing code. Rights, Rules, and Responsibilities defines plagiarism as “the use of any outside source without proper acknowledgment.” It ranges from “verbatim copying” (e.g., cutting-and-pasting code) to “thorough paraphrasing” (e.g., changing variable names or rearranging code). We use sophisticated tools to detect plagiarism and our teaching staff takes the issue very seriously.

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