Craig Miller
256 South College, x-1400
Email: millercr
Office hours to be announced and placed on Web page
TuTh 9:30-11
Room 4 (basement) South College
Foundations of Algorithms, by Neapolitan and Naimipour
Suggested text: UNIX in a Nutshell, O'Reilly & Associates
This course introduces the study of algorithms at a formal level, including approaches for designing algorithms, theoretical methods for analyzing performance, and empirical methods for testing performance. In the process of studying algorithms, students learn or review data structures (e.g. matrices, hash tables, and trees) and problem solving approaches (e.g. divide and conquer, dynamic programming, the greedy approach, and backtracking).
Certainly a primary goal of the course is to achieve a solid competency in designing, analyzing and implementing algorithms, but the course also targets some general skills that are useful in almost any area of computing:
While the grade is primarily determined from test and quiz scores, they will frequently cover material explicitly encountered in assignments done outside of class. Thus, much of the effort and learning in the course will go in the completion and study of these assignments.
The two quizzes will be scheduled approximately one to two weeks before each of the two tests. Part of their purpose is to provide some initial feedback to both the students and the instructor on how the class is going. They may also cover elementary concepts found in an ongoing assignment.
| 15% | Test 1 | Tue Oct 13 |
| 15% | Test 2 | Tue Nov 17 |
| 25% | Final Exam | Mon Dec 14 |
| 35% | 6-7 Assignments | Assigned 2 weeks in advance |
| 10% | 2 Quizzes | Announced a week in advance |
Tests and quizzes can only be made up with a written medical excuse and must be arranged as soon as possible.
Assignments turned in after the due date but before the next class meeting will be accepted with a 10% penalty. Assignments completed after the next class meeting will generally not be accepted for credit.
Unless explicitly told otherwise, all assignments in this course are individual assignments. Students may not work together in the design or implementation of code or written assignments. The only exceptions to this are:
All other assistance should come from the instructor. Any questions about the appropriateness of collaboration should be discussed with the instructor. Failure to acknowledge someone else's code or even design ideas in any work is plagiarism, which warrants a report to the College's judicial system and may lead to suspension or expulsion.
| Week | Topic | Text Reading |
|---|---|---|
| Sept 2 | Course Overview | Section 1.1 |
| Sept 7 | Images, Matrices and Algorithm Fundamentals | Çourse notes and Section 1.2 |
| Sept 14 | Definitions and Notations of Efficiency | Sections 1.3, 1.4 and Appendix A |
| Sept 21 | Hashing | Class Notes and Section 8.4 |
| Sept 28 | Divide and Conquer Approach | Ch. 2 and Appendix B |
| Oct 5 | Problems using Divide and Conquer | Ch. 2 |
| Oct 12 | Dynamic Programming | Ch. 3 |
| Oct 19 | Problems using Dynamic Programming | Ch. 3 |
| Oct 26 | Greedy Algorithms | Ch. 4.1 |
| Nov 2 | Shortest path and scheduling problems | Sections 4.2 and 4.3 |
| Nov 9 | Backtracking | Ch. 5 |
| Nov 16 | Comparisons in theory and practice | Sections 4.4 and 5.7 |
| Nov 23 | Intro to Computational Complexity | Ch. 7 |
| Nov 30 | Complexity of Sorting Problems | Ch. 7,8 |
| Dec 7 | Intro to Theory of NP | Ch. 9 |