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

1: Aug 21 (Tue)

Introduction to course:

• go through syllabus
• get acquainted with the Top Hat system
• emphasize that the task of an algorithm is to implement a specification.

We specify the sorting problem, and

• use the top-down approach to implement it (the result is the well known insertion sort method)
• argue (with the fibonacci function as example) that the bottom-up approach often results in faster implementations.

Cormen Reading: Chapter 1.
Howell Reading: Sections 1.1-2.

2: Aug 23 (Thu)

Using insertion sort as example, we see

• how to convert top-down design to bottom-up implementation (Howell Section 1.4)
• how to do simple reasoning about time and space complexity (cf Cormen Section 2.2).

We then address (cf Howell Sections 1.3 & 2.1) how to prove the correctness of algorithms:

• we shall first conside iterative algorithms (cf. Howell Section 2.3 and Cormen Section 2.1)
  • and first consider (on the board and as a quiz) programs on scalars.

Briefly motivate Assignment 1, due next weekend.

3: Aug 28 (Tue)

Continue how to prove program correctness:

• for iterative programs, we now consider some operating on arrays:
  • first a read-only program (for finding the last occurrence of an element in an array)
  • next we again consider insertion sort
    (a full proof is given in Howell's Theorem 2.7 whereas Cormen has a partial proof on p.19)
  • finally we discuss the upcoming Assignment 1 (also read-only).
• for recursive programs (Howell Section 2.2) we need to do explicit mathematical induction.

4: Aug 30 (Thu)

Wrap up the correctness of recursive programs:

• again consider insertion sort (cf. Howell Section 2.2).

Introduce the "Dutch National Flag" problem:

• motivate its relevance
• develop a linear-time constant-space algorithm for it (Howell Section 2.4).

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:

• Introduce the "Big-O" notation, and reason about its properties (cf Howell 3.2)
• Introduce "Big-Omega" and "Big-Theta" (cf Howell 3.3),
  while distinguishing between "best-case" and "worst-case" interpretation (cf. Cormen p.49; Howell p.57).

Motivate the upcoming Assignment 2.

6: Sep 6 (Thu)

Wrap up asymptotic notation:

• Introduce "little-o" (and "little-omega"), cf Howell 3.10.

Address the complexity of iterative algorithms,
where we for the analysis of (nested) loops need to estimate sums (cf. Howell 3.4-6):

• upper approximations are straightforward
• lower approximations require that the functions are smooth
• the key result is summarized as Theorem 3.28 in Howell.

Further discuss Assignment 2, due over the weekend.

7: Sep 11 (Tue)

Wrap up the slides Analyze:

• give examples of how to use Howell's Theorem 3.28
• mention some pitfalls in the analysis of algorithms.

Introduce general recurrences:

• they show up when analyzing divide and conquer algorithms (Cormen Section 2.3).

Discuss (the first half of) the upcoming Assignment 3.

8: Sep 13 (Thu)

Address how to solve general recurrences:

• to check a proposed solution, the substitution method (Cormen Section 4.3) can be used;
  • we illustrate by 3 examples
  • Assignment 3 (due over the weekend) contains 3 similar examples
• present a general recipe, the "Master Theorem"
  (as described in Cormen Section 4.5 or Howell Sections 3.7-8):
  • apply it to some examples

9: Sep 18 (Tue)

Continue the Master Theorem:

• motivate why it holds (cf. Cormen Section 4.4)
• give an example, T(n) = 2T(n/2) + n log(n), where
  • Cormen's Theorem 4.1 is not applicable,
  • the Master Theorem from the slides gives a solution
    sandwiched between n log(n) and n^q for any q > 1,
  • but Howell's Theorem 3.32 gives the exact order n log(n) log(n).
• give an example where to apply it, one needs to define S(k) = T(2^k)
• sketch a proof (cf. Cormen Section 4.6.1 which is optional)

Introduce graphs which (cf. Cormen's Appendix B.4 & B.5)

• may be directed or undirected
• may be acyclic and/or connected

10: Sep 20 (Thu)

Continue graphs which

• are trees if they are acyclic and connected
• may be represented using an adjacency matrix or using adjacency lists
  as described in Cormen 22.1 (or Howell 9.3-4).

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

• merge sort (Howell Section 10.2 or Cormen Section 2.3)
• quicksort (Cormen Sections 7.1-2 or Howell Section 10.3).

Prepare for Exam 1:

• have lively discussions of Assignments 3 and 4
• but didn't find time for Assignments 1 and 2, nor for Exam 1 from Fall 2016

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

• allows priority queue operations to be implemented in logarithmic time, cf. Cormen 6.5
• can be constructed from a heap in linear time, cf. Cormen 6.3

Discuss and give back graded Exam 1.
Briefly discuss the upcoming Assignment 5.

14: Oct 4 (Thu)

Wrap up heaps:

• describe an efficient and in-place sorting algorithm: heapsort, cf. Cormen 6.4
• further discuss the upcoming Assignment 5.

Introduce other clever applications of Divide & Conquer:

• efficient multiplication of large integers (or polynomials, as in Howell Section 10.1)
• matrix multiplication (Cormen Section 4.2)

Assignment 5 due over the weekend.

Oct 9 (Tue)

Class canceled due to KSUnite

15: Oct 11 (Thu)

More examples of Divide & Conquer:

• the selection problem where
  • a naive approach may run in quadratic time
  • we show how "pseudo-medians" enable selection in linear time (Cormen Section 9.3 or Howell Section 10.4)
• the problem in Assignment 6, due over the weekend.

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:

• giving optimal change (Howell 12.1)
• the binary knapsack problem (Howell 12.4)
• the problems in the upcoming Assignment 7 (we postponed discussing them).

17: Oct 18 (Thu)

More examples of dynamic programming:

• all-pair shortest path (Floyd's algorithm, cf Howell 12.3 or Cormen 25.2)
• predicting the likely outcome of a baseball series (Question 1 in the upcoming Assignment 7)
• purchasing baseball players (Question 2 in the upcoming Assignment 7)

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):

• motivate the concept
• show the correctness of a greedy strategy for a simple scheduling problem
• discuss the more complex scheduling problem found in Question 1 in the upcoming Assignment 8
• explore (thru a couple of quizzes) general principles of correctness
• discuss various approaches to construct a minimum-cost spanning tree, cf. Cormen 23 or Howell 11.2:
  • present Kruskal's algorithm, and analyze its running time
  • present Prim's algorithm, and analyze its running time
• present Dijkstra's algorithm for single-source shortest paths, cf. Howell 11.3 or Cormen 24.3
• mention that one by repeated use of Dijkstra's algorithm can also do all-pair shortest paths, cf Question 2 in the upcoming Assignment 8.

19: Oct 25 (Thu)

Continue greedy algorithms:

• give a (rather contrived) example showing that even if a schedule cannot be improved by pairwise swapping it may still not be optimal
• recall Dijkstra's algorithm: analyze its running time (same as Prim's), and argue for its correctness
• present the proof that Kruskal's algorithm returns an optimal solution
• Discuss Question 3 in Assignment 8, due over the weekend.

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):

• they are described in Cormen: Chapter 21, Sections 1-3 (or Howell Chapter 8, Sections 1-3)
• we prove that with "Union-by-Rank", operations can be made to run in logarithmic time
• mention that one can implement union/find so that the amortized cost per operation is almost in O(1).

Prepare for Exam 2:

• discuss questions from the 2016 exam set
• elaborate on Prim's algorithm

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

• how many people must be present in order for a shared birthday to be more likely than not
• the expected number of birthday coincidences
• the expected wait time until success in a sequence of experiments
• the expected cost of "hire and fire" (cf. Cormen 5.2)

Discuss Questions 1 and 2 in the upcoming Assignment 9.

23: Nov 8 (Thu)

Finish basic probability theory:

• recall basic properties (such as linearity) of expectations
• analyze strategies to maximize the chance of hiring the best person when only one person can ever be hired (cf. Cormen 5.4.4)
• discuss Questions 2 and 3 in Assignment 9, due over the weekend.

Motivate randomized algorithms, and

• introduce randomized quicksort (Cormen 7.3-4 or Howell 10.3) whose expected running time we analyze
• discuss how, and how not, to randomly permute an array

24: Nov 13 (Tue)

We embark on discussing what constitutes a really hard problem, cf. Cormen 34.1-2 or Howell 16.2-3:

• introduce the class P
• motivate the class NP, and then formally define it
• define the concept of polynomial reduction
• define the class of NP-hard (and NP-complete) problems
• mention the existence of a "first" NP-hard problem, boolean SATisfiability, cf. Cormen 34.3

Discuss Questions 1 and 2 in the upcoming Assignment 10.

25: Nov 15 (Thu)

• Discuss and give back graded Exam 2.
• We present a number of NP-hard problems, cf. Cormen 34.4-5 (except 34.5.3&5) or Howell 16.4-5
• to prove that those problems are indeed NP-hard we need several polynomial-time reductions, some of which we present:
  • from Clique to VertexCover, cf. Cormen 34.5.2
  • from CSat to 3-Sat, cf. Howell 16.4.
• Further discuss Assignment 10, due over the Thanksgiving break.

Nov 19-23 (Mon-Fri)

Thanksgiving holiday

26: Nov 27 (Tue)

Wrap up NP-hard problems:

• present the reduction from 3-Sat to Clique, cf. Cormen 34.5.1
• sketch the reduction from Sat to CSat, cf Howell 16.4
• sketch the reduction from 3-Sat to 3-Col that is the topic of Question 1 in the upcoming Assignment 11.

Motivate Approximation Algorithms (cf. Cormen 35.0&1):

• discuss the binary knapsack problem (cf Howell 17.2):
  • a simple improvement of a greedy algorithm gives approximation within a factor two
  • a generalization gives us arbitrarily high precision where each approximation is polynomial but with degree that depends on the precision
• discuss a version of the knapsack problem where one can take arbitrary many copies of each item (Question 2 in the upcoming Assignment 11)

27: Nov 29 (Thu)

Continue knapsack problems and their approximations:

• for the fractional knapsack problem, cf.Cormen 16.2, show a greedy strategy that is optimal
• for the version where we allow "arbitrary many copies of each item",
  suggest by examples that the above greedy strategy is not optimal but not too bad either
  as to be formalized in Question 2 in the upcoming Assignment 11
• for the binary version, there exists a fully polynomial approximation scheme:
  we can approximate within an error of 1/k at a cost polynomial even in k.

Embark on the slides LowerBounds:

• all comparison-based sorting algorithms must have running time in Omega(n lg(n))
  as can be seen by looking at the height of decision trees (cf. Cormen 8.1)
• introduce "adversary arguments" to establish lower bounds that are more precise than what information theory would yield
  • as in Cormen 9.1 on finding minimum and maximum
  • or as in detecting whether a graph is connected
  • or as in Question 3 in Assignment 11, due over the weekend.

28: Dec 4 (Tue)

Discuss how to approximate the Traveling Salesman Problem (Cormen 35.2 and Howell 17.4):

• in the general case, there exists no polynomial approximation algorithm (unless P = NP)
• but if the triangle inequality holds, it can be polynomially approximated within a factor two.

Wrap up randomized algorithms:

• mention "Monte-Carlo" algorithms, in particular for testing if a given number is a prime (cf. Cormen 31.8-9)
• mention a couple of pitfalls in probability reasoning.

29: Dec 6 (Thu)

General review session, preparing for the final exam:

• discuss the set from Fall 2016
• discuss solutions for Assignments 9 & 10 & 11
• sketch a hierarchy of complexity classes, where in most cases it is unknown whether the inclusion is strict.

Dec 13 (Thu)

Final exam, 2:00 - 3:50pm