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

You can find all course material here

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.

For homework assignments:

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.
>>>>>>>>>>>>