This course will help you design and analyze algorithms and data structures. You will learn to ask and answer questions such as the following:

Given two alternative ways to solve the same problem, which is faster on the average?

Which is faster in the worst case?

Could there be a yet faster method?

How might a good algorithm for a new problem be found?

We will learn these skills in the context of working example problems, learning general tools along the way. In order to make our work reasonably concrete, we'll occasionally pause to code an algorithm up in Python, but our primary focus will be on design and analysis rather than programming implementation.

Due to the one-semester scope of this course, we won't be able to cover all the material in our textbook, and even that massive book doesn't cover the entire breadth of the field. Our emphasis will be on sequential algorithms for discrete, symbolic problems; we will cover parallel algorithms only lightly and won't discuss continuous, numeric problems at all. Also, we will primarily discuss algorithms that guarantee exact answers, spending only a few days on approximation algorithms for problems that are infeasible to solve exactly.

I will be available in my office (OHS 306) 10:30-11:20 on Mondays, Tuesday, Thursdays, and Fridays, as well as by appointment. Or try your luck: just stop by and see whether my door is open. You may send me electronic mail at max@gustavus.edu or call me at extension 7466. I'll try to put any updates to my office hours on my web page, so check there if in doubt.

The schedule shows a due date for each of the eight homework assignments. In order to receive any credit for a problem, you must submit a reasonable initial attempt at a solution by this due date. I will return graded homework as quickly as I can, but ordinarily with only a numerical grade, no comments. The reason why I don't write comments is because I want you to come talk with me face-to-face. If a problem needs more work, you should treat that as an invitation to come talk with me about it. Once you've done the additional work, you may turn in a revised solution for regrading. Please attach the graded original to your resubmission. All revised submissions are due one week after the original graded versions are returned to you. You are welcome to consult with me as many times as you like throughout the process of producing your initial submission, your revised submission, and even thereafter.

I am adopting my colleague San Skulrattanakulchai's policy on homework collaboration, which he describes as follows: "I encourage you to work with other students on the homework provided that you do so in such a way that every one in your group learns the material. The most effective way to do this is to first discuss each problem as a group and then have each person work on the problem individually. When you're done (or stuck) compare your work and discuss it. Remember that doing the homework is how you learn the material; and that you are not allowed to work cooperatively on tests.

"If you do work with other students on the homework, I would like you to follow these guidelines:

- Each person should write up the answers independently.
- Each person should be able to work each one of the problems independently.
- Each person gives credit to the others who helped."

There will be two intra-term tests as shown on the schedule below and a final exam as scheduled by the registrar. If you have a conflict with a testing time, please contact me as soon as possible to make an alternative arrangement.

Exams will be closed-book and mostly closed-notes. You may, however, use a
single 8 1/2 by 11 sheet of paper with **hand-written** notes for
reference. (Both sides of the sheet are OK.)

Any substantive contribution to your solution by another person or taken from a publication or online source should be properly acknowledged in writing. Failure to do so is plagiarism and will necessitate disciplinary action.

You are expected to be familiar with the college academic honesty honor code policy and to comply with that policy. If you have any questions about it, please ask.

You will earn up to 200 grade points for your work on homework and tests, divided as follows. Each of the 8 homeworks will be graded on a scale of 12 points, totaling 96 points. Each of the two tests that happens during the semester, in class, will be graded on a scale of 32 points, for 64 more points. The remaining 40 points will come from the comprehensive final exam. In addition to these 200 points, you can earn extra-credit points as described in separate guidelines. Your course grade will be recorded as follows:

Points | Grade |
---|---|

185-200 | A |

178-184 | A- |

171-177 | B+ |

165-170 | B |

158-164 | B- |

151-157 | C+ |

145-150 | C |

138-144 | C- |

131-137 | D+ |

118-130 | D |

000-117 | F |

Please point out any arithmetic or clerical error I make in grading, and I will gladly fix it. You may also request reconsideration if I have been especially unjust.

Gustavus Adolphus College is committed to ensuring the full participation of all students in its programs. If you have a documented disability (or you think you may have a disability of any nature) and, as a result, need reasonable academic accommodation to participate in class, take tests or benefit from the College's services, then you should speak with the Disability Services Coordinator, for a confidential discussion of your needs and appropriate plans. Course requirements cannot be waived, but reasonable accommodations may be provided based on disability documentation and course outcomes. Accommodations cannot be made retroactively; therefore, to maximize your academic success at Gustavus, please contact Disability Services as early as possible. Disability Services (https://gustavus.edu/advising/disability/) is located in the Advising and Counseling Center.

Support for English Language Learners (ELL) and multilingual students is available via the College's ELL Support staff person, Andrew Grace (agrace@gustavus.edu or x7395). He can meet individually with students to consult about academic tasks and to help students seek other means of support. In addition, ELL and multilingual students can seek help from peer tutors in the Writing Center. Please let me know if there is any accommodation in the course that would enable you to more fully show your abilities; for example, I would consider allowing extra time on tests, as well as allowing a dictionary in an otherwise closed-book test.

Date | Reading | Topic | Due |
---|---|---|---|

9/6 | Introduction | ||

9/8 | 1-3 | Asymptotics | |

9/9 | 4.0-4.5 | Divide and conquer | |

9/12 | Divide and conquer, continued | ||

9/13 | 5.0-5.3 | Probabilistic analysis | |

9/15 | 6.0-6.4 | Heapsort | |

9/16 | 6.5 | Priority queues | |

9/19 | 7.0-7.3 | Quicksort | HW1 |

9/20 | 7.4 | Analysis of quicksort | |

9/22 | 8.0-8.2 | Sorting in linear time | |

9/23 | 8.3 | Radix sort | |

9/26 | 9.0-9.2 | Medians and order statistics | HW2 |

9/27 | 11.0-11.3.2 | Hash tables | HW1 rewrite |

9/29 | 12.0-12.3 | Binary search trees | |

9/30 | 13.0-13.2 | Red-black trees | |

10/3 | 13.3 | Insertion in red-black trees | HW3 |

10/4 | No class (attend Nobel Conference) | ||

10/6 | Discussion | HW2 rewrite | |

10/7 | Review | ||

10/10 | Intra-term test 1 (take home) | ||

10/11 | 14 | Augmenting data structures | test 1 |

10/13 | 15.0-15.1 | Rod cutting | HW3 rewrite |

10/14 | 15.2 | Matrix-chain multiplication | |

10/17 | 15.3 | Dynamic programming | |

10/18 | 15.4 | Longest common subsequence | HW4 |

10/20 | 16.0-16.2 | Greedy algorithms | |

10/21 | 16.3 | Huffman codes | |

10/24 | No class (reading day) | ||

10/25 | No class (reading day) | ||

10/27 | 17.0-17.3 | Amortized analysis | HW4 rewrite |

10/28 | 17.4 | Dynamic tables | HW5 |

10/31 | 18.0-18.2 | B-trees | |

11/1 | 18.3 | Deleting from a B-tree | |

11/3 | Skip lists | ||

11/4 | Skip lists, continued | HW6 | |

11/7 | Skip lists, continued | HW5 rewrite | |

11/8 | 21.0-21.3 | Disjoint-set data structures | |

11/10 | Catch up | ||

11/11 | Review | ||

11/14 | Intra-term test 2 (take home) | HW6 rewrite | |

11/15 | 22.0-22.2 | Breadth-first search | |

11/17 | 22.3-22.4 | Depth-first search; topological sort | test 2 |

11/18 | 23 | Minimum spanning trees | |

11/21 | 24.0-24.2 | Single-source shortest paths; Bellman-Ford | |

11/22 | Extra office hour | ||

11/24 | No class (Thanksgiving) | ||

11/25 | No class (Thanksgiving) | ||

11/28 | 24.3 | Dijkstra's algorithm | |

11/29 | 25.0, 25.2 | All-pairs shortest paths; Floyd-Warshall | HW7 |

12/1 | The Floyd-Warshall algorithm, continued | ||

12/2 | 27.0-27.1 | Dynamic multithreading | |

12/5 | 27.2-27.3 | Multithreaded algorithms | |

12/6 | 35.0-35.1 | Approximation algorithms; vertex cover | HW8 |

12/8 | 35.5 | The subset-sum problem | HW7 rewrite |

12/9 | The subset-sum problem, continued | ||

12/12 | Catch up | ||

12/13 | Review; evaluation | ||

12/15 | No class (reading day) | HW8 rewrite |

Course web site: http://gustavus.edu/+max/courses/F2011/MCS-375/

Instructor: Max Hailperin <max@gustavus.edu>