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.