Fall 2003, Section 00, MTh 1:00-2:15, Curtis 206
This course explores classic algorithms and their application in the real world using advanced features of the C++ programming language. Algorithm run-time complexity is examined with respect to the impact on applications. Advanced sorting and searching techniques are examined. Common file organizations and file processing techniques are presented.
CIS 136.
Neapolitan and Naimipour; Foundations of Algorithms, using C++ Pseudocode, 3rd edition; Jones and Bartlett, 2003. ISBN: 0-7637-2387-8.
Grades for this course will be based on the following assessment items with weights as follows:
Assignment will require programming and will usually include a written component. Acceptable programming languages for assignments are C++ and Java. Other programming languages may be used, but must be approved by the instructor in advance.
Programs should be well documented using comments. Please include, at the beginnning of your program, a comment block with your name, course number, assignment number, date, a brief description of the problem, and an overview of your approach to the problem. Also include comments throughout the program to clearly describe all steps in your algorithm. Each function should have a comment block describing the function, all parameters, and return value. Further, code should be indented to enhance readability.
Through these assignments, the student shows ability to apply course material in a practical situation, and demonstrates understanding of the underlying theory.
Tests for this course will be written and will consist of problems and short answer questions. Tests will be open-book and open-notes.
Through tests, the student demonstrates competency in understanding and applying programming concepts and techniques in limited specific situations.
The format for the final exam will be the same as that of the tests, but longer. The final exam is comprehensive.
| Date | Topic |
|---|---|
| 8/25 8/28 |
Course Intro Algorithm Efficiency and Analysis; Ch. 1 (except 1.4.3), Sec. 2.1 |
| 9/4 9/8 9/11 9/15 |
C++ Template Functions; notes only Sorting and Searching; Sec. 2.2, 2.3, 2.4, 2.8, 7.1, 7.2, 7.4, 7.5, 7.6, 7.8 |
| 9/18 9/22 |
C++ STL; notes only |
| 9/25 9/29 |
Essential Data Structures; notes only |
| 10/2 | Test 1 |
| 10/6 10/9 10/16 |
Greedy Altorithms; Ch. 4 (through 4.3) |
| 10/20 10/23 10/27 10/30 |
Backtracking; Ch. 5 |
| 11/3 11/6 11/10 |
Branch and Bound; Ch. 6 (except 6.3) |
| 11/13 | Test 2 |
| 11/17 11/20 |
Theory of NP; Ch. 9 |
| 11/24 12/1 |
Number Theoretic Algorithms; Sec. 2.6, 10.1, 10.2, 10.3, 10.6 |
| 12/4 12/8 |
Advanced File Processing; notes only |
| TBA | Final Exam |
| No. | Assigned | Due |
| 1 | 8/28 | 9/8 |
| 2 | 9/8 | 9/22 |
| 3 | 9/22 | 10/6 |
| 4 | 10/9 | 10/23 |
| 5 | 10/23 | 11/3 |
| 6 | 11/6 | 11/17 |
| 7 | 11/20 | 12/4 |