An exploration of classic algorithms and their application in the real world using advanced features of the C++ programming language. Algorithm run-time complixity 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.
Prerequisites: CIS 136.
Neapolitan and Naimipour; Foundations of Algorithms, using C++ Pseudocode, 3rd edition; Jones and Bartlett, 2003. ISBN: 0-7637-2387-8.
Grades are based on the following assessment items:
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.
Written assignment components should be produced by word processor when practical.
Program components are to be submitted in both printed and electronic form. Your instrutor will provide instructions for submitting programs electronically.
Tests will be written and will consist of problems and short answer questions. Usage of the computer will not be allowed during tests. Tests will be open-book and open-notes.
For classes that meet one evening per week, the test period will be during the second half of the class meeting.
The student will write a paper or implement a programming project that further explores some topic presented in, or related to, the course. A paper should be a minimum of 8 pages double-spaced, and is to include proper references. Whether the student chooses to write a paper or implement a programming project, the student will approve the topic/project with the instructor in advance.
At the end of the semester, the student will present his/her paper or project to the class in a 10-15 minute formal presentation.
Students who are active and attentive members of the class, and who contribute to the class from time to time, will receive 5 points for class participation. Students who fall short of this expectation will receive fewer points, commensurate with their level of participation. Also, students who do not abide by Classroom Protocol guidelines will receive a reduced class participation grade.
| Mo | Topic | Reading | |
|---|---|---|---|
| Aug | 23 |
Algorithm Efficiency and Analysis C++ Template Funcitons Sorting and Searching |
1.1-1.4.2, 2.1 2.2, 2.3, 2.4, 2.8, 7.1, 7.2, 7.4, 7.5, 7.6, 7.8 |
| 30 | |||
| Sep | 13 | C++ STL | notes only |
| 20 |
Graph Theory Graph Data Structure |
notes only | |
| 27 |
Dynamic Programming Test 1: Oct 4 |
3.1-3.3, 3.5, 3.6 | |
| Oct | 4 | ||
| 18 | Greedy Algorithms | 4.1-4.3 | |
| 25 | Backtracking | 5.1-5.7 | |
| Nov | 1 | ||
| 8 | Branch and Bound | 6.1, 6.2 | |
| 15 |
Number-Theoretic Algorithms Test 2: Nov 22 |
10.1, 10.2, 10.6, 10.7 | |
| 22 | |||
| 29 |
Presentations Other Topics |
||
| Dec | 6 |