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. We've also prepared an assignment FAQ that answers common questions about assignment submissions, programming style expectations, and the required readme.txt files.
| # | DUE | LOGO | ASSIGNMENT | COLLABORATION | SUBMIT |
|---|---|---|---|---|---|
| 1 | Sunday Feb 12 |
 |
Percolation (Checklist) Given a system of randomly distributed insulating and metallic materials: what fraction need to be metallic for the system to be an electrical conductor? |
This is an individual assignment. | Submit! |
| 2 | Sunday Feb 19 |
 |
Deques & Randomized Queues
(Checklist) Implement two general-purpose data structures using arrays, linked lists, generics, and iterators. |
You can work with a partner on this assignment. | Submit! |
| 3 | Sunday Feb 26th |
 |
Autocomplete (Checklist) Implement text autocompletion by finding all terms beginning with a given prefix, sorted by associated weight. |
You can work with a partner on this assignment. | Submit! |
| 4 | Sunday Mar 5th |
 |
8 Puzzle (Checklist) Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm. |
You can work with a partner on this assignment. |
Submit! Leaderboard (Results) |
| 5 | Sunday Mar 12th |
 |
Kd-Trees (Checklist) Create a symbol table data type whose keys are two-dimensional points, supporting efficient range search and nearest neighbor search. |
You can work with a partner on this assignment. |
Submit! Leaderboard (Results) |
| 6 | Sunday Apr 9th |
 |
WordNet (Checklist) Find the shortest common ancestor of a digraph in WordNet, a semantic lexicon for the English language that computational linguists and cognitive scientists use extensively. |
You can work with a partner on this assignment. |
Submit! Leaderboard (Results) |
| 7 | Sunday Apr 16th |
 |
Seam Carving (Checklist) Implement a content-aware image resizing algorithm where an image is reduced in size based on the pixels with the least "energy" content. |
This is an individual assignment. | Submit! Leaderboard (Results) |
| 8 | Monday May 15th |
 |
Burrows Wheeler (Checklist) Implement Burrows-Wheeler data compression, a revolutionary algorithm that outcompresses gzip and PKZIP. |
This is an individual assignment. | Submit until Tuesday 5pm, May 16!
Leaderboard (Results) |
|
Caution. The assignments below have not yet been updated for this semester and may change significantly.
|
Submission policy. You must submit your solutions electronically via the Dropbox submission system, using your Princeton netID and password for authentication. Be sure to include your name, netID, and precept number at the top of every file you submit in the prescribed format. Also be sure to click the Check All Submitted Files button: it 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 resubmit and unsubmit files as needed up until the submission deadline. However, you may click the Check All Submitted Files button at most 10 times per assignment (at which point you get compile, checkstyle, findbugs, and API results but no correctness tests). To use a late day, students must check the checkbox on our online submission system, Dropbox, that indicates that their work is not complete. If the deadline has passed and the checkbox is not checked, submitted work will be graded as-is.
If you are working with a partner, only one partner (with the other partner present) submits the code and readme.txt; the other partner either submits no files or will leave the checkbox checked to indicate that none of the partner files should be graded. Both partners in total have 10 times to use the Check All Submitted Files button. For example, one partner may submit 7 times and the other may submit 3 before the Correctness checks are disabled.
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.
Lateness policy. programming assignments are due at 11pm on the date specified, with a 3-hour grace period. Late assignments are assessed a 4-point penalty per day or partial day: 0–3 hours late (no penalty), 3–27 hours late (4 points), 27–51 hours late (8 points), and so forth. your first 16 lateness points are automatically waived. No additional lateness points will be waived without the recommendation of a Dean or a letter from McCosh Health Center.
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
in the submission, 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.
Collaboration policy. This course permits many forms of collaboration, including help 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.
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 via personal interactions or the Piazza course forum. These discussions must be kept at a general level, without exposing your solutions. For example, you may ask about:
N is 0?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 in a previous offering. 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.
Piazza works best for individual questions with well-defined answers.
Use public posts when your question can be asked in a general way, without sharing code or other work about assignments. Other students may answer it, or they may benefit from seeing the discussion.
If you have a question that involves your code or other specific details, then use office hours, the lab, or this two-step approach:
Never post assignment code to Piazza, even privately; the Dropbox is easier for course staff to use.
Collaboration with a partner. On those programming assignments designated as partner, the collaboration policy is relaxed to permit working with one classmate, as long as both students have a passing grade on a previous assignment. Choose a partner whose skill level is close to your own. Two students may partner on up to 3 assignments together. If either student wishes to continue partnering after those 3 assignments, they must find a new partner. In such cases, both students must work together (in the same room) and discuss, write, debug, test, analyze, document, and submit all elements of the assignment together. There is one exception—you may discuss your solutions with course staff in office hours, even if one partner is unable to attend. Both partners are responsible for understanding all parts of the submitted assignment and receive the same grade. Take turns leading. If two students begin working on an assignment as partners and cannot complete it together, (at least) one student must contact the lead preceptor to request a partnership dissolution.
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 any collaboration (whether authorized or unauthorized) in the readme.txt file for that week's assignment. Using and acknowledging unauthorized collaboration will typically result in a grade of 0 for the assignment (but no further penalty).
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 assignments, checklists, lecture slides, lecture videos, and precept handouts). If you do so, you must cite any code that you copy or adapt. 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 0 on the assignment to an F in the course.