Captain's Log: CIS 775, Analysis Of Algorithms, Fall 2014

1: Aug 25g (Mon)
Introduction to course: Cormen Reading: Chapter 1.
Howell Reading: Section 1.1.
2: Aug 27 (Wed)
Using the insertion sort method as example, we Cormen Reading: Sections 2.1 & 2.2.
Howell Reading: Sections 1.2-1.4; Sections 2.1-2.2.
3: Aug 29 (Fri)
We address, with insertion sort as one of the examples, how to prove the correctness of a Discuss the principle of binary search as to be used in Assignment 1.
Sep 1 (Mon)
University Holiday (Labor Day)
4: Sep 3 (Wed)
5: Sep 5 (Fri)
6: Sep 8 (Mon)
We continue the theory of asymptotic notation, and Howell Reading: Section 3.3.
7: Sep 10 (Wed)
We finish the theory of asymptotic notation, and Discuss Assignment 2, due tomorrow at 11pm.
8: Sep 12 (Fri)
We address the complexity of iterative algorithms, where we need to estimate sums (cf. Howell 3.4-6):
9: Sep 15 (Mon)
Introduce general recurrences: Discuss model solutions for Assignment 1 (now graded).
10: Sep 17 (Wed)
11: Sep 19 (Fri)
We present a general recipe (the "Master Theorem") to solve recurrences,
cf. Cormen Sections 4.4 & 4.5 (Section 4.6.1 is optional) or Howell Sections 3.7-8: Discuss model solutions for Assignment 2 (now graded).
12: Sep 22 (Mon)
Wrap up the Master Theorem: We embark on a detailed study of the divide and conquer paradigm, with applications such as We discuss the upcoming Assignment 4.
13: Sep 24 (Wed)
Show how clever application of the divide and conquer paradigm enables Further discuss Assignment 4, due tomorrow at 11pm.
14: Sep 26 (Fri)
Show one more application of divide & conquer: Discuss model solutions for Assignment 3.
15: Sep 29 (Mon)
Introduce graphs which may Briefly motivate the upcoming Assignment 5.
16: Oct 1 (Wed)
Prepare for Exam 1, discussing relevant questions from Discuss model solutions for Assignment 4.
17: Oct 3 (Fri)
Exam 1
18: Oct 6 (Mon)
Introduce the heap data structure, cf. Cormen Chapter 6 or Howell Sections 5.1-2&6, used for Discuss the upcoming Assignment 5.
19: Oct 8 (Wed)
20: Oct 10 (Fri)
Present amortized analysis, cf Cormen Chapter 17 (or Howell Sections 4.3&4.5), illustrated by
21: Oct 13 (Mon)
Introduce union/find structures, useful to represent equivalence classes, cf Cormen: Chapter 21, Sections 1-3 (or Howell Chapter 8, Sections 1-3); Briefly discuss the upcoming Assignment 6.
22: Oct 15 (Wed)
23: Oct 17 (Fri)
Introduce dynamic programming (Cormen 15.1 & 15.3)
which often allows an efficient implementation of exhaustive search, as illustrated by Hand back, and discuss, graded Exam 1.
24: Oct 20 (Mon)
Further study applications of dynamic programming: Motivate the upcoming Assignment 7.
25: Oct 22 (Wed)
Give one further application of dynamic programming: Discuss model solutions for Assignment 6.
Assignment 7 due tomorrow at 11pm.
26: Oct 24 (Fri)
One last application of dynamic programming: We embark on greedy algorithms (the topic of Cormen 16 or Howell 11):
27: Oct 27 (Mon)
Continue greedy algorithms:
28: Oct 29 (Wed)
See other examples of the greedy paradigm: Further discuss Assignment 8, due tomorrow at 11pm.
29: Oct 31 (Fri)
Discuss depth-first traversal of graphs, directed as well as undirected (Cormen 22.3 or Howell 13.1-3). Discuss model solutions for Assignments 7 and 8.
30: Nov 3 (Mon)
See how depth-first traversal can be augmented into Prepare for Exam 2, discussing relevant questions from Fall 2013 and Fall 2012.
31: Nov 5 (Wed)
Exam 2
32: Nov 7 (Fri)
See how depth-first traversal can be augmented into Start introduction to key concepts of probability theory, cf Cormen Chapter 5 (Sect 5.4 cursory only), looking at:
33: Nov 10 (Mon)
Continue probability theory, introducing random variables which may be used to calculate Discuss the upcoming Assignment 9.
34: Nov 12 (Wed)
Finish basic probability theory, illustrated by Motivate randomized algorithms; one important such is Assignment 9 due tomorrow at 11pm.
35: Nov 14 (Fri)
Continue randomized algorithms:
36: Nov 17 (Mon)
37: Nov 19 (Wed)
38: Nov 21 (Fri)
More probabilistic reasoning: Introduce "adversary arguments" to establish lower bounds that are more precise than what information theory would yield
Nov 24-28 (Mon-Fri)
Thanksgiving holiday
39: Dec 1 (Mon)
We embark on discussing what constitutes a really hard problem, cf. Cormen 34.1-2 or Howell 16.2-3:
40: Dec 3 (Wed)
Continue the discussion of what is a really hard problem: Discuss Assignment 10, due tomorrow at 11pm.
41: Dec 5 (Fri)
Present several polynomial-time reductions (so as to show that various problems are NP-hard):
42: Dec 8 (Mon)
Finish the slides on NP: Embark on Approximation Algorithms: Discuss the upcoming Assignment 11.
43: Dec 10 (Wed)
Discuss the binary knapsack problem (cf Howell 17.2): Present two seemingly equivalent problems (Howell 17.5) where Further discuss Question 2 (where C is for extra credit) in Assignment 11, due tomorrow at 11pm.
44: Dec 12 (Fri)
General review session:
Dec 16 (Tue)
Final exam, 11:50am - 1:40pm

Torben Amtoft