COMP 312: Parallel and Sequential Algorithms

Dan Licata Spring, 2017


In this course, you will learn to design, analyze, and program sequential and parallel algorithms and data structures. The emphasis is on fundamental algorithmic concepts applicable across a wide variety of problem domains, and transferable across a reasonably broad set of programming languages and computer architectures. We will in general consider parallel algorithms, those that do multiple things at once, viewing sequential algorithms as a special case. The course includes a significant programming component in which you will program concrete examples from domains such as engineering, scientific computing, graphics, data mining, and information retrieval. By the end of the course, we expect you to:
  1. differentiate between problems and algorithms. A problem defines an interface while an algorithm defines a particular method to solve the problem. For example, quicksort is an algorithm to solve the sorting problem. Being able to cleanly define a problem is key in the process of putting together large programs and in reusing their components. Similarly, we distinguish between abstract data types and particular data structures that implement them.
  2. know and be able to apply a toolbox of algorithm design techniques, such as reduction, inductive techniques (contraction, divide and conquer, dynamic programming, greediness), and randomization. We also expect you to know and be able to apply a toolbox of abstract data types, such as sequences, sets and tables, and graphs, as well as implementations thereof.
  3. analyze performance in terms of work, span, and space using big-O asymptotics. We cover a variety of techniques for analyzing asymptotic performance including solving recurrences, randomized analysis, and counting arguments.

Prerequisites: COMP 211, COMP 212, and MA 228.


There will be two lectures per week, Tu-Th 1:20pm-2:40pm in Exley 109. This time will be used for chalk-board lectures, for interactively coding as a whole class, and possibly for small-group or individual work. Lectures will be your primary source of information for the course, and attendance is strongly encouraged. The textbook we will use is Algorithms: Parallel and Sequential.

There will be one- to two-week-long written and programming assignments. Homeworks are designed to help you internalize the course material; they consist of written problems and short to medium-sized programming tasks. No credit will be given for homework handins that do not compile. If you cannot make it to class for some reason, you may drop the HW off at Dan's office, Exley 633. No late homeworks will be accepted, except by permission of instructor.

There will be an in-class midterm and final exam. As the only completely non-collaborative type of assignment in the course, exams account for a significant portion of your grade. However, lest that sound too scary, the exams will not ask you to learn new skills, just to demonstrate that you have acquired the skills we ask you to practice in homeworks.


Your grade will be based on homework assignments (55%), a midterm exam (20%), a final exam (20%), and class participation (5%). (Percentages are subject to change.) Generally, 90%-100% should be interpreted as A work, 80-90% as B, 70-80% as C, 60-70% as D, and below that as failing. However, the instructor may adjust the final letter grade boundaries (in either direction) at the end of the semester, to account for differences between the intended and actual difficulty of the assignments. Assignments will be graded for correctness, clarity, and efficiency.