CSE 341 / CSE 549, Fall 2014
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.

Admission Policy

Every one in the class starts out on a waiting list. During the first week of classes, there will be an exam and students will be admitted into the class based on their performance in this exam. This exam will test the following:
In a nutshell, if you were comfortable with the material taught in CSE 241 or in your undergraduate algorithms class, you will do fine in the test.

Instructors

Kunal Agrawal
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

Teaching Assistants

Jordyn Maglalang
Office Hours:   Friday 9 to 11 AM, Jolley 511

Robert Utterback
Office Hours:   Monday 10AM to Noon, Jolley 513

Autograder Czars

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

John Emmons
No Office Hours

Piazza

All enrolled students will be automatically signed up for the Piazza site. Please register as soon as you get your invitation. All questions (that are not of a personal nature) should be posted to Piazza. All questions emailed directly to the instructors or the TAs will receive the response "Please repost to Piazza," where both the question and the answer will reach its full audience. It is in everyone's interest that we maintain this policy; this is absolutely the most effective way to communicate.

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

Pre-requisites

CSE 131, CSE 241 and CSE 332 are strongly recommended. In particular, if you don't know the basics of C++, you should be confident that you can pick it up on your own.

Textbook

There is no textbook for the course, so you should be sure to come to every class and take notes. We may or may not provide course notes depending on the lecture.

Assignments

Please look at the course calendar for the exam and homework schedules. These may change as the class progresses, so check back frequently.

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.

Grading

For students enrolled in CSE 341:
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.

For students enrolled in CSE 549:
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.

Disability Resources

Students with disabilities or suspected disabilities are strongly encouraged to both bring any additional considerations to the attention of the instructors and make full use of the University's Disability Resource Center (http://disability.wustl.edu).

Academic Integrity and Collaboration Policy

The academic integrity policy is articulated in the collaboration handout. You are responsible for reading it and following it to the letter. Please contact the instructors or the TAs if you have any questions, preferably before the violation occurs.

Handouts

Useful Formulae
Master Method Cheat Sheet

Calendar

MondayTuesday WednesdayThursday 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

CSE 549 Assigned Readings