CS 3500 A Theory I - Part 1

Fall 2003

[Syllabus] [Homework]

 
Topics
Date(s)
Reading
Design and Analysis of Algorithms Overview:
Paradigm Problems, Design Methods, Driving Applications.

Complexity = Performance as a Function of Input Size.
Time and Space as Computational Resources.
The RAM Computationa Model.

First Paradigm Problem: Sorting.

Algorithm: Bubblesort.
Design Method : GREEDY.
Tue., Jan. 6
Reading:
CLRS Chapters 1 & 2
and 1st set of Lecture Notes.
Algorithm: Tournamentsort.
Design Method: DATA STRUCTURES.
Thu., Jan. 8
Reading:
2nd set of Lecture Notes.
Complementing Help Section:
Review Recursion and Solving Recurrences.
Sections A1, A2, A3
Reading: CLRS Chapters 3 & 4
Set A of Help Notes.
Complementing Help Section:
Data Structures, Heaps.
Sections A2, A3
A1 = MLK Holiday
Reading: CLRS Chapter 6
Set B of Help Notes.
RECURSIVE SORTING ALGORITHMS.
Algorithm: Mergesort. Design Method: DIVIDE & CONQUER.
Algorithm: Quicksortsort. Design Method: RANDOMIZATION.
Off the record: Here's an interesting recent article from Science magazine. Among several other points, it makes a very strong argument about recursion, claiming that it is the main cognitive differentiation between humans and the rest of the primates.
Tue., Jan. 13
Reading: CLRS Chapters 3 & 7,
3rd set of Lecture Notes.
Medians and Order Statistics.
Design Method: DIVIDE & CONQUER.
1st Implementation: Randomized, RANDOMIZATION.
Thu., Jan. 15
Reading: CLRS Pars 9.1 & 9.2
4th set of Lecture Notes. 1 2 3 4
Medians and Order Statistics.
Design Method: DIVIDE & CONQUER.
2nd Implementation: Deterministic.
Tue., Jan 20
Reading: CLRS Paragraph 9.3
4th set of Lecture Notes, continued.
Mincost Spanning Tree.
Design Method: GREEDY and DATA STRUCTURES.
Thu., Jan. 22
Reading: CLRS Chapter 23,
and 5th Set of Lecture Notes.
Complementing Help Section:
Review for Quiz 1.
Sections A1, A2, A3,B
Practice Quiz.
Quiz 1.
Tue., Jan 27
Quiz A and Quiz B.
Complementing Help Section:
Review for HW3.
Sections A2, A3,B
Makeup for A1: Wed Feb 4.
Depth First Search in Undirected Graphs.
Design Method: Recursion and Graph Theory.
Thu., Jan. 29
Reading: CLRS Paragraphs 22.1, 22.3, Problem 22-2
and 6th Lecture Notes.
Depth First Search in Undirected Graphs.
Biconnectivity.
Tue., Feb. 3
Reading: as previous lecture
Depth First Search in Directed Graphs.
Topological Sorting.
Thu., Feb. 5
Reading: Reading: CLRS Paragraphs 22.3, 22.4
and 7.I set of Lecture Notes.
Depth First Search in Directed Graphs.
Strong Connectivity.
Tue., Feb. 10
Reading: CLRS Paragraph 22.5
and 7.II set of Lecture Notes. 1 2 3 4 5 6
Breadth First Search.
Dijkstra's Shortest Paths.
Thu., Feb 12
Reading: 8th Set of Lecture Notes.
Strassen's Multiplication.
Tue., Feb 17
Reading: CLRS 28.2 and these Notes.
Complementing Help Section:
Review for Quiz 2.
Sections A1, A2, A3,B
Practice Quiz.
Quiz 2.
Thu., Feb 19
Quiz 2 and Key to Quiz 2.
Section B Quiz 2 and Key to Section B Quiz 2.
All Pairs Shortest Paths.
Dynamic Programming.
Tue., Feb 24
Reading: CLRS 15, intro pp 323-324, CLRS 25, 25.1, 25.2 pp 620-635, and these Notes.