Instructor: |
Dr. Jane Ingram | Office Hours: |
Mon, Wed: 2:30 - 3:30 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Office: |
365-A Trexler | Tu, Th: 2:45 - 3:45 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Phone: | 375-2446 | Also by appointment or drop-in |

**Course Web Site: **
http://cs.roanoke.edu/Spring2011/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).

**Intended Learning Outcomes:**
At the end of the course
the successful student should be able to:

- explain the design of standard algorithms studied in the course that use a variety of techniques including brute force, divide-and-conquer, decrease-and-conquer, transform-and-conquer, dynamic programming, and greedy approaches;
- design algorithms using the various design techniques listed above;
- perform a complete mathematical analysis of the computational complexity of algorithms;
- analyze and implement (in C++) various algorithms studied in the course;
- write clear documentation for programs that adheres to given specifications;
- understand, and provide arguments for, the limitation of algorithms,
- understand and be able to implement some strategies for coping with limitations of algorithms such as backtracking and branch-and-bound.

**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 lectures during the semester to choose from
for one of these lectures but attendance is required at
the lecture "Can We Build Trustworthy Software?" by
Dr. Greg Morrisett, Wednesday, March 30.
**

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

Grade Component | Weight |
---|---|

Tests (2) | 36% |

Homework Assignments, Labs, & Programming Projects | 35% |

Co-curricular | 3% |

Final Exam | 26% |

Test Dates:
| Test #1 | Tuesday, February 22 |

Test #2 | Tuesday, April 5 | |

Final Exam | Thursday, April 28 (2:00 - 5:00 pm) |

Grading Scale: | 93-100 | A | 83-86 | B | 73-76 | C | 63-66 | D | |||

90-92 | A- | 80-82 | B- | 70-72 | C- | 60-62 | D- | ||||

87-89 | B+ | 77-79 | C+ | 67-69 | D+ | below 60 | F |

**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 Office of Disability Support 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 the Office of
Disability Support Services in the Goode-Pasfield Center in the Library,
please contact Bill Tenbrunsel, Associate Dean, at 375-2247 or
tenbruns@roanoke.edu.

**Assignments**: There will be several
assignments including weekly homework to be handed in (in addition
to daily practice problems that will not be handed in),
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. Weekly homework problems will be turned in **every
Tuesday**. For weekly homework you will receive
one grade based on effort (did you make a reasonable attempt at the
problems) rather than correctness and a separate grade
for correctness. On some (but not
all - this policy is mainly for proofs) of the 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 **to turnitin through Inquire**
a one page, single-spaced, 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.