ECS 223 - Parallel Algorithms

CRN #72973

Lecture: Tues-Th, 10:30-11:50 pm, 1062 Bainer

TA: Stewart He

Stewart's Office Hours: Tu 8:30-10:30 am, Fri 8-10 am, 55 Kemper.

Prof. Amenta's Office Hour: Mon 4-5 pm, 2123 Kemper Hall

Prerequisites: ECS 222A. This can be waived with the consent of instructor; a good grounding in undergraduate algorithms should be sufficient, especially for someone with parallel programming experience.

Introduction

This is a theoretical course in parallel algorithms. We will cover algorithms for searching and sorting, numerical computations, lists and trees, geometry, and other topics.

Our main focus will be the analysis of algorithms, that is, proving upper and lower bounds on running time, total work, and/or communication. We will work mainly with the PRAM model and its extensions, and also Bulk Synchronous Processing (BSP).

We will critique both algorithms and models by considering how well they reflect real parallel computing platforms and the programming models presented by languages such as CUDA, Hadoop/Map-Reduce, or Pregel.

Textbook


Textbook: An Introduction to Parallel Algorithms, by Joseph JaJa. We will have readings in this book to prepare for class discussions and we will do some of the exercises as homework.



Other Online Resources:
  • Parallel Algorithms, by Guy Blelloch and Bruce Maggs.
  • Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, by Uzi Vishkin.
  • Mining of Massive Datasets, by Jure Leskovec, Anand Rajaraman and Jeff Ullman. Good material on MapReduce/Hadoop, and algorithms for that programming model.
  • Programming on Parallel Machines, Prof. Matloff's book for his course on parallel programming, ECS 158. This is a good reference for real programming models.
  • There will also be occasional research papers and handouts.

  • Format

    We will run this like a seminar course. There will be a reading assignment due before most class meetings. The class meetings will focus on discussion. For all the readings, there will be short-answer questions which have to be answered in writing, in class on the day that the reading is due. This is to ensure that everyone does the reading and we can have a meaningful discussion.

    There will be three problem sets, to provide practice in algorithm design and analysis, as well as writing.

    There will be two in-class midterms, one in the middle of the quarter and one towards the end. There will not be a final.

    Grading

    Grades will be determined using this formula (approximately):

    Reading questions 15%
    Homework 30%
    Midterm1 20%
    Midterm2 25%
    Attendance, preparation and participation 10%

    Reading, reading questions, and lectures

    Readings and reading questions.

    Homework

    While you are encourged to discuss the homework with each other, you must a) write up your own solutions, in your own words, and b) report, in your solutions, who you discussed the problems with and what other sources (papers, Web, books, etc) you used to arrive at the solution. We are mainly concerned with seeing that you understand the solutions.