CSE 638-01 (#49403), AMS 641-01 (#50557): Advanced Algorithms, Spring 2013

Lecture Time and Location. TuTh 2:30 pm - 3:50 pm, Melville Library W4540, West Campus

Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. TuTh 12:30 pm - 2:00 pm, 1421 Computer Science Building

TA. Vikas Ganjigunte Ashok (vganjiguntea{at}cs{dot}stonybrook{dot}edu)
Office Hours. Tu 4:00 pm - 5:00 pm, 2110 Computer Science Building (TA Room)

Course Description. We will explore various topics in the following three areas:

  1. Parallel algorithms (for shared- and distributed-memory architectures)
  2. Randomized algorithms
  3. External-memory, cache-efficient and cache-oblivious algorithms
The course will include both theoretical and programming components.

The course will be supported by an educational grant from XSEDE (Extreme Science and Engineering Discovery Environment). We will use the computing resources provided by XSEDE for homework problems and projects.

Prerequisites. Background in algorithms analysis (e.g., CSE 548) and programming languages (e.g., C/C++) is required (or consent of instructor).

Textbooks. All are recommended, but none is required.

  1. Ananth Grama, George Karypis, Vipin Kumar, and Anshul Gupta. Introduction to Parallel Computing (2nd Edition), Addison Wesley, 2003.
  2. Joseph JáJá. An Introduction to Parallel Algorithms (1st Edition), Addison Wesley, 1992.
  3. Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms (3rd Edition), MIT Press, 2009.
  4. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms (1st Edition), Cambridge University Press, 1995.
  5. Jeffrey S. Vitter. Algorithms and Data Structures for External Memory, Series on Foundations and Trends in Theoretical Computer Science, Now Publishers, Hanover, MA, 2008.
  6. Ulrich Meyer, Peter Sanders, and Jop Sibeyn (Editors). Algorithms for Memory Hierarchies: Advanced Lectures (1st Edition), Lecture Notes in Computer Science, Springer, 2003.

Course Requirements. There will be 3 homework assignments, one in-class final exam, and one project. Each student will be responsible for scribing one lecture. The course grade will be based on the following.

Download the Latex template for scribe notes.

Blackboard. Some course documents (e.g., scribe notes, homework solutions, etc.) will be available through Blackboard.

Lecture Schedule.

Date Topic Notes / Reading Material
Tue, Jan 29 Introduction -
Thu, Jan 31 Analytical Modeling of Parallel Algorithms
Tue, Feb 5 Analytical Modeling of Parallel Algorithms ( Continued )
  • Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Feb 7 Analytical Modeling of Parallel Algorithms ( Continued )
Tue, Feb 12 The Cilk++ Concurrency Platform
Thu, Feb 14 Analysis of a Work Stealing Scheduler
Tue, Feb 19 Analysis of a Work Stealing Scheduler ( Continued )
Thu, Feb 21 Parallel Quicksort and Selection
  • Chapter 2 (Basic Techniques), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
  • Chapter 9 (Randomized Algorithms), Section 9.6.3 (A Parallel Randomized Quicksort Algorithm), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
  • HW1 out
Tue, Feb 26 Parallel Quicksort and Selection ( Continued )
  • Chapter 4 (Searching, Merging, and Sorting), Section 4.5 (Selection), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
Thu, Feb 28 Parallel Connected Components
  • Chapter 2 (Basic Techniques), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
  • Guy E. Blelloch and Bruce M. Maggs, “Parallel Algorithms” (Section 4.3), The Computer Science Handbook, Editor: Allen Tucker, Chapman & Hall/CRC, 2004.
Tue, Mar 5 Parallel Connected Components
( Continued )
-
Thu, Mar 7 Parallel Minimum Spanning Trees (and Radix Sort & Counting Sort)
Tue, Mar 12 Parallel Minimum Spanning Trees (and Radix Sort & Counting Sort)
Thu, Mar 14 Parallel Maximal Independent Set
Tue, Mar 19 Spring Break -
Thu, Mar 21 Spring Break -
Tue, Mar 26 Parallel Maximal Independent Set ( Continued )
Thu, Mar 28 "Resilient Algorithms"
by Anirban Mitra and Akassh Mishra
( Part 1 and Part 2 )
-
Tue, Apr 2 Project Progress Report ( Presentation ) -
Thu, Apr 4 Project Progress Report ( Presentation ) -
Tue, Apr 9 Project Progress Report ( Presentation ) -
Thu, Apr 11 "Streaming Algorithms"
by Ajinkya Potdar and Hemanga Borah
( Entire Presentation )
-
Tue, Apr 16 Analyzing I/O and Cache Performance
Thu, Apr 18 Analyzing I/O and Cache Performance ( Continued ) -
Tue, Apr 23 Cache-efficient Searching and Sorting
  • Chapter 9 (Cache Oblivious Algorithms) by Piyush Kumar, Algorithms for Memory Hierarchies: Advanced Lectures (1st Edition), Ulrich Meyer, Peter Sanders, and Jop Sibeyn (Editors), Lecture Notes in Computer Science, Springer, 2003.
  • Alok Aggarwal and Jeffrey S. Vitter, “The input/output complexity of sorting and related problems”, Communications of the ACM, 31(9), pp. 1116-1127, 1988.
  • Chapter 3 (A Survey of Techniques for Designing I/O-Efficient Algorithms) by Anil Maheshwari and Norbert Zeh, Algorithms for Memory Hierarchies: Advanced Lectures (1st Edition), Ulrich Meyer, Peter Sanders, and Jop Sibeyn (Editors), Lecture Notes in Computer Science, Springer, 2003.
  • HW3 out
Thu, Apr 25 Cache-efficient Searching and Sorting ( Continued )
  • Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran, “Cache-Oblivious Algorithms”, Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 285-298, 1999.
Tue, Apr 30 Cache-oblivious Priority Queue with Decrease-Keys
Thu, May 2 Cache-oblivious Priority Queue with Decrease-Keys ( Continued )
  • Lecture slides on amortized analysis.
Tue, May 7 - -
Thu, May 9 Final Exam -

Homeworks.

Exam.