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

1: Aug 21 (Tue)
Introduction to course: We specify the sorting problem, and Cormen Reading: Chapter 1.
Howell Reading: Sections 1.1-2.
2: Aug 23 (Thu)
Using insertion sort as example, we see We then address (cf Howell Sections 1.3 & 2.1) how to prove the correctness of algorithms: Briefly motivate Assignment 1, due next weekend.
3: Aug 28 (Tue)
Continue how to prove program correctness:
4: Aug 30 (Thu)
Wrap up the correctness of recursive programs: Introduce the "Dutch National Flag" problem: Briefly embark on asympotic notation.
Assignment 1 due over the weekend.
5: Sep 4 (Tue)
Embark on asymptotic notation, cf. Cormen Chapter 3 or Howell Section 3.1: Motivate the upcoming Assignment 2.
6: Sep 6 (Thu)
Wrap up asymptotic notation: Address the complexity of iterative algorithms,
where we for the analysis of (nested) loops need to estimate sums (cf. Howell 3.4-6): Further discuss Assignment 2, due over the weekend.
7: Sep 11 (Tue)
Wrap up the slides Analyze: Introduce general recurrences: Discuss (the first half of) the upcoming Assignment 3.
8: Sep 13 (Thu)
Address how to solve general recurrences:
9: Sep 18 (Tue)
Continue the Master Theorem: Introduce graphs which (cf. Cormen's Appendix B.4 & B.5)
10: Sep 20 (Thu)
Continue graphs which Further discuss Assignment 4, due over the weekend.
11: Sep 25 (Tue)
We embark on a detailed study of the divide and conquer paradigm, with natural applications such as Prepare for Exam 1:
12: Sep 27 (Thu)
Exam 1
13: Oct 2 (Tue)
Introduce the heap data structure, cf. Cormen 6.1-2 (or Howell Sections 5.1-2&6), which Discuss and give back graded Exam 1.
Briefly discuss the upcoming Assignment 5.
14: Oct 4 (Thu)
Wrap up heaps: Introduce other clever applications of Divide & Conquer: Assignment 5 due over the weekend.
Oct 9 (Tue)
Class canceled due to KSUnite
15: Oct 11 (Thu)
More examples of Divide & Conquer:
16: Oct 16 (Tue)
Introduce dynamic programming (Cormen 15.1 & 15.3) which allows an efficient implementation of exhaustive search in many situations, such as:
17: Oct 18 (Thu)
More examples of dynamic programming: Mention that in some situations, a subpart of an optimal solution is not necessarily an optimal solution to the subproblem.
18: Oct 23 (Tue)
We embark on greedy algorithms (the topic of Cormen 16 or Howell 11):
19: Oct 25 (Thu)
Continue greedy algorithms: Introduce the concept of equivalence relations (which union/find structures help to represent).
20: Oct 30 (Tue)
Introduce union/find structures, useful to represent equivalence classes (in particular connected components in graphs): Prepare for Exam 2: Didn't have time to discuss Assignments 5-8, but model solutions are uploaded
21: Nov 1 (Thu)
Exam 2
22: Nov 6 (Tue)
Introduction to key concepts of probability theory (such as random variables and expectations),
cf Cormen Chapter 5 (Sect 5.4 cursory only), so as to calculate Discuss Questions 1 and 2 in the upcoming Assignment 9.
23: Nov 8 (Thu)
Finish basic probability theory: Motivate randomized algorithms, and
24: Nov 13 (Tue)
We embark on discussing what constitutes a really hard problem, cf. Cormen 34.1-2 or Howell 16.2-3: Discuss Questions 1 and 2 in the upcoming Assignment 10.
25: Nov 15 (Thu)
Nov 19-23 (Mon-Fri)
Thanksgiving holiday
26: Nov 27 (Tue)
Wrap up NP-hard problems: Motivate Approximation Algorithms (cf. Cormen 35.0&1):
27: Nov 29 (Thu)
Continue knapsack problems and their approximations: Embark on the slides LowerBounds:
28: Dec 4 (Tue)
Discuss how to approximate the Traveling Salesman Problem (Cormen 35.2 and Howell 17.4): Wrap up randomized algorithms:
29: Dec 6 (Thu)
General review session, preparing for the final exam:
Dec 13 (Thu)
Final exam, 2:00 - 3:50pm


Torben Amtoft