15-451 Algorithms                  04/29/09
                        recitation notes

* FFT
* Answer questions, go over topics as needed, general review
* Do TA evals
====================================================================

FFT
===
FFT allows us to do a convolution of two vectors of length n in time
O(n log n).  Def of convolution of A and B is vector C such that 
C[i] = A[0]*B[i] + A[1]*B[i-1] + ... + A[i]*B[0].
E.g., if A and B are the vectors of coefficients of polynomials A(x)
and B(x), then C gives the coefficients for the polynomial A(x)*B(x).

Uses: Consider the following problem.  You are given a string P of 1's and
*'s (the ``pattern''), and a string T of 0's and 1's (the ``text'').
You want to find all places where the pattern P appears in text T,
where a star can match either a 0 or a 1.  For instance, if P = 11*1
and T = 10111101, then P appears twice in T: once starting at the
3rd position in T and once starting at the 5th position in T.

Say P has length n and T has length m, where m>n.  There is
a simple O(mn)-time algorithm to solve this problem: try all
O(m) possible starting positions, and for each one, check in time
O(n) to see if $P$ matches there.  

We can use the FFT to do this faster.  All we need to do is reverse P,
change the *'s to zeroes (so in the above example, this would give us
1011), and then do a convolution with T.  We can then scan the result
to see the positions where the value of C[i] equals the number of 1s
in P.




===================================================
General Review
--------------
What the course has been about:
 1. techniques for developing algorithms
 2. techniques for analysis

Break down (1) into
 (a) fast subroutines: useful tools that go *inside* an algorithm.
     E.g., data structures like B-trees, hashing, union-find.  Things
     like sorting, DFS/BFS.

 (b) problems that are important because you can reduce a lot
     of *other* problems to them: network flow, linear programming.

Notion of reduction is important in algorithms and in complexity
theory: 
 - solve a problem by reducing it to something you know how to do.
 - show a problem is hard by reducing a known hard problem to it.



Let's organize the algorithms and problems we've discussed in class
along a "running time" line.

sublinear  ---  linear --- near-linear  ---  low-degree poly  ---  general poly(n) ---  hard but probably not NP-complete  ---  NP-complete 



sublinear:
 - data structures: hashing, balanced search trees, heaps, union find.

linear:
 - depth-first search, breadth-first search, topological sorting
 - selection/median-finding

near-linear:
 - greedy algs with good data structures
   -  Prim, Kruskal, Dijkstra
 - divide-and-conquer algorithms
   - sorting, FFTs

low-degree & general poly(n):
 - dynamic programming: Bellman-Ford, LCS, etc.
 - network flow, matchings, min-cost flow
 - linear programming
 - Graph matrix algorithms
 - primality testing (we didn't really worry about exact running time)

Hard-but-not-probably-not-NP-complete:
 - factoring

NP-complete:
 - 3-SAT, Vertex cover, Clique, TSP, etc.

----------------------------------------------------------------

Algorithm tools and where they are typically used:
* Dynamic programming: typically for improving exponential time down to
	polynomial. 
* Reducing to LP, or reducing to network flow: likewise, typically for
	improving exponential time down to polynomial. 
* Divide-and-conquer: typically for getting from O(n^2) to O(n log n).
        Sometimes just for reducing exponent (like Karatsuba or Strassen).
* Data structures: ditto
* Randomization: everywhere.
* Approximation algorithms: typically for NP-complete problems, but
        sometimes also makes sense for easier problems too.

----------------------------------------------------------------

Analysis tools:
* Amortized analysis, Potential functions, piggy banks:
    Typically for showing O(1) or O(log n) amortized cost per operation
* Reductions:  proving NP-completeness by reducing a known NP-complete
    problem to it, or giving a poly-time algorithm by reducing to a
    problem like LP or network flow. 
* Recurrences.  Esp with divide-and-conquer
* Linearity of expectation
* Group properties for number-theory algs.

=====================================