<A NAME="title"></A> QUEEN'S UNIVERSITY <BR>

QUEEN'S UNIVERSITY

SCHOOL OF COMPUTING
Parallel Algorithms
CISC-872
Fall Term 2016
http://www.cs.queensu.ca/home/akl/cisc872/2016/info16.html

This page provides information on the course. It tells you about the instructor, course schedule, and method of grading. It also contains a course description, textbook title, and some important dates. Practice problems can also be found here.

Instructor and Schedule

The instructor of this course is:

Instructor Office E-mail Phone
Selim Akl 520 Goodwin Hall akl@cs.queensu.ca 33184

One session per week is scheduled for this course as follows:

Day Time Place
Thursday 11:00 a.m. - 1:30 p.m. Goodwin Hall 521

Office Hours

I will be glad to meet with you any time you need to see me in my office. Please talk to me in class to arrange an appointment.

Back to top

Grading

Your grade is the total of marks obtained as follows:

Component Percentage
Participation 60
Final Exam 40
Final Grade 100

Course Description

The design and analysis of parallel algorithms. Computational models. Complexity classes. Parallel algorithms for various problems including: basic arithmetic, sorting, searching, selection, graph theory, matrix computations, combinatorial enumeration, optimization, computational geometry, numerical analysis.

Prerequisite

An undergraduate course on the design and analysis of algorithms.

Back to top

Textbook

S.G. Akl, Parallel Computation: Models and Methods, Prentice Hall, Upper Saddle River, New Jersey, 1997.

Relevant chapters are indicated in the course outline below.

Calendar

Week Date Chapters To Read/Assignment Due
1 Sept 15 Introduction
2 Sept 22 Models of Computation/Assignment 1
3 Sept 29 Combinational Circuits/Assignment 2
4 Oct 6 Parallel Prefix/Assignment 3
5 Oct 13 Divide and Conquer/Assignment 4
6 Oct 20 Pointer-Based Data Structures/Assignment 5
7 Oct 27 Linear Arrays and Meshes/Assignment 6
8 Nov 3 Hypercubes and Stars/Assignment 7
9 Nov 10 Models Using Buses/Assignment 8
10 Nov 17 Broadcasting with Selective Reduction/Assignment 9
11 Nov 24 Parallel Synergy/ Assignment 10
12 Dec 1 Assignment 11

Back to top

Assignments

Below is a list of problems from the textbook. Solutions to these problems will be presented by you in class.

  1. Assignment 1: 1.16
  2. Assignment 2: 2.6, 2.8, 2.9
  3. Assignment 3: 3.22
  4. Assignment 4: 4.20, 4.22
  5. Assignment 5: 5.16
  6. Assignment 6: 6.4
  7. Assignment 7: 7.6, 7.15, 8.10, 8.12, 8.15, 8.16, 8.26
  8. Assignment 8: 9.2, 9.7
  9. Assignment 9: 10.4, 10.16, 10.24, 10.26, 10.45
  10. Assignment 10: 11.6, 11.9, 11.12
  11. Assignment 11: 12.17, 12.23

Back to top

Final

This will be a two-hour written, `closed-book', exam. No electronic devices will be allowed. The details are as follows:

Date Time Place
Thursday, December 8, 2016 12:00 - 2:00 Goodwin 521

Recommended reading

An example illustrating the memory access unit for the Broadcasting with Selective Reduction model of computation is available here.

Back to top