CMSC 441, Spring 1997
Course Description
Textbook:
Introduction to Algorithms,
Cormen, Leiserson and Rivest, McGraw-Hill.
Prerequisites:
You should have mastered the material covered in the following
courses: CMSC 203 (Discrete Structures), CMSC 341 (Data Structures)
and MATH 152 (Calculus and Analytic Geometry II). The material in
Chapters 5, 11 and 13 of the textbook (covering sets, elementary data
structures and binary search trees) should be familiar. Some
knowledge of probability and counting (Sections 6.1 - 6.4 of the
textbook) is also expected. In addition, proficiency in the
implementation of the elementary data structures (e.g. stacks,
queues, linked lists, binary trees and graphs) in PASCAL or C is
assumed.
Topics:
This course stresses the quantitative methods used in the design and
analysis of algorithms. The main emphasis of this course is to help
you develop the skills needed to analyze the running times of
algorithms and to prove the correctness of algorithms. A secondary
goal of this course is to familiarize you with a broad range of
fundamental algorithms. The material covered in this course will
include algorithms for sorting, order statistics, hashing, balanced
binary trees, dynamic programming and graphs. If time permits, a
selection of advanced topics (such as cryptographic algorithms,
NP-completeness, Strassen's algorithm or parallel algorithms) may also
be included.
Your final grade will be based upon class participation (2%),
a programming project (12%), homework assignments (36% total),
Exams 1 & 2 (15% each) and the final exam (20%). It is very
important that you do the weekly homework assignments. The homework
assignments count for a major portion of your grade --- more than each
exam. Your grade is given for work done during the semester;
incomplete grades will only be given for medical illness or other such
dire circumstances.
Your final letter grade is based on the standard formula: 0 <= F
< 60, 60 <= D < 70, 70 <= C < 80, 80 <= B < 90,
90 <= A < 100. Depending upon the distribution of grades in the
class, there may be a curve in your favor, but under no circumstances
will grades be curved downward. As a guideline, we expect that a
student receiving an ``A'' should be able to solve the homework
problems with facility, design and analyze new algorithms in written
exams and demonstrate an understanding of the impact of theoretical
analysis in practical programming settings.
Lecture and Homework Policy:
You are expected to attend all lectures. You are responsible
for all material covered in the lecture as well as those in the
assigned reading. However, this subject cannot be learned simply
by listening to the lectures and reading the book. In order to
master the material, you need to spend time outside the classroom,
to think, to work out the homework and understand the solutions.
There will be a total of 10 homework assignments. The homework
average will be computed from your 9 best homework grades. Homework
is due at the beginning of lecture --- this is so you do not work on
your homework during lecture. Late homework will not be accepted
--- this is to allow for timely discussion of the homework solutions.
Since you will be given partial credit for serious attempts, you
should simply turn in whatever you have accomplished for the homework
set when it is due. A good approach to solving the homework problems
is to work on one problem each day and to come to class or office
hours with prepared questions about the problems you have not been
able to solve.
Working Together:
You are encouraged to work with other students and to consult other
reference books. However, you must acknowledge your collaborators and
reference materials by listing them on the last page of your homework.
Also, you must write up your homework independently. This means
you should only have the textbook and your own notes in front of you
when you write up your homework --- not your friend's notes, your
friend's homework or other reference material.
You should not have a copy of someone else's homework or project
under any circumstance. For example, you should not
let someone turn in your homework. Cases of academic dishonesty
will be dealt with severely.
Exams:
The exams will be closed-book and closed-notes.
The dates for Exams 1 and 2 are Thursday, February 27 and Thursday,
April 10. The final exam will be comprehensive and cover the
material from the entire course. There will be a combined final exam
for both sections of this course, so the time and location of the
final exam will differ from those listed in the class schedule.
Details on the final exam will be announced soon.
Programming Project:
You will be assigned one project which will have significant written
and programming components. The project will be due on the last day
of class (Thursday, May 8). Details will be announced at a later
date.
Last Modified:
Wed Jan 29 11:34:48 EST 1997
Richard Chang, chang@gl.umbc.edu