CS214 Parallel Algorithm
MWF    4:00 – 4:50 PM    Online (via Zoom)
Instructor: Yihan Sun   -    Email : yihans at cs.ucr.edu    Office Hour: 1-2pm Monday
Reader: Haide He (hehaide39 at gmail.com)
(This is a tentative scheduler, the final version may be different)
|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|
|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|
|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
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|
Final exam: 25%
Presentation Bonus: 5%
Class Participation and other Bonus: 5%
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.
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).
We will use C++ with CilkPlus for programming part. Please make sure you are familiar with C++.
You have 2 grace days to use across the quarter.
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.
- 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.