CPSC 270A Algorithms, Spring 2005


Anil M. Shende
365B Trexler, x2341
email address: shende@roanoke.edu
Office Hours: M: 8:30am--9:30am; W: 1:00pm--2:30pm; Th: 9:00am--11:00am; and by appointment


Introduction to the Design & Analysis of Algorithms, by Anany Levitin


This course provides an introduction to advanced data structures and the design and analysis of algorithms. Topics include computational complexity, sorting techniques, hash tables, various kinds of search trees, graph algorithms and various techniques for the design of algorithms. All programming projects will be done in C++ on a Linux platform.


CPSC 220, or permission of the instructor. Familiarity with Java and Unix is assumed.

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.

Class Attendance

Regular attendance is highly recommended. Regardless of attendance, students are responsible for all material covered or assigned in class.


There will be two take-home tests (due at the beginning of class on February 14 and March 21) and a take-home final exam (due at the beginning of class on April 25). 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 emergency.

Besides the exams, there will be regular homework assignments and short programming projects.

Home Work: Home work assignments will be assigned every day in class. Home work must be turned in on the Monday of the next week at the beginning of the class period. All home work must be handed in as LaTeX documents. We will go over creating LaTeX documents in class. No hand-written home work assignments will be accepted, unless explicitly stated otherwise in the assignment. No late home work assignments will be accepted.

Programming projects: There will be several short programming projects assigned during the semester. Programs will be graded on correctness, style and documentation. Programs are due by midnight on the assigned date. No late programs will be accepted. All programs are to be turned in by email; instructions for submission will be given in the assignment handout.


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
Home works22%
Tests (2)30% (15% each)
Final Exam20%

The grading scale is as follows: