[Latex Template]

Please carefully read the Academic Integrity before you start working on the homework assignments.

Written Assignments

You must use LaTeX to prepare your solution. Here you can find sample code for writing solutions using LaTeX.

There will be both coding assignments and written assignments.

For written assignments (as well as exams), 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.

For coding assignments, you are expected to implement parallel code for a given task. Input/output of the problem will be specified. We will test your code on a multicore server at UCR, and your score will be based on 1) the running time of your code and 2) the clarity and completeness of your report in experimental study of your own code. You will be able to test your code on the same server.

All assignments and deadlines are listed on the course schedule

Projects

There will be two projects in this class.

Project 1: Parallel Sorting

In this project, you will implement a parallel sorting algorithm. In class, we will cover two sorting algorithms: parallel quicksort and parallel merge sort. We will also provide some relevant papers if you want to more advanced ideas or optimizations. You can choose to implement any algorithm you want, or you can design your own algorithm or creative optimizations to improve the performance!

There will be 15 points for Project 1, plus bonus points. 10 points will be based on your performance - the faster the code is, the higher points you get. The other five points will be based on the final report.

In this project, you will implement a parallel algorithm for graph Breadth-First Search (BFS). In class, we will cover the basic algorithm for BFS. More papers will be provided to help you get a better performance. Again, you can choose any algorithms and add any optimizations as long as you can achieve the best performance!

There will be 20 points for Project 2. 10 points will be based on your performance. Since Project 2 is more involved than Project 1, a mid-term report is required to help you track your progress. The midterm and final project are 5 points each.

How to write a good report?

For both projects, the quality of the report is important for you to get a high score. A good report should include:

  • Clearly describe your algorithms and optimizations, with reasonable motivations to use these methods.

  • Describe the efforts you tried to improve the performance, such as paper reading or finding ideas online.

  • Conduct in-depth experimental study of your algorithm by designing experiments to understand the performance bottlenecks, the effectiveness of each optimizations, etc.

  • Present experimental results to evaluate your algorithm with figures, tables, etc.

Paper Reading and Presentations

At the end of the class, you can choose to give a presentation on reading a recent research paper to get 3 bonus points of the class. The points will be assigned based on the presentation quality. If you are interested, you need to reserve a slot during Week 5. There can be at most one presenter for each paper. All papers are first-come first-serve.