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 topdown approach to implement it
(the result is the well known insertion sort method)

argue (with the fibonacci function as example)
that the bottomup approach often results
in faster implementations.
Cormen Reading: Chapter 1.
Howell Reading: Sections 1.12.

2: Aug 23 (Thu)

Using insertion sort as example, we see

how to convert topdown design to bottomup 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 readonly 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 readonly).

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 lineartime constantspace 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 "BigO" notation,
and reason about its properties
(cf Howell 3.2)

Introduce
"BigOmega" and
"BigTheta" (cf Howell 3.3),
while distinguishing between
"bestcase" and "worstcase" interpretation
(cf. Cormen p.49; Howell p.57).
Motivate the upcoming Assignment 2.

6: Sep 6 (Thu)

Wrap up asymptotic notation:

Introduce "littleo" (and
"littleomega"), 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.46):

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

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.34).
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.12 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.12
(or Howell Sections 5.12&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 inplace 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 "pseudomedians" 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:

allpair 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
minimumcost 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 singlesource shortest paths,
cf. Howell 11.3 or Cormen 24.3

mention that one by repeated use of Dijkstra's algorithm
can also do allpair 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 13
(or Howell Chapter 8, Sections 13)

we prove that with "UnionbyRank",
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 58,
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.34 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.12 or Howell 16.23:

introduce the class P

motivate the class NP, and then formally define it

define the concept of polynomial
reduction

define the class of NPhard (and NPcomplete) problems

mention the existence of a "first" NPhard 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 NPhard problems, cf.
Cormen 34.45 (except 34.5.3&5) or
Howell 16.45

to prove that those problems
are indeed NPhard we need several
polynomialtime reductions,
some of which we present:

from Clique to VertexCover, cf. Cormen 34.5.2

from CSat to 3Sat, cf. Howell 16.4.

Further discuss Assignment 10, due over the Thanksgiving break.

Nov 1923 (MonFri)

Thanksgiving holiday

26: Nov 27 (Tue)

Wrap up NPhard problems:
 present the reduction
from 3Sat to Clique, cf. Cormen 34.5.1

sketch the reduction
from Sat to CSat, cf Howell 16.4

sketch the reduction
from 3Sat to 3Col 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 comparisonbased 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 "MonteCarlo" algorithms,
in particular for testing if a given number is a prime
(cf. Cormen 31.89)

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
Torben Amtoft