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.
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.
Problem-Solving Assignments
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.
| Assignment | Release Date | Deadline |
|---|---|---|
| Problem-Solving I | 1/3 | 1/14 |
| Problem-Solving II | 1/15 | 2/2 |
| Problem-Solving III | 2/3 | 2/21 |
In each assignment, there are six problems. The first three problems are easier, and each is worth for 30 points—20 points for multiple testcases, and if you pass them all, you will receive another 10 points. The last three problems are optional and are much harder. Each problem is worth for 15 points—10 points for multiple testcases, and if you pass them all, you will receive another 5 points.
You can get 135 points in maximum for each assignment, which contributes 10% to your final grade. If you get 100 points in one assignment, you will get the full 10% for your final grade, and if you get 135 points, you will get 13.5%. This means you can get more than 100% for your final grade. Indeed, many of you will, and those of you will receive A+ in CS 142.
Performance-Engineering Assignments
Performance-Engineering Assignments include written problems and programming problems.
The written part is similar to other algorithm courses you have taken, and you must use LaTeX to prepare your solution. Here you can find sample code for writing solutions using LaTeX. The programming part is based on a server ti-05, and the detailed instruction will be given in the assignment problem description.
In grading, we will reward not only correctness but also clarity and simplicity. To avoid losing points for hard-to-understand solutions, you should make sure your solutions are either self-explanatory or contains good explanations. Please understand that grading your assignments is a lot of work for your TAs and readers, especially determining the correctness and cost bounds for your algorithms. We reserve the right to manually deduct points for solutions that are conceptually correct but does not show a sincere attempt to explain the ideas clearly.
| Assignment | Release Date | Deadline I | Deadline II |
|---|---|---|---|
| Performance-Engineering I | 1/3 | 1/19 | 1/24 |
| Performance-Engineering II | 1/25 | 2/8 | 2/11 |
Each performance-engineering assignment contributes 15% to your final grade. Similar to the problem-solving training, it is out of 100 points. Hence, if you get 120 points in one assignment, you will get 120%*15%=18% to your final score. If you score more than 100% for your final grade, you will receive A+ in CS 142.
Project
CS 142 has a project for either sequential or parallel algorithms. For Winter 2022, the list of sequential algorithm you can pick and implement include: Graham scan, Fortune’s algorithm, Joined-based trees, BGSS’s algorithm for SCC, van Emde Boas tree, Hungarian algorithm, Hopcroft–Karp algorithm, or any other algorithms that has the instructor’s permission. You should not use your project for other courses, such as A* algorithm. The parallel option is quicksort, and we will let you join a git-classroom and work on a parallel quicksort algorithm step-by-step.
In both cases, you want to first understand the algorithm, implement an initial version, design unit test, and try to add optimizations step-by-step. You want to keep track of the performance improvement for each component of your algorithm after each optimization. Eventually, you will have a chance to present your project in class, and submit a report.
For undergraduate students, you need to try at least one of the two (sequential and parallel) topics, and for graduate students, you need to do both.
| Event | Due Date |
|---|---|
| Proposal | 2/18 |
| Midway Report | 3/1 |
| Presentation | 3/7 or 3/9 |
| Final Report | 3/11 |