MA/CSSE473 – Design and Analysis of Algorithms

Fall, 2008-09 (200910) Schedule Overview updated Sat Nov 15 at 3:13:40 PM

Link to All non-ANGEL web pages for the course

This schedule will be updated prior to each day's class

Preparations are to be completed before the class session.


Session quick links:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Week Session Preparation HW Due Topics Resources
0

1

Thu Sep 4

Details 		 
  • Course introduction
  • Introduction to algorithms and review of CSSE 230
0

2

Fri Sep 5

Details
  • Chapter 1;
  • Sections 2.1 and 2.2
  • Background Survey on ANGEL. (do it before 5 PM on Thursday if you can)
  • What is an Algorithm?
  • Fibonacci Algorithms and their analysis
  • Integer arithmetic
1

3

Mon Sep 8

Details
  • Sections 2.3 - 2.7
  • Appendix A
  • CACM interview with Donald Knuth.
    (July-August 2008)
  
  • Fibonacci numbers via Matrix multiplication
  • Analyzing Addition
  • Algorithms for multiplication
  • Master Theorem review
1

4

Tue Sep 9

Details
  • Sections 3.1-3.3
  • Appendix B
  • Asymptotics review
  • Faster multiplication
1

5

Thu Sep 11

Details
  • Section 3.3
  • Sections 4.1-4.4
  
  • More precise Fibonacci analysis
  • Modular Arithmetic
1

6

Fri Sep 12

Details
  • Section 4.5
  • Modular Exponentiation
  • Review of Induction
2

7

Mon Sep 15

Details
  • Catch up on previous reading assignments
  
  • Mathematical Induction examples
  • Structural Induction
  • Euclid's Algorithm for gcd
2

8

Tue Sep 16

Details
  • Catch up
  • HW 3 discussion
  • Euclid efficiency
  • Extended Euclid
  • Look at HW 4
2

9

Thu Sep 18

Details
  • Section 4.6
  
  • Modular Division
  • Primality testing
  • Fermat's Little Theorem
2

10

Fri Sep 19

Details
  • List some review topics from the textbook
  • Fermat's Little Theorem: Proof
  • More Primality testing
3

11

Mon Sep 22

Details
  • Sections 5.3 and 5.4
  
  • Miller-Rabin test
  • Primality algorithm summary/analysis
  • Generating Random primes
  • RSA Cryptosystem
3

12

Tue Sep 23

Details 		 
  • RSA Cryptosystem
  • Amortized Efficiency Analysis
  • Brute Force Algorithms
3

13

Thu Sep 25

Details
  • Sections 5.5
  
  • Guest Lecture: Bebo White
  • none
3

14

Fri Sep 26

Details
  • Sections 5.6
  
  • Donald Knuth Interview
  • Brute Force Algorithms
  • Divide and COnquer
4

15

Mon Sep 29

Details
  • Catch up on reading
  • Divide and conquer
  • Closest points
  • Convex hull
4

16

Tue Sep 30

Details
  • review for exam
  
  • EXAM #1
  • Textbook and a page of notes
4

17

Thu Oct 2

Details 		   
  • Convex Hull details and analysis
  • Strassen's Matrix Multiplication algorithm
4

18

Fri Oct 3

Details 		 
  • Decrease and conquer
  • Insertion Sort
  • DFS and BFS
  • Topological Sort
5

19

Mon Oct 6

Details
  • 6.1 - 6.2
  
  • DFS and BFS
  • Topological Sort
  • Combinatorial Object Generation
5

20

Tue Oct 7

Details
  • 6.3-6.4
  • Homework Algorithms
  • Lexicographic Permutation Generation
  • Subset Generation
  • Gray Codes
5

21

Thu Oct 9

Details
  • Section 6.5
  
  • Find next lexicographic permutation
  • permutation --> sequence number
5

22

Fri Oct 10

Details
  • Section 6.6
  • Generating sequence number from a permutation
  • Decrease by a constant factor
  • Fake Coin problem
  • Josephus Problem
6

23

Mon Oct 13

Details 		 
  • Transform and conquer:
  • Pre-sorting (3 qpplications)
  • Gaussian Elimination (3 applications)
  • Balanced trees (AVL, 2-3)
  • Heaps and Heap Sort
6

24

Tue Oct 14

Details 		 
  • HW 10Due Wednesday at noon
  • 2-3 trees
  • Heap definition and representation
  • insert and removeMax operations
  • HeapSort
  • BuildHeap
7

25

Mon Oct 20

Details
  • Sections 7.1 and 7.2
  
  • Heap COnstruction Comparisons
  • Horner's Rule
  • Linear Programming at a GLance
  • Problem reductions
  • Space-Time tradeoff examples
  • Efficient String Search Intro
7

26

Tue Oct 21

Details
  • Sections 7.3 and 7.4
  
  • No class today
7

27

Thu Oct 23

Details
  • Section 8.1
  
  • Horspool's Algorithm
  • Boyer-Moore
7

28

Fri Oct 24

Details
  • Section 8.2
  • Boyer-Moore wrapup
  • Review of Hashing algorithms and analysis
  • Assign Boyer-Moore implementation problem
8

29

Mon Oct 27

Details
  • Section 8.3
  
  • Hashing
  • B-trees
  • Dynamic Programming
8

30

Tue Oct 28

Details 		   
  • Dynamic Programming
  • Binomial Coefficients
  • Transitive Closure Calculation
8

31

Thu Oct 30

Details
  • Sections 9.1-9.2
  • Warshall's Algorithm
  • Optimal BSTs
8

32

Fri Oct 31

Details 		   
  • Exam 2
  • You may begin at 7:30 if you wish.
  • None
9

33

Mon Nov 3

Details 		   
  • Optimal BSTs
9

34

Tue Nov 4

Details 		 
  • Optimal BSTs
  • Greedy Algorithms
  • Prim, Krushkal intro
9

35

Thu Nov 6

Details
  • Section 11.1
  
  • More on Prim, Krushkal
  • Disjoint set representation
9

36

Fri Nov 7

Details
  • Section 11.2
  • Disjoint sets
10

37

Mon Nov 10

Details
  • Section 11.3, 11.4
  
  • Disjoint sets and Kruskal analysis
  • Prim Data Structures
10

38

Tue Nov 11

Details
  • Section 12.1
  • Prim Detailed Algorithm
  • Dijkstra
10

39

Thu Nov 13

Details
  • Section 12.2
  
  • No class (instructor illness)
  
10

40

Fri Nov 14

Details
  • Epilogue (P 465)
  • P and NP