CSCI 235
Analysis of Algorithms
College of the Holy Cross, Fall 2017
Home | | Syllabus | |
Assignments | |
Lecture Notes
Instructor
Lecture times
Course description
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
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.
For the most part, we will not do any programming in this class. Textbook
It is expected that Holy Cross students will have textbooks and other required class
materials in order to achieve academic success. If you are unable to purchase course materials,
please go to the Financial Aid office where a staff member will be happy to provide you with
information and assistance.
Exams
Midterm Exam II: Monday, November 6, 6:00 - 8:00 p.m.
Final exam:
Homework Assignments
Quizzes
Grading
Late Policy
Collaboration Policy
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
Math and CS Department's policy on Academic Integrity
as well as the
College's Academic Integrity Policy.
Disability Statement
If you are already registered with Disability Services, please be sure to get your accommodation
letters and deliver them to your instructors in a timely fashion. Instructors need 4-5 days advance
notice to be able to facilitate the process of receiving testing accommodations.
Home | | Syllabus | |
Assignments | |
Lecture Notes
Constance Royden--croyden@holycross.edu
Constance Royden
Office: Haberlin 308
Extension: 2472
Email: croyden@holycross.edu
Office Hours: Mon & Wed 3:00 - 4:00 p.m., Tues. 1:00 - 3:00 p.m., or by appointment.
MWF, 11:00 - 11:50 a.m.
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.
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.
Introduction to Algorithms, 3rd edition by Cormen, Leisersen, Rivest and Stein.
This excellent and comprehensive textbook is a "must" for any computer scientist.
Midterm:
There will be two midterm exams held on the following date:
Midterm Exam I: Wednesday, September 27, 6:00 - 8:00 p.m.
Please mark your calendars now.
The final exam will be held during finals week as scheduled.
Final Exam: TBD
There will be approximately eight to ten homework
assignments during the semester. These problem sets will be of the "paper and pencil"
variety. While some feedback will be given on the homework sets, students will be expected
to compare their answers with those in the posted solutions once the homework is handed back,
so they can see where they can
correct or improve their answers. Homework problems, or problems very similar to them, may
appear on exams or quizzes, so students are advised to study the solutions sets.
There will be approximately eight to ten short quizzes during the semester.
These may or may not be announced ahead of time.
Participation: 5%
Quizzes: 10%
Homework: 20%
Midterm exam I: 20%
Midterm exam II:20%
Final exam: 25%
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.
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.
Any student who feels the need for accommodation based on the impact of a disability should contact
Office of Disability Services to discuss support services available.
Once the office receives documentation supporting the request for accommodation, the student would
meet privately with Disability Services to discuss reasonable and appropriate accommodations.
The office can be reached by calling 508-793-3693 or by visiting Hogan Campus Center, room 215A.
Computer Science 235--Analysis of Algorithms
Last Modified: August 14, 2017
Page Expires: August 24, 2018