Combinatorial Algorithms
MATH 482, Spring 2002
 

Weekly Homework Assignments


 
#1 due Thurs., Jan. 31 1.2-2, 1.2-3, 1-1 (complete table for the functions n, n^2, and 2^n only), and 2.1-1
#2 due Thurs., Feb. 14 2.2-1, 2.3-1, 2.3-4, 2-1, 3.1-4, 3-2 a,b,d,e, 4.1-1, 4.1-2
#3 due Tues., Feb. 26 4.2-1, 4.2-2, 4.2-3, 4.2-4, 4.3-1, 4.3-2, 4-1
#4 due Tues., Mar. 5 6.1-5, 6.1-6, 6.2-1, 6.2-2, 6.3-1, 6.4-1
#5 due Thurs., Mar. 14 6.5-1, 6.5-2, 6.5-3, 7.1-1, 7.1-2, 7.1-3
#6 due Thurs., Mar.21 7.2-1, 7.2-2, 7.2-3, 7.4-1, 7-3
#7 due Thurs., Apr. 4 8.1-1, 9.2-4, 9-1
#8 due Thurs., Apr. 11 9.3-1 (groups of size 7 only), 9.3-5, 15.2-1, 15.2-2, 15.2-3
#9 due Thurs., Apr. 18 worksheet handed out in class
#10 due Thurs., Apr. 25 15.4-5, 22.2-2, 22.2-6, 22.3-2
#11 due Thurs., May 9 worksheet handed out in class

 
Catalog Description Prerequisites: Math 150B and 262 and some computer programming experience. Computer oriented study of semi-numerical and non-numerical algorithms. Sorting, tree searching, generation of combinatorial structures, algorithm proof techniques, best algorithms, programming complexity.
Textbook Introduction to Algorithms, Second Edition, by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, published by McGraw-Hill, 2001.
Important Dates Exams will be given on March 5 and April 30. The cumulative final exam will be given on May 21, 12:45-2:45. No makeup exams will be given.
Course Outline
Chapters 1 - 2     Introduction
Chapter 3    Growth of Functions
Chapter 4    Recurrences
Chapter 5    Probabilistic Analysis and Randomized Algorithms
Chapter 6    Heapsort
Chapter 7    Quicksort
Chapter 8    Lower Bounds for Sorting (8.1)
Chapter 9    Medians and Order Statistics
Chapter 15  Dynamic Programming
Chapter 22  Elementary Graph Algorithms
Chapter 23  Minimum Spanning Trees
Chapter 24  Single-Source Shortest Paths
Chapter 25  All-Pairs Shortest Paths
Chapter 31  Number-Theoretic Algorithms (time-permitting)
Chapter 32  String Matching (time-permitting)
Chapter 34  NP Completeness
Chapter 35  Approximation Algorithms (time-permitting)
Course Objectives To provide the students with a comprehensive introduction to the modern study of computer algorithms.

For the students to:

(1) Become familiar with the design, analysis, and application areas of standard algorithms for such problems as sorting a sequence of numbers and searching a graph as well as numerous others.
(2) Learn (or review) the mathematics needed to understand the analysis of algorithms.
(3) Learn the basic principles and techniques of computational complexity.

Techniques Used to Obtain Course Objectives Lectures will be used to present new material. Students are expected to actively participate in this course - reading relevant sections in the textbook, doing all assigned problems, and asking and answering questions during class. Short quizzes will be given on occasion. Weekly homework will be assigned and collected during class.
Assignments Students are encouraged to work in groups outside of class, but each student must write up all assignments in his or her own words. All sources of assistance (including classmates, family members, friends, colleagues, books, websites, etc.) must be acknowledged in the write-up of solutions.

Late work is highly discouraged, given no feedback, and drastically marked down according to the formula below, WITH NO EXCEPTIONS.

LATE SCORE = x/n,

where x = lowest score given on assignment and n = number of days late.

Example: Suppose you turn in your assignment, which had been worth 10 points, 2 days late. The lowest score given on the assignment was 3 points. Your score would thus be 3/2 = 1.5 points, even if your work had been perfect.

No feedback will be given on late work.

Class Attendance Policy Class attendance is an essential part of this course.

Missing class is highly discouraged. However, if an absence is unavoidable, it is your responsibility to ask your classmates what you missed. (Advice: Get the phone numbers and/or e-mail addresses of at least two classmates.)

Grading Policy Your course grade will be based on exams, homework, quizzes, and in-class work. These are weighted as follows:

Midterm exams (2)  25% each
Cumulative final exam  35%
Homework, quizzes, and in-class work  15%

Course grades will be assigned as follows:

90-100% A
80-89% B
70-79% C
60-69% D
59% or below F

Cutoffs for “plus” and “minus” grades will be determined at the end of the semester.
This information is subject to revision.

 

return to main page