Parallel and Sequential Algorithms

Welcome to the course homepage of CSE 341 / CSE 549!

Class meets Mondays and Wednesdays, 2:30 to 4 PM for both CSE 341 and 549
in Green Hall L0160. For students enrolled in CSE 549, there is an additional
class on every Friday, 2:30 PM to 4:00 PM, in Whitaker 218.

- basic algorithmic concepts, such as recursion, divide and conquer;
- simple algorithms, such as quick sort, merge sort, etc; and
- basic mathematical concepts used in the analysis of algorithms, such as asymptotic notation, solving recurrences using master method and recursion tree, induction, and basic discrete probability.

Office Hours: Wednesdays 4 to 5:30 PM, Jolley 508

Email: kunal AT cse.wustl.edu

I-Ting Angelina Lee

Office Hours: Wednesdays 4 to 5:30 PM, Jolley 508

Email: angelee AT cse.wustl.edu

Office Hours: Friday 9 to 11 AM, Jolley 511

Robert Utterback

Office Hours: Monday 10AM to Noon, Jolley 513

Office Hours: Thursday 3 to 4 PM, Jolley 508 (for coding and autograder questions)

John Emmons

No Office Hours

The Piazza page for this class is located at https://piazza.com/wustl/fall2014/cse341cse549/home

You have a total of 4 late days per semester at no grade penalty. At most two days late may be used per assignment. If you have used up these four late days, your score will be reduced by 25% off of the total (not yours) score per late day.

There are 4 homeworks and 2 exams. Each homework is worth 10 points, for a total of 40 points. Each exam is worth 30 points for a total of 60 points.

The students enrolled in the graduate course have the same homework assignments and exams. Each homework is worth 5 points for a total of 20 points. Each exam is worth 20 points for a total of 40 points.

In addition, students enrolled in 549T must attend recitations on Fridays, where everyone is required to prepare a lecture based on the assigned paper readings. The lecture you prepare is worth 10 points. Graduate students will work on a final project of their choice, in a group of 2--4 (TBD), and the final project is worth 30 points.

Master Method Cheat Sheet

Monday | Tuesday | Wednesday | Thursday | Friday |

Aug 25 L1: Introduction |
Aug 26 |
Aug 27 L2: Genome Sequencing Assigned: Homework 0 |
Aug 28 |
Aug 29 R1: Final Project Discussion |

Sept 01 Holiday |
Sept 02 |
Sept 03 L3: Cost Model: Work, Span, and Parallelism |
Sept 04 |
Sept 05 R2: Work Stealing Analysis (Presenter: Robert Utterback) |

Sept 08 L4: Matrix Multiplication Due: Homework 0 Assigned: Homework 1 |
Sept 09 |
Sept 10 L5: Divide and Conquer Algorithms |
Sept 11 |
Sept 12 R3: Cache Complexity of Matrix Multiplication (Lecture) |

Sept 15 L6: Merge Sort |
Sept 16 |
Sept 17 L7: Parallel Scan and its Applications |
Sept 18 |
Sept 19 R4: Cache Oblivious Algorithms (Presenter: Chao Wang) |

Sept 22 L8: More Scan and Quicksort Due: Homework 1 Assigned: Homework 2 |
Sept 23 |
Sept 24 L9: Dynamic Programming I |
Sept 25 |
Sept 26 R5: Cache Oblivious and Cache Aware Sort (Presenters: Jordyn Maglalang and Qi Han) |

Sept 29 L10: Dynamic Programming II |
Sept 30 |
Oct 01 L11: Collect, Map Reduce, and ADT |
Oct 02 |
Oct 03 R6: The Data Locality of Work Stealing (Presenters: Shaurya Ahuja and Son Dinh) |

Oct 06 Midterm Review Due: Homework 2 Assigned: Homework 3 |
Oct 07 |
Oct 08 Midterm Exam |
Oct 09 |
Oct 10 R7: Sequential Consistency and Linearizability (Lecture) |

Oct 13 L12: Bellman Ford and Johnson's Algorithms |
Oct 14 |
Oct 15 L13: Johnson's contd. and Floyd-Warshall |
Oct 16 |
Oct 17 Holiday Due: Final Project Proposal |

Oct 20 L14: Graph Contraction and Strongly Connected Components |
Oct 21 |
Oct 22 L15: More Graph Contraction |
Oct 23 |
Oct 24 R8: Concurrent Data Structures (Presenters: Li Zheng and Siyao Lu) |

Oct 27 L16: Minimum Spanning Tree and Maximal Independent Set Due: Homework 3 Assigned: Homework 4 |
Oct 28 |
Oct 29 L17: Maximal Independent Set Continued and HP Bounds |
Oct 30 |
Oct 31 R9: Reducer Hyperobjects (Presenters: Grant Schmedake) |

Nov 03 L18: Parallel Breadth-First Search |
Nov 04 |
Nov 05 L19: Treap I |
Nov 06 |
Nov 07 R10: Parallel BFS with Bag Reducers (Presenter: Shane Carr) |

Nov 10 L20: Treap II |
Nov 11 |
Nov 12 L21: Last of Treap and Max Flow |
Nov 13 |
Nov 14 R11: Final Project Presentations |

Nov 17 L22: Max Flow Due: Homework 4 |
Nov 18 |
Nov 19 L23: Cache Complexity |
Nov 20 |
Nov 21 R12: Final Project Presentations |

Nov 24 Class Cancelled |
Nov 25 |
Nov 26 Pre-Turkey Day |
Nov 27 |
Nov 28 Post-Turkey Day |

Dec 01 Final Review |
Dec 02 |
Dec 03 Final Exam |
Dec 04 |
Dec 05 No Class Due: Final Project Write-up |

- Recitation 2:

Scheduling Multithreaded Computations by Work Stealing, Sections 1--3, and 7

Thread Scheduling for Multiprogrammed Multiprocessors, Sections 1, 2, 3.1, 3.4, 4.1--4.3, and 5--6

- Recitation 4:

Cache-Oblivious Algorithms, Sections 1--3 and 6--8

- Recitation 5:

Cache Oblivious Funnelsort, Section 4

Cache Oblivious and Cache Aware Sort, Sections 1, 2 (Sorting), 3 (Sorting), and 5 (Mergesort and Distribution sort)

- Recitation 6:

The Data Locality of Work Stealing

- Recitation 8:

Michael-Scott Concurrent Queue

- Recitation 9:

Reducers and Other Cilk++ Hyperobjects

- Recitation 10:

A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers)