CS214 Parallel Algorithm
Monday & Wednesday 4:00 – 4:50 PM Online (via Zoom)
Instructor: Yihan Sun -
Email : yihans@cs.ucr.edu Office Hour: TBA
TA: TBA
Course Information
The course covers basic concepts of parallel shared-memory algorithms such as theoretical models, scheduling, and concurrency. It addresses techniques for designing efficient parallel algorithms for computational problems in a variety of areas including sorting, searching, algebra, graph theory, data structures, computational geometry, and scheduling. It also includes implementing efficient parallel algorithms.
Lecture: 3 hours.
Prerequisite(s): CS 141 or equivalent courses; proficiency in C++.
Other Useful Tools
You could post your questions or problems you want to discuss on Campuswire.
All written homework solutions should be submitted via Gradescope.
Calendar:
Course Schedule
(This is a tentative scheduler, the final version may be different)
| Dates | Topic | Reading |
|---|---|---|
| Mon 03/29 | Introduction | TAPP § 3.1, 3.2 |
| Wed 03/31 | Background | TAPP § 5.1, 5.2, 13 |
| Fri 04/02 | Models | TAPP § 5.1, 5.2, 6, 17 |
| Mon 04/05 | Simple parallel arrays | TAPP § 13 |
| Wed 04/07 | Divide-and-conquer and solving recurrences | TAPP § 14 |
| Fri 04/09 | Sorting | TAPP § 14 |
| Mon 04/12 | Sorting | TAPP § 14 |
| Wed 04/14 | Concurrency | TAPP § 5 |
| Fri 04/16 | Deterministic Parallelism | [BFGS2012] |
| Mon 04/19 | Hash table | |
| Wed 04/21 | Parallel Binary trees | PA § 6 |
| Fri 04/23 | Parallel Binary trees | PA § 6 |
| Mon 04/26 | Parallel Binary trees | PA § 6 |
| Wed 04/28 | Midterm review | |
| Fri 04/30 | Midterm | |
| Mon 05/03 | Parallel Binary trees | PA § 6 |
| Wed 05/05 | Parallel Binary trees | PA § 6 |
| Fri 05/07 | Parallel graph algorithms | TAPP § 15, PA § 5 |
| Mon 05/10 | Parallel graph algorithms | TAPP § 15, PA § 5 |
| Wed 05/12 | Parallel graph algorithms | TAPP § 15, PA § 5 |
| Fri 05/14 | Parallel graph algorithms | TAPP § 15, PA § 5 |
| Mon 05/17 | Parallel graph algorithms | TAPP § 15, PA § 5 |
| Wed 05/19 | I/O efficient algorithms | |
| Fri 05/21 | I/O efficient algorithms | |
| Mon 05/24 | I/O efficient algorithms | |
| Wed 05/26 | Scheduling algorithms | TAPP § 19 |
| Fri 05/28 | review | |
| Mon 05/31 | Memorial Day - no class | |
| Wed 06/02 | Presentation (optional) | TAPP § 19 |
| Fri 06/04 | Presentation (optional) |
Some of the lecutues are marked with (*). This means that they are reviews for undergraduate algorithm courses (in particular, CS141 at UCR). Note that this does not mean that we'll learn these topics again in CS218. They are just to remind you the contents that you should already be familiar with. You need to make sure you have already learned them in previous courses.
Assignments and projects
Written Assignments
Here you can find sample code for writng solutions using LaTeX.
| Release Date | Due Date | Assignment |
|---|---|---|
| Mon 03/29 | Wed 04/14 11:59pm | Assignment 1 |
| Wed 04/14 | Fri 04/30 11:59pm | Assignment 2 |
| Fri 04/30 | Mon 05/17 11:59pm | Assignment 3 |
| Mon 05/17 | Wed 06/02 11:59pm | Assignment 4 |
| Fri 04/09 | Wed 04/28 11:59pm | Project 1 |
| Fri 04/23 | Wed 05/12 11:59pm | Project 2 |
| Mon 05/10 | Mon 05/31 11:59pm | Project 3 |
Policy
Grading
Assignments: 40%
Midterm: 15%
Final exam: 25%
Project: 20%
Presentation Bonus: 5%
Class Participation and other Bonus: 5%
Project
In this course, we have three projects, you need to choose two of them. If you work on all the three of them, you can get bonus points.
Presentation
At the end of the course, you can share your results of the projects (or other interesting topics) in the last two classes. This is optional (up to 5% bonus).
Programming
We will use C++ with CilkPlus for programming part. Please make sure you are familiar with C++.
Late Policy
You have 2 grace days to use across the quarter.
Plagiarism Warning
Cheating or plagiarism will NOT be tolerated!!!
Check UCR academic integrity for additional information.
You CAN get help from the instructors, TAs, textbooks (or relevant books), or the Internet, but must cite them. You can discuss homework problems with your classmates, but must acknowledge them. You CANNOT look at others' solution/code or share your solution/code with others. You CANNOT copy anything from the book or the Internet. When you write down your solution, it MUST be close-book.
Other Suggestions
- You need basic knowledge about algorithms, data structures, probabilistic, discrete math and programming. Courses such as CS141 or CS218 is helpful. If you don't have some basic background in algorithms, you should take these courses first. If you don't have such basic knowledge and you still want to take the course, you have to be aware that you need to spend more time on the course.
- Reading slides and the textbook before each lecture could be very helpful. All course material will be available online before class.
- You could participate in the discussions in Campuswire. Paying attention to other students' questions can also be helpful for yourself.
- Start working on homework assignments as early as possible. You have about 2 weeks for each of the homework assignment. However, don't start working on it on the last day. The homework problems can be hard and take a lot of time to finish.
- Please don't underestimate the time you will need to spend on this course. Especially if you don't have enough background in algorithm design, you need to spend much more time in this course.