UMBC CMSC441, Design & Analysis of Algorithms, Spring 2002, Section 0101

Course Description

Textbook

Introduction to Algorithms, second edition, Cormen, Leiserson, Rivest and Stein. McGraw-Hill. Note: you must have the second edition of this textbook which was just published in August 2001. The new textbook has a green cover.

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 Appendix B, Chapter 10 and Chapter 12 of the textbook (covering sets, elementary data structures and binary search trees) should be familiar. Some knowledge of probability and counting (Appendix C 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 C/C++ or Java is assumed.

Objectives

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.

Grading

Your final grade will be based upon homework assignments (20% total), Exams 1 & 2 (25% each) and the final exam (30%). It is very important that you do the weekly homework assignments. The homework assignments count for a major portion of your grade. 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 11 homework assignments. The homework average will be computed from your 10 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 grading and 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 Tuesday, March 5 and Thursday, April 4. If you miss an exam for good reason (e.g., medical illness), the average score of the remaining exams will be used in place of that exam. The final exam will be comprehensive and cover the material from the entire course. The final exam will be given on Friday, May 17 3:30pm - 5:30pm in ACIV Room 151. Note that this is not the regularly scheduled time for TuTh 2:30 classes!

Last Modified: 22 Jul 2024 11:28:59 EDT by Richard Chang
to Spring 2002 CMSC 441 Section Homepage