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)
* Proposeandreject algorithm for stable matching
 Greedy Algorithms (9 hours)
* Interval Scheduling
* Interval Partitioning
* Min Lateness Scheduling
* Cycle and Cut Properties for Min Spanning Trees
* UnionFind Data structure
* Shortest Paths: proof of correctness of Dijkstra
 DivideandConquer (6 hours)
* Medianofmedians
* Closest Pair of Points
* Fast Integer and Matrix Multiplication
 Dynamic Programming (6 hours)
* Parsing contextfree languages
* RNA secondary structure
* Edit distance
* Shortest Paths: BellmanFord
 Network Flows (6 hours)
* FordFulkerson Algorithm
* max flowmin cut theorem
* capacity scaling algorithm\EdmondsKarp algorithm
* max cardinality bipartite matching
* max number of edgedisjoint paths
 Polynomial Time Reductions and NPcompleteness (6 hours)
* classes P and NP
* NPcompleteness
 Approximation algorithms (3 hours)
* Traveling Salesman Problem: simple 2approximation 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.
 Final Exam (TWO SHEETS OF NOTES)  50%  07 December, 12:102:00 p.m.
(in WGHL (Wrigley Hall) 101)
The goal is to learn the material, and grades are meant to be reflective of how well you learned it. For this reason, the final exam is more heavily weighted, and is cumulative. If your percentage grade on the final exam exceeds that on
either or both tests, the final exam grade
replaces the lower test grade(s) in calculations of the final course grade.
You must write both tests in order for a grade to be eligible for replacement.
The final exam grade does not replace homework grades.
It is imperative that you make a legitimate attempt to answer all of the
homework questions. Any scaling of grades at the end of the course takes into
account the effort invested.
General Course Information:
Students may discuss homework
assignments with their classmates; however all work turned in is expected
to be that of the individual. If you have any questions regarding appropriate
collaboration please see the instructor.
More information is on the primary course web page.
We will follow the text closely, but the emphasis on the tests will be the same as that in the lectures. Hence, although class attendance is not required, it is highly recommended.