Professor Tom Armstrong, Wheaton College, Fall 2016
- Meeting Times: MTuW at 3:30 in SC1315
- Office Hours: MW at 2:30 - 3:30 in SC1308 and by appointment
An introduction to the mathematical foundations, design, implementation and computational analysis of fundamental algorithms. Problems include heuristic searching, sorting, several graph theory problems, tree balancing algorithms, and the theoretical expression of their orders of growth. Out-of-class assignments and in-class labs emphasize the balance between theoretical hypotheses and experimental verification. C/C++, Java, Perl or Maple are applied to various solutions.
- You will be able to analyze the behavior of algorithms
- You will be able to design algorithms using new techniques (e.g., greedy, divide and conquer, dynamic programming, etc.)
- You will be able to distinguish algorithms based on their design
- You will be able to translate pseudocode into a programming language implementation
It is the expectation for all classes taught at Wheaton College that one hour of class time may expect two to three hours of preparation outside of class. In addition to preparation time, programming assignments are designed to take a significant amount of time per week. Start all assignments early. No late work is accepted.
All work and submissions in this course must be entirely your own original content. Assignments and examinations are to be done individually unless otherwise specified. Laboratories are collaborative and should be done in pairs. Resources (electronic and print) that contain documentation about programming languages are typically allowed, but those containing implementations of assignment components -- except the course texts -- are off limits. At the discretion of the instructor, violations of academic integrity will result in penalties up to and including failing the course and reporting the violation to the College Hearing Board. If you have general questions/concerns or specific instances to discuss, do not hesitate to ask in class or privately.
In compliance with the Wheaton College policy and equal access laws, a Dean is available to discuss appropriate accommodations that may be recommended for students with disabilities. Requests for accommodations are to be made during the first two weeks of the semester so that timely and appropriate arrangements can be made.
Algorithm Design by Jon Kleinberg and Éva Tardos (Hereafter: K&T)
- ISBN-13: 978-0321295354
- ISBN-10: 0321295358
| Week | Topic | |
|---|---|---|
| 1 TuW | Week of 29 Aug | Introduction |
| 2 TuW | Week of 5 Sept | Introduction to Algorithms — K&T 1 |
| 3 | Week of 12 Sept | Algorithm Analysis — K&T 2 |
| 4 | Week of 19 Sept | Algorithm Analysis — K&T 2 |
| 5 | Week of 26 Sept | Graphs — K&T 3 |
| 6 | Week of 3 Oct | Graphs — K&T 3 |
| 7 W | Week of 10 Oct | Greedy Algorithms — K&T 4 |
| 8 | Week of 17 Oct | Greedy Algorithms — K&T 4 |
| 9 | Week of 24 Oct | Midterm Examination |
| 10 | Week of 31 Oct | Divide & Conquer — K&T 5 |
| 11 | Week of 7 Nov | Divide & Conquer — K&T 5 |
| 12 | Week of 14 Nov | Dynamic Programming - K&T 6 |
| 13 MTu | Week of 21 Nov | Dynamic Programming - K&T 6 |
| 14 | Week of 28 Nov | Illness |
| 15 | Week of 5 Dec | K&T 8 |
| Weighting | Evaluation |
|---|---|
| 40% | Daily Assignments |
| 20% | In-Class Practical Assignments |
| 10% | End-of-Semester Project |
| 15% | Midterm Examination |
| 15% | Final Examination |
A passing grade (i.e., >60%) on each individual method of evaluation is a necessary condition for passing the course.