Assignments & Projects
Please carefully read the Academic Integrity before you start working on the homework assignments.
In short, you can get help from the instructors, TAs, textbooks (or relevant books), the Internet, or discussions with your classmates, but you must cite them fully and completely (i.e., provide citations to the book or website link, acknowledge the other students that had discussions with you). Again, you are NOT allowed to:
- copy anything from the book or the Internet,
- read or look at anyone else’s solutions (write-up or code),
- share your solutions (write-up or code) with any other students, during or after the completion of the course (other than your teammate for the problem-solving challenge).
When you write down your solution, it MUST be close-book. This is to make sure you truly understand and can recreate the solutions.
You must use LaTeX to prepare your solution. Here you can find sample code for writing solutions using LaTeX.
Programming Problems in Homeworks
All problems will be given on codeforces, so we do not post the problems here.
We will use CodeForces to submit and test codes. You also need to submit a short report to describe your algorithm and specify your submission id. Here is a guideline about using CodeForces.
We run automatic code comparison programs on student solutions. These programs are very good at detecting similarity between code, even code that has been purposefully obfuscated. Such programs can compare a submitted assignment against all other submitted assignments, against all known previous solutions of a problem, etc. The signal-to-noise ratio of such comparisons is usually very distinctive, making it very clear what code is a student’s original creative work and what code is merely transcribed from some other source. Cheating is simply not worth the risk.
You need to submit a brief report on how you solved these problems, including:
- Your name, SID, and your codeforces ID;
- Specify which submission is yours (there is a unique id for each submission);
- Describe the algorithm you designed;
- Show cost analysis if necessary.
You will not get the point if you don’t provide the report to explain how your algorithm works.
| Event | Deadline |
|---|---|
| Programming Part for Homework 2 | Oct 31 |
| Programming Part I for Homework 3 | Nov 14 |
| Programming Part II for Homework 3 | Nov 21 |
| Programming Part for Homework 4 | Dec 1 |
We will have about 10 programming problems in the homework to help you get a deeper understanding of the algorithms covered in this course.
You can get more than 100% for your final grade. Indeed, many of you will, and those of you will receive A+ in CS 219.
Written Homework Assignments
There will be three written homework assignments, similar to normal written homework in other courses. The total point for each assignment can be found on the policy page. You must use LaTeX to prepare your solution.
| Homework | Deadline |
|---|---|
| Homework 1 | Oct 19 |
| Written Part for Homework 2 | Nov 7 |
| Written Part for Homework 3 | Nov 21 |
Course Presentation
We have the privilege of a small class, and everyone will have a chance to give a presentation. As an advanced-level graduate course mostly for students doing research work, this course will help you practice and boost your presenting skills, which are crucial for your research career.
In particular, we will have two types of slots, one for 20 minutes, and the other for 40 minutes (only two slots available for this type). If you choose a 40-minute slot, the maximum points for your presentation will be 25 pts instead of 20 pts. All slots will be in the last five lectures, reserved in a first-come-first-take order. For the 20-minute slot, examples can be some topics from our textbook but not covered in CS 141/142/218/219, an algorithm in a research paper, etc. The 40-minute slot should contain more content, such as a few algorithms for the same topic which may involve some co-design of data structures. An example topic can be “dynamic graph connectivity”. In any case, you should have a consensus with the instructors on the topic, which guarantees it is not too hard or too simple. You should contact the instructor either directly or using DM on campuswire. The deadline of finalizing the topic is Nov 20.
You should prepare slides for your presentations. To guarantee your talk quality, the presenter must send a draft version of the slides to Yan at least two days (48 hours) before the presentation. This part is 5 pts (i.e., if you do so with finished slides, you will always receive 5 pts; otherwise you will receive 0 pts). Then, Yan will talk to you with feedback for one to several iterations, depending on the quality of your preparation. Then, your talk will be evaluated by the criteria in this evaluation form for the rest 15 or 20 pts. You are welcome to reverse engineer the grading process.
This link is about how to give a clear talk.