CSE 551 Fall 2015 Foundations of Algorithms Syllabus This document is available at http://www.public.asu.edu/~ccolbou/src/551syllabusf15.html

We cover most of chapters 1, 4, 5, 6, and 7, and selected topics from chapters 8, 11, and 13. Some of the topics in chapters 4, 5, and 6 have already been covered in CSE 310, so we focus on the new material in these chapters. We may also cover a few selected topics that are not covered by the textbook.

Below is a tentative schedule of topics, with lecture hours:

• Introduction (3 hours) * Propose-and-reject algorithm for stable matching
• Greedy Algorithms (9 hours) * Interval Scheduling * Interval Partitioning * Min Lateness Scheduling * Cycle and Cut Properties for Min Spanning Trees * Union-Find Data structure * Shortest Paths: proof of correctness of Dijkstra
• Divide-and-Conquer (6 hours) * Median-of-medians * Closest Pair of Points * Fast Integer and Matrix Multiplication
• Dynamic Programming (6 hours) * Parsing context-free languages * RNA secondary structure * Edit distance * Shortest Paths: Bellman-Ford
• Network Flows (6 hours) * Ford-Fulkerson Algorithm * max flow-min cut theorem * capacity scaling algorithm\Edmonds-Karp algorithm * max cardinality bipartite matching * max number of edge-disjoint paths
• Polynomial Time Reductions and NP-completeness (6 hours) * classes P and NP * NP-completeness
• Approximation algorithms (3 hours) * Traveling Salesman Problem: simple 2-approximation based on Min Spanning Trees * Load Balancing * Knapsack
Tests and reviews together occupy six further hours.

The grading for the class is as follows:

• Homework Assignments - five at 4% each - 20%
Always due at the start of class. Late submissions will not be accepted without documentation of a medical or family issue.
Homework 1 out 02 September, due 16 September, return 23 September. Solutions are here. (Questions 1, 3, and 5 graded.) Grades out of 30 are: 0 0 4 4 5 6 7 7 7 8 9 9 9 9 10 10 10 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 17 17 18 18 20 21 21 23 23 23 23 24 24 26 27 27
Homework 2 out 16 September, due 30 September, return 07 October. Solutions are here. (Questions 2, 3, and 4 graded.) Grades out of 30 are: 8 8 9 10 11 12 12 12 13 13 13 13 13 14 14 15 15 16 16 16 16 16 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 19 19 19 20 20 20 20 20 20 20 21 21 21 21 21 22 22 22 22 22 22 22 23 23 23 23 23 24 24 24 24 24 24 25 25 25 25 25 25 25 25 25 26 26 27 27 27 28 28 28 28 28 28 29
Homework 3 out 30 September, due 14 October, return 26 October. Solutions are here. Grades out of 30 are: 3 3 4 5 6 7 7 7 8 8 8 8 8 9 9 9 9 10 10 10 10 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 18 18 18 18 18 18 19 19 20 20 20 20 20 21 21 22 26
Homework 4 out 14 October, due 28 October, return 09 November. Solutions are here. Grades out of 30 are: 0 1 2 3 3 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 8 8 8 8 8 8 8 9 9 9 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 14 14 14 15 15 16 16 16 16 16 17 17 18 18 18 19 20 20 23 23 24 25
Homework 5 out 04 November, due 25 November, return 02 December. Solutions are here. Grades out of 30 are: 3 4 5 6 6 8 10 10 10 10 11 11 11 12 12 12 12 12 13 13 13 13 13 13 13 14 14 14 14 15 15 15 15 15 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 18 18 18 18 19 19 19 19 19 19 19 20 20 20 20 20 20 20 21 22 23 23 23 23 23 23 23 23 23 23 23 23 23 24 24 24 25 25 25 26 26 30 30 30
• Test 1 (Closed Book) - 15% - 05 October in class. Solutions and comments are here. The test was to be graded out of 40, but there were very few high grades. So treat it as a grade out of 30. Grades out of 30 are: 6 6 7 8 10 11 11 11 12 12 12 12 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 21 21 21 21 21 22 22 22 22 22 22 22 22 22 22 23 23 23 23 24 24 24 24 25 25 25 25 26 27 28 29 31 34. For the two students over 30, the extra points still count.
• Test 2 (Closed Book) - 15% - 02 November in class Solutions and comments are here. The test was to be graded out of 40, but there were very few high grades. So treat it as a grade out of 30. Grades out of 30 are: 7 8 9 9 9 10 10 10 11 11 11 11 11 11 11 11 12 12 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 16 16 16 16 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 20 20 20 21 21 21 21 21 21 22 22 22 23 23 23 24 25 26 26 26 27 28 28 28 31 32 34 34 38 For the five students over 30, the extra points still count.