|
Home | | Syllabus | |
Assignments | |
Lecture Notes
Instructor
Constance Royden
Office: Swords 318/333
Extension: 2472
Email: croyden@mathcs.holycross.edu
Office Hours: Mon, Wed 11 a.m. - noon, Thurs 10:00 a.m. - nooon
Lecture times
MWF, 10:00 - 10:50 a.m.
Course description
Algorithms are recipes for solving computational problems. In this course
we will study fundamental algorithms for solving a variety of problems, including
sorting, searching and graph algorithms. More importantly, we will focus on
general design and analysis techniques that underlie these algorithms. For example,
we will examine divide-and-conquer, dynamic programming, greediness, and probabilistic
approaches. With an understanding of these techniques, you will be prepared to design
some of your own algorithms.
Algorithms are judged not only by how well they solve a problem,
but also by how effectively they use resources like time and space.
We will learn techniques for analyzing time and space complexity of
algorithms and will use these to evaluate tradeoffs between different
algorithms. We will also see that problems can be organized into a hierarchy
that measures their inherent difficulty by the efficiency of the best possible
algorithm for solving them.
Prerequisites
The prerequisite for this class is CSCI 132, Data Structures and 1 semester
of calculus.
You should feel comfortable with simple data structures (arrays, lists, trees,
stacks and queues) as well as recursion. You should also feel comfortable with
basic calculus concepts such as limits and derivatives.
In addition you should be prepared to learn some new mathematical techniques.
In order to analyze algorithms, we'll need to use some mathematical methods that may be
new to you. We will learn these methods in class, and they are also explained well
in the textbook.
The Notation we will use for algorithms is the pseudocode used in the textbook.
We will not do any programming in this class.
Textbook
Introduction to Algorithms, 2nd edition by Cormen, Leisersen, Rivest and Stein.
This excellent and comprehensive textbook is a "must" for any computer scientist.
Exams
Midterm:
There will be one midterm exam held on the following date:
Midterm Exam: Wednesday, October 17, 6:30 - 8:30 p.m.
Please mark your calendars now.
Final exam:
The final exam will be held during finals week:
Final Exam: Saturday, December 15, 8:30 a.m.
Homework Assignments
There will be approximately eight to ten homework
assignments during the semester. These problem sets will be of the "paper and pencil"
variety. No programming will be involved.
Grading
Participation: 10%
Homework: 30%
Midterm exam: 30%
Final exam: 30%
Late Policy
Assignments are due at the beginning of class on the assigned due date.
Late assignments will be marked down 10% for each day late. That is, assignments
turned in after the time they are due will be marked down 10%, assignments turned
between 24 and 48 hours after the due date will be marked down 20%, and so on. The
penalty will be determined when the assignment is physically transferred to the
instructor or signed in by any Math/CS faculty member or the department secretary.
Late work will not be accepted after the graded assignment is returned to the class.
Collaboration Policy
You are allowed to discuss strategies for solving homework problems
with other students, however any work you turn in must be your own work (i.e.
you may not simply copy another student's answers and turn them in as your own).
In addition you must clearly indicate the names of any students you work with on
each assignment.
You may consult public literature (books, articles, etc) for information,
but you must cite each source of ideas you adopt.
Please familiarize yourself with the department's policy on
Academic Integrity.
Home | | Syllabus | |
Assignments | |
Lecture Notes
Constance Royden--croyden@mathcs.holycross.edu
Computer Science 235--Analysis of Algorithms
Date Created: August 26, 2005
Last Modified: August 24, 2007
Page Expires: August 24, 2008
|