CS 221 - Analysis of Algorithms - Spring 2010

Class Information

Instructor: Nicholas Coleman
Time: MWF
2:00 pm - 2:50 am
Classroom: ELAB 243
Text: The Design & Analysis of Algorithms
Second Edition
by Anany Levitin
ISBN 0-321-35828-7
Textbook cover

Links

Lectures, Assignments, and Exams

Monday Wednesday Friday
Week 1 1/11
  • Introduction
  • Syllabus
  • What Is an Algorithm?
Levitin 1.1 		1/13
  • Fundamentals of Algorithms Problem Solving
  • Important Problem Types
Levitin 1.2 - 1.3 		1/15
  • Efficiency Analysis
Levitin 2.1
Week 2 1/18
NO CLASS - MLK Day 		1/20
  • Asymptotic Notations
  • Basic Efficiency Classes
Levitin 2.2 		1/22
  • Nonrecursive Algorithm Analysis
Levitin 2.3
Homework 1: Section 2.3
1d, 1e, 1g, 2b, 2d, 5
Week 3 1/25
  • Recursive Algorithm Analysis
  • Recurrence Relations
Levitin 2.4, App. B 		1/27
  • Recursive Algorithm Analysis
  • Recurrence Relations
Levitin 2.4, App. B
Week 4 2/1
  • Brute Force Algorithms
    • Selection Sort and Bubble Sort
    • Sequential Search and String Matching
Levitin 3.1 - 3.2
Homework 1 due
Homework 2: Section 2.4
1a, 1c, 1e, 8a, 8b 		2/3
  • Brute Force Algorithms
    • Closest-Pair and Convex-Hull
    • Exhaustive Search
Levitin 3.3 - 3.4
Week 5 2/8
  • Divide and Conquer
    • MergeSort
    • QuickSort
    • Binary Search
Levitin 4.1 - 4.3 		2/10
  • Divide and Conquer
    • Closest-Pair and Convex Hull
Levitin 4.4
Week 6 2/15
  • Divide and Conquer
    • Closest-Pair and Convex Hull
  • Decrease and Conquer
Levitin 4.6, 5 Homework 2 due 		2/17
  • Decrease and Conquer
    • Insertion Sort
    • Depth-First Search
    • Breadth-First Search
Levitin 5.1 - 5.2
Week 7 2/22
  • Decrease and Conquer
    • Topological Sorting
    • Generating Combinatorial Objects
Levitin 5.3 - 5.4 		2/24
  • Decrease and Conquer
    • Decrease by a Constant Factor
    • Variable Size Decrease
Levitin 5.5 - 5.6
Week 8 3/1
  • Transform and Conquer
    • Balanced Search Trees
Levitin 6.3 		3/3
  • Transform and Conquer
    • Heaps and Heapsort
Levitin 6.4
Homework 3: Pick 4 problems from 3.3.4, 3.4.9b, 4.1.11, 4.6.10, 5.5.3, 5.6.9
Week 9 3/8
  • Transform and Conquer
    • Problem Reduction
Levitin 6.6 		3/10
NO CLASS - SIG-CSE
Week 10 3/15
  • Space and Time Tradeoffs
    • Sorting by Counting
    • Input Enhancement in String Matching
Levitin 7.1-7.2 		3/17
  • Space and Time Tradeoffs
    • Hashing
    • B-Trees
Levitin 7.3-7.4
Homework 3 due
Homework 4
Week 11 3/22
  • Dynamic Programming
    • Binomial Coefficients
    • Warshall's Algorithm
    • Floyd's Algorithm
Levitin 8.1-8.2
3/24
  • Dynamic Programming
    • Optimal Binary Search Trees
    • The Knapsack Problem
    • Memory Functions
Levitin 8.3-8.4
Spring
Break		 3/29
NO CLASS 		3/31
NO CLASS
Week 12 4/5
4/7
Homework 4 due
Week 13 4/12
4/14
Week 14 4/19
4/21
Homework 5 due
Week 15 4/26
4/28
Finals 5/7
Final Exam
1:00 - 2:50 pm