CPSC 270: Algorithms

Course Web Site: http://cs.roanoke.edu/Spring2009/CPSC270A

Textbook: Introduction to the Design & Analysis of Algorithms, 2^nd edition by Anany Levitin, Addison Wesley Publishers, 2007.

Course Objectives: This course is an introduction to advanced data structures and the design and analysis of algorithms. The course also provides an introduction to C++ (assuming a programming background in Java). At the end of the course the students should be able to design algorithms using a variety of techniques, do a complete analysis of the computational complexity of algorithms, understand and be able to implement (in C++) various sorting algorithms, hash tables, various types of search trees, and graph algorithms.

Prerequisites: CPSC 220; Familiarity with Java and Unix is assumed.

Attendance Policy: Class attendance is a very important aspect of a student's success in this course. The student is expected to attend every class and is accountable for any missed classes. Attendance at two Department of Mathematics, Computer Science, and Physics Conversation Series lectures is required (there will be several options).

Grading Policy: The course grade will be based on 3 tests, regular homework and lab activities, programming projects, the co-curricular requirement, and a comprehensive final examination with weights as follows:

Make-up Policy: Everyone is expected to take tests and the exam at the scheduled time. Make-ups will be given only for legitimate, documented absences and, if given, may be oral.

Special Needs: If you are on record with the College's Special Services as having special academic or physical needs requiring accommodations, please meet with me as soon as possible. We need to discuss your accommodations before they can be implemented. Also, please note that arrangements for extended time on exams and testing in a semi-private setting must be made at least one week before the exams. If you believe you are eligible for accommodations but have not yet formally contacted Special Services, please call 375-2248 or drop by the Office of Academic Services in the Library.

Assignments: There will be several assignments including daily homework, both in-class and out-of-class labs and programming activities, and larger programming projects. These will vary in difficulty, amount of time required, and credit. Daily homework problems will be turned in the next class period after assigned unless otherwise specified. For daily work you will receive one grade based on effort (did you make a reasonable attempt at the problems) rather than correctness. However, a few of the problems (between 0 and 3) will be graded for correctness. On some (but not all - this policy is mainly for proofs) of these graded problems you will be given two tries. If a "two-try" problem is not perfect (logically correct and well-written) on the first try, it may be turned in again the next class (after being returned to you) to be re-graded. Such a problem will not be given a grade on the first try; there will only be comments.

Late Policy for Assignments, Labs, and Programming Projects: Unless otherwise specified, work is to be turned in at the beginning of class on the day it is due. Late homework and lab assignments will not be accepted. For programming projects, ten percent per calendar day (24 hours) will be deducted for late work; work will not be accepted if it is handed in more than 5 days late OR after the graded assignment or lab has been returned (whichever comes first).

Co-Curricular Requirement: The Department of Mathematics, Computer Science, and Physics is offering a series of lectures designed to engage the campus community in discussions of ongoing research, novel applications, and other issues that face these disciplines. You are invited to attend all of the events but participating in at least two is mandatory. Within one week of attending an event you must submit a one page paper reflecting on the discussion. If you do not turn the paper in within the one week time frame you may not count that event as one you attended.

Academic Integrity: Students are expected to adhere to the policies in the "Academic Integrity at Roanoke College" Handbook. In particular, all tests, exams, quizzes, programming and computer assignments, and papers are to be the work of the individual student. You are encouraged to get help from the instructor if you need help with an assignment. The work you turn in must be your own. Using someone else's work or ideas as your own is plagiarism and an academic integrity offense. Examples of academic integrity violations include copying a program or part of a program (even one line) from someone else, writing code for someone else, telling someone else how to solve a problem (such as telling someone the formula needed in a program or a spreadsheet) or having someone tell you how to solve a problem. Discussion among students should be limited to general concepts, not specific aspects of how to complete the assignment.

Electronic Devices and Academic Integrity: All cell phones and other electronic devices (including IPods and laptops) must be turned off prior to entering the classroom or lab. Any use of such a device during a test will be considered a breach of academic integrity. Handheld calculators may be used only with the permission of the instructor, and when permitted, may not be shared by students (each student must have his/her own).

Computer Use Policies: All students must abide by the Computer Use policies of the Roanoke College. Failure to do so will result in involuntary withdrawal from the course.