Syllabus
Course Synopsis
This course provides an introduction to advanced data structures and the design and analysis of algorithms. Topics include various techniques for the design of algorithms, analysis of these algorithms for computational complexity, and intractability. Any programming activities will be done in C++ on a Linux platform.
Required Texts
- Introduction to the Design & Analysis of Algorithms, by Anany Levitin
Prerequisites
CPSC 250 and MATH 131. Familiarity with C++ and Unix/Linux is assumed.
Intended Learning Outcomes
At the end of this course successful students will be able to:
- design algorithms for various problem types,
- analyse the efficiency of algorithms, and
- analyse the computational complexity of problems.
Class Attendance
Regular attendance in class and the lab sessions is highly recommended. Regardless of attendance, students are responsible for all material covered or assigned in class.
Mechanics
The course will meet in class for three hours during the week. There will be three tests (on February 13, March 20, and April 17) in class during the semester. The final exam is scheduled for Monday, April 29: 8:30am - 11:30am.
Make-up tests will be available by pre-arrangement only in case of scheduling conflicts. After the test, make-ups will be available only in case of documented medical emergencies.
Besides the exams, there will be quizzes in class, regular homework assignments, and a co-curricular requirement.
Quizzes: Quizzes will be in class and will be announced one class period before the quiz.
Co-curricular Requirement: The Mathematics, Computer Science and Physics department offers a series of discussions that appeal to a broad range of interests related to these fields of study. These co-curricular sessions will engage the community to think about ongoing research, novel applications and other issues that face these disciplines. Each student is required to attend at least three of these sessions, and turn in a short paper describing the contents of the session, and his/her critical reflections about the topic and content. These papers are due in class within a week of the session. A paper submitted beyond a week from the event being discussed in the paper will not be accepted.
Grading
The final grade will be computed based on the grades in the tests, the final exam, home works and programming projects according to the following weights.
| Component | Weight | |
|---|---|---|
| Co-curricular | 4% | |
| Home works | 15% | |
| Quizzes | 15% | |
| Tests (3) | 36% | (12% each) |
| Final Exam | 30% |
The final course grade will be calculated as follows:
| < 60 | 60-62 | 63-65 | 66-69 | 70-72 | 73-75 | 76-79 | 80-82 | 83-85 | 86-89 | 90-92 | > 92 |
| F | D- | D | D+ | C- | C | C+ | B- | B | B+ | A- | A |
Academic Integrity
Students are expected to adhere to the Academic Integrity policies of Roanoke College. All work submitted for a grade is to be strictly the work of the student unless otherwise specified by the instructor. The policies as outlined in the Academic Integrity handbook will be enforced in the course.
Graded programs are subject to the Roanoke College Academic Integrity policies. Copying a program or a portion of a program (even a single line) or reading another person's program to obtain ideas for solving a problem is plagiarism. Other examples of integrity violation include writing code for some else, using code written by someone else, telling someone else how to solve a problem or having someone tell you how to solve a problem (and using their method). These cases apply to any work that is handed in for a grade under the instructor's assumption that the work is your own. Unless specified otherwise by the instructor, discussion among students should be limited to general discussion of concepts and language details, not specific aspects of a solution to the assigned problem.