Parallel processors are everywhere: servers, desktops, tablets, even cell phones. However, writing programs that take advantage of all the available parallelism is challenging, in part because it requires different techniques than what we have learned in the sequential algorithms courses.
This course will teach how to design and analyze algorithms for parallel systems. The students will learn the techniques for designing and analyzing parallel algorithms for various parallel models of computation (shared memory, distributed memory, interconnection networks) and how these models relate to modern parallel systems, such as multicores, clusters and GPUs.
I am traveling during the first week of classes. So the first "real" lecture will not be until after the add date, if you are considering registering for the course after attending the first couple of lectures. Therefore, if you are wondering if this course is for you, I suggest you email me as soon as possible.
During the first week (in lieu of the lectures), there will be a takehome assessment exam, which will be posted on this webpage. The assessment exam will not be graded. The goal of the assessment exam is to give me and you (the student) an idea of how prepared you are to take the course and to adjust the course and topics approriately. Therefore, although the exam is not graded, to give an accurate picture of your preparedness, solve all the problems to the best of your ability. The exam should be individual effort, but you are allowed to use the CLRS textbook (standard text for undergraduate algorithms course). If you would like to hear feedback on your preparedness before the drop date, email me your exam before noon on Wednesday, August 24. Otherwise, it is due at 5pm on Friday, August 26, by email.
This is a course on advanced algorithmic concepts, so you should be very comfortable with asymptotic notation, design and analysis of basic algorithms, and the algorithms taught in an undergraduate algorithms course (most of the material from the CLRS textbook), hence, the 'B' or better requirement in ICS 311. If you are a graduate student who took an algorithms course outside of the UH system, email me with a brief description of the algorithms course(s) that you have taken (a link to the course webpage is a plus) and I'll provide you with an override to register for the course.
The following manuscript is also a good introduction to parallel algorithms:
The grade in the course will consist of the following components:
Content. The notes you write should cover all the material covered during the relevant lecture. Your notes should be understandable to someone who has not been to the lecture. You should write in full sentences where appropriate; point form (like I write on the board) is often too terse to follow without a sound track (though occasionally it is appropriate). Use numbered sections, subsections, etc. to organize the material hierarchically and with meaningful titles. If you feel it is appropriate, use nested bullets to organize material hierarchically even deeper. Try to preserve the motivation, difficulties, solution ideas, failed attempts, and partial results obtained along the way in the actual lecture.
Format. Write your notes using LaTeX, with figures in Encapsulated PostScript (generated from xfig, ipe, Adobe Illustrator or whatever you want). Start from the Latex template, which sets the style.
Timing. Try to write the lecture notes for a class on the same day while the material is fresh in your mind and it will save you time. You should finish the first draft of your notes and send it to me by two days after the lecture. Then I'll either send you comments via email or we'll schedule a meeting to go over your writeup, I'll make suggestions, you'll make a second pass, and send it to me. I'll make the final pass, and post it on the webpage. The goal will be to get the notes out by one week after the corresponding class.
There will be 35 homeworks (once every 23 weeks) throughout the semester. You may collaborate with anyone on the homeworks, but you must write up your own solutions. You must write the names of everyone you discussed the solution with in your homework writeup. The homework must be typed up. It will be due at the beginning of the lecture on the day it is due and can be either submitted in person in lecture (preferred) or emailed to me before the class.
Late Homeworks. Late homeworks can be emailed to me. Penalty for late homeworks is 33% of the maximum number of points within every 24 hours that it is late. For example, if homework is worth 30 points and is due at 10:30am on Wednesday, submitting it before Thursday 10:30am will result in deduction of 10 points; submitting it before Friday 10:30am, will result in deduction of 20 points; submitting it after Friday 10:30am will result in deduction of full 30 points, thus, are not worth anything. Extenuating circumstances do arise, therefore, a single homework will be accepted up to 48 hours late without any point deductions.
Goal. Ideal outcome of the project at the end of the class is for you to obtain results that can be published at an algorithms conference. To receive full credit on the project, you do not have to achieve this goal (that's the nature of research), but that should be your goal. If you do not achieve publishable results, your writeup should describe the ideas and approaches you took to solve the problem.
Topic. The topic of your research project should be related to parallel algorithms. I will be available for brainstorming during office hours for possible topic of interest. You must be interested in the topic, but I must approve the topic, so check with me first.
Format. Here is a list of possible formats of the project. This list is not exhaustive, so if you have an interesting idea that you don't see on the list below, come discuss it with me.
Writeup. The project must be written up in a research paper format. It should be somewhere between 6 to 15 singlespaced pages with 1 inch margins. It should start with a title, author and a 12 paragraph abstract. The body of the writeup should consist of introduction, the body and the conclusions. The introduction should describe the problem you are addressing, present a brief literature review of related results on the topic, and a summary of your results. The body should describe your solution, teachnique/approach to solving it and results. If you haven't achieved significant results, you should still describe the techniques/approaches you have tried and why they didn't work. The conclusions should summarize what you have presented and present possible directions for future research, e.g. open problems that remain unsolved and/or possible approaches that you might have tried if you had more time. You are welcome to collaborate on the project with anyone (even outside the class), including me, but you should give credit to people you have collaborated with. This is the nature of research.
Presentation. At the end of the semester you should give a 30 minute presentation about your project.
Specific topics will be filled in the schedule as they are covered during the semester.
Week  Day  Date  Topic  Scribe Notes  Notes 
1  Mon  Aug 22  NO CLASS (Nodari is at a conference): Takehome assessment exam  Due 5:00pm on Friday, August 26 (by email)  
Wed  Aug 24  NO CLASS (Nodari is at a conference): Finish the takehome assessment exam  
2  Mon  Aug 29  NO CLASS (Nodari is sick)  
Wed  Aug 31  Introduction to parallel algorithms  
3  Mon  Sep 5  HOLIDAY: Labor Day  
Wed  Sep 7  Models of parallel computation  Notes 02  Reading: [BM04, sections 1.1], [J92, section 1.11.3]  
4  Mon  Sep 12  Models of parallel computation (cont.) Brent's Theorem 
Notes 03  Reading: [BM04, sections 1.21.4], [J92, section 1.41.5] 
Wed  Sep 14  Work vs cost; Efficiency  Notes 04  Reading: [J92, section 1.51.6]  
5  Mon  Sep 19  Simmulation of CRCW PRAM on EREW PRAM  Notes 05  
Wed  Sep 21  Simple prefix sums  Notes 06  Reading: [HS86]  
6  Mon  Sep 26  Workefficient prefix sums  Notes 07  Reading: [J92, section 2.1][B93, sections 1.11.2] 
Wed  Sep 28  Segmented prefix sums  Notes 08  Reading: [B93, sections 1.4.1, 1.5] Homework 1 out 

7  Mon  Oct 3  Finding minimum  Reading: [J92, section 2.6]  
Wed  Oct 5  Partitioning; Simple workefficient merging  Notes 10  Reading: [J92, section 2.4]  
8  Mon  Oct 10  O(log log n) merging  Reading: [J92, section 4.14.2.3]  
Wed  Oct 12  Finish O(log log n) merging. Parallel Search Trees  Reading: [J92, section 2.5] Homework 1 due 

9  Mon  Oct 17  Pipelining, Pipelined Mergesort  Reading: [J92, sections 2.5, 4.3] Homework 2 out 

Wed  Oct 19  Pipelined Mergesort (cont.), Merging with covers  Reading: [J92, sections 4.2.4, 4.3.2]  
10  Mon  Oct 24  Pipelined Mergesort (cont.)  Reading: [J92, sections 4.2.4, 4.3.2]  
Wed  Oct 26  Pipelined Mergesort (cont.), Sorting Networks  Reading: [J92, sections 4.3.2, 4.4]  
11  Mon  Oct 31  01 Principle  Reading: [01 Notes, 01 Notes2]  
Wed  Nov 2  Bitonic Mergesort  Reading: [J92, section 4.4] Homework 2 due Homework 3 out 

12  Mon  Nov 7  List Ranking  Reading: [J92, section 3.1.1]  
Wed  Nov 9  NO CLASS (Nodari is traveling)  
13  Mon  Nov 14  Deterministic coin tossing, 3coloring of linked list  Reading: [J92, section 2.7]  
Wed  Nov 16  O(log n) List Ranking  Reading: [J92, section 3.1.2] Homework 3 due 

14  Mon  Nov 21  Euler Tour Technique. Problems on trees  Reading: [J92, section 3.2] Homework 4 out 

Wed  Nov 23  Tree contraction, arithmetic expression evaluation  Reading: [J92, section 3.3]  
15  Mon  Nov 28  Lowest Common Ancestor (LCA), Range Minima Queries (RMQ)  Reading: [J92, section 3.4]  
Wed  Nov 30  Connected Components, Minimum Spanning Tree  Reading: [J92, sections 5.15.2]  
16  Mon  Dec 5  Convex Hull  Reading: [J92, section 6.1] Homework 4 due 

Wed  Dec 7  Project presentations  Project due 