Syllabus for MCS-375: Algorithms (Fall 2011)

Overview

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

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.

Office hours

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.

World Wide Web

All course materials will be available through my World Wide Web page. The URL for this course is https://gustavus.edu/+max/courses/F2011/MCS-375/. After this syllabus I will give hardcopy handouts only to those students who want them.

Text

Our text will be the third edition of Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, published by The MIT Press.

Homework assignment policy

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:

Tests

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.)

Honor

Students are encouraged to discuss the course, including issues raised by the assignments. However, the solutions to assignments should be individual original work unless you indicate otherwise in accordance with the policy for collaborative homework stated above. In your discussions with other students, remember that your primary goal needs to be building your understanding, not just getting the assignment done.

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.

Grading

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:

PointsGrade
185-200A
178-184A-
171-177B+
165-170B
158-164B-
151-157C+
145-150C
138-144C-
131-137D+
118-130D
000-117F

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.

Style guidelines

All assignments should be readily readable and should not presuppose that I already know what you are trying to say. Use full English sentences and clear diagrams, programs, etc. Remember that your goal is to communicate clearly and that the appearance of your work plays a role in this communication process. You may submit your homework by email or as stapled hardcopy with your name on it.

Accessibility

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.

Schedule

DateReadingTopicDue
9/6Introduction
9/81-3Asymptotics
9/94.0-4.5Divide and conquer

9/12Divide and conquer, continued
9/135.0-5.3Probabilistic analysis
9/156.0-6.4Heapsort
9/166.5Priority queues

9/197.0-7.3QuicksortHW1
9/207.4Analysis of quicksort
9/228.0-8.2Sorting in linear time
9/238.3Radix sort

9/269.0-9.2Medians and order statisticsHW2
9/2711.0-11.3.2Hash tablesHW1 rewrite
9/2912.0-12.3Binary search trees
9/3013.0-13.2Red-black trees

10/313.3Insertion in red-black treesHW3
10/4No class (attend Nobel Conference)
10/6DiscussionHW2 rewrite
10/7Review

10/10Intra-term test 1 (take home)
10/1114Augmenting data structurestest 1
10/1315.0-15.1Rod cuttingHW3 rewrite
10/1415.2Matrix-chain multiplication

10/1715.3Dynamic programming
10/1815.4Longest common subsequenceHW4
10/2016.0-16.2Greedy algorithms
10/2116.3Huffman codes

10/24No class (reading day)
10/25No class (reading day)
10/2717.0-17.3Amortized analysisHW4 rewrite
10/2817.4Dynamic tablesHW5

10/3118.0-18.2B-trees
11/118.3Deleting from a B-tree
11/3Skip lists
11/4Skip lists, continuedHW6

11/7Skip lists, continuedHW5 rewrite
11/821.0-21.3Disjoint-set data structures
11/10Catch up
11/11Review

11/14Intra-term test 2 (take home)HW6 rewrite
11/1522.0-22.2Breadth-first search
11/1722.3-22.4Depth-first search; topological sorttest 2
11/1823Minimum spanning trees

11/2124.0-24.2Single-source shortest paths; Bellman-Ford
11/22Extra office hour
11/24No class (Thanksgiving)
11/25No class (Thanksgiving)

11/2824.3Dijkstra's algorithm
11/2925.0, 25.2All-pairs shortest paths; Floyd-WarshallHW7
12/1The Floyd-Warshall algorithm, continued
12/227.0-27.1Dynamic multithreading

12/527.2-27.3Multithreaded algorithms
12/635.0-35.1Approximation algorithms; vertex coverHW8
12/835.5The subset-sum problemHW7 rewrite
12/9The subset-sum problem, continued

12/12Catch up
12/13Review; evaluation
12/15No class (reading day)HW8 rewrite

Course web site: http://gustavus.edu/+max/courses/F2011/MCS-375/
Instructor: Max Hailperin <max@gustavus.edu>