Parallel Algorithms

Instructor Textbooks Schedule Class Format Course Work Test Correction
Labs Deadlines Collaboration Grading SR Notes

This course introduces algorithms based upon multi-processor environments, with an emphasis on fundamental problem-solving techniques. Specific algorithms will be developed for shared-memory machines, called parallel random access machines (PRAMs), and will address representative problems, in such areas as lists, trees, searching, sorting, graphs, geometry, and strings.

Beyond the PRAM model of computation, multi-process environments often must consider such implementation issues as concurrent accessing of shared data and critical sections of code. This course also will discuss solutions to such issues using semaphores, monitors, or message passing.

Selected algorithms will be implemented on the department's network, using the SR parallel programming language. SR follows a C-like syntax, providing a wide range of parallel constructs. With very few changes, an SR program can move from a single processor environment to a network, with the programmer controlling what runs where.


Henry M. Walker

Office: Science 2420
Telephone: extension 4208
Office hours are posted weekly on the bulletin board outside my office.
Additional hours can be scheduled by appointment.
If you wish, you may reserve a half hour meeting by signing up on the weekly schedule.


Joseph JáJá, An Introduction to Parallel Algorithms,. Addison-Wesley, 1992.

Stephen J. Hartley, The SR Programming Language: Operating Systems Programming,Oxford University Press, 1995.

The schedule

The class is scheduled to meet 10:00-noon on Tuesdays and 10:00-11:00 am on Thursdays, from January 20 through March 14 and from March 31 through May 9.

While the schedule for this course is expected to evolve, a Tentative Class Schedule is available.

Class Format

This course will take advantage of the asymmetric nature of its meeting time (Group B: Tuesdays 10-noon and Thursdays 10-11) by experimenting with several class formats.

Course Work

Course Work will involve a combination of the following activities.

  1. Exercises: Written exercises will be assigned to clarify and expand upon algorithms described in class or covered in the text. Students will be exempted from the written exercises based on the material from their presentations. Written exercises normally will be due on Thursdays.

  2. Discussion Preparation: As noted under ``Student-Led Discussions'' above, some classes will require students to present the idea motivating an algorithm or an example. On such days, a statement of an algorithm's idea and a worked out example will be due at the start of class. (These statements will be counted as part of the written work for the course.)

  3. Programs: Several programming problems will be assigned throughout the semester.

  4. Laboratory Exercises: will be due one week after they have been started in class. Thus, labs started one Tuesday will be due at the start of class on the following Tuesday.

  5. Tests/Exam: Two hour tests are scheduled for Thursday, February 27, and Thursday, April 17. Following the published exam schedule, an exam is scheduled for 2:00 pm on Wednesday, May 14.

  6. Student Talks: As noted under Student Presentations above, each student will collaborate in presenting two algorithms to the class.

Late Penalty: Work is due at the start of class on the date specified in the assignment. A penalty of 33 1/3 % per class meeting will be assessed on any work turned in late, even work submitted at the end of a class.} Thus, work turned in 4 days late will be weighted -33 1/3 %; since a negative score reduces a semester total, it is better not to turn the work in at all.
Exception: Deadlines for programming problems and laboratory exercises are automatically extended at least one class day if the HP network is down for an unscheduled period of 3 or more hours during the week preceding the assignment due date. (In such cases, however, deadlines for written assignments are not extended.)

Absolute Deadline: All homework must be turned in by Thursday, May 8 at 5:00 pm.


The work in this course is split between individual and group work. Students are encouraged to work together on laboratory exercises, discussion preparation, and oral presentations (i.e., please collaborate on course work 2, 4, and 6 above). However, since this course seeks to enable students to develop their own parallel algorithms, collaboration is not allowed on written assignments, programs, or tests (i.e., do NOT collaborate on course work 1, 3, and 5 above).


The final grade will be based upon each student's demonstration of his or her understanding of and facility in programming, not on the performance of the class as a whole nor on a strict percentile basis. While some flexibility may be possible in determining a final semester grade, the following scheme approximates the relative weights attached to various activities in this course.
Exercises/Summaries: 15% Labs: 30% Hour Tests: 25%
Oral Presentations: 10% Exam: 20%

This document is available on the World Wide Web as

created January 10, 1997
last revised January 10, 1997