CS421 - Advanced Data Structures and Algorithm Development - Chapter 1 OverView

• "How can we decide in advance how long a program will take to run?"
• A difficulty measure should have the following characteristics:
  • it should measure effort that we care about
  • it should be quantitative
  • it should be easy to compute
  • it should be a good predictor
• "In general, to analyze a problem we need to pick a measure of problem size and a measure of solution effort, then see how they relate; the measure of solution effort should have at least the four properties itemized above."
• PAUSE: Do the three fragments in Figure 1.1 do the same thing?
• PAUSE: If the run time grows like n³, what happens if we double the input?
• PLAN:
  1. recognize the problem
  2. build an abstract model
  3. design an algorithm to solve the problem within the model
  4. analyze both the algorithm and the problem within the model
  5. compare the upper and lower bounds to see if the solution is good enough

1. Problems
   We want to identify solvable problems, and for each such problem we want bounds on the computational cost. Our aim is to solve problems with as little computational effort per problem instance as possible.
   • Problem Types
     • Search problems: find an X in the input satisfying property Y. [ch. 2-3]
     • Structured problems: Transform the input to satisfy property Y. [ch. 4-5]
     • Construction problems: Build an X satisfying property Y. [ch. 5-6]
     • Optimization problems: Find the best X satisfying property Y. [ch. 6-7]
     • Decision problems: Decide whether the input satisfies property Y. [ch. 6-7]
     • Adaptive problems: Maintain property Y over time.
   • Categories of hard problems
     • A conceptually hard problem (don't understand the problem well enough)
     • An analytically hard problem (don't know how to analyze how long it will take to solve every problem instance)
     • A computationally hard problem (relatively small problem instances will take millions of years to solve)
     • A computationally unsolvable problem (no algorithm can exist)
   • Towers of Hanoi problem
2. Models
   The set of legal operations is the environment and the subset of operations we want to minimize is the goal. The environment and the goal together make up the model.
3. Algorithms - finite sequence of operations, each chosen from a finite set of well-defined operations.
   • PAUSE: Think about the algorithm for solving the Towers of Hanoi.
   • An algorithm that uses itself to solve a problem is called a recursive algorithm.
   • The forward-backward strategy: Solve simple special cases and then generalize their solution, then test the generalization on other special cases.
4. Analysis
   • Upper Bounds
     "Analysis first involves figuring out bounds on the number of operations an algorithm performs given an input of size n. Usually we will first find its worst cost, that is, the maximum number of times it performs the chosen operation. since the algorithm is proof that we can solve the problem using at most that number of operations, even in the worst case, this gives an upper bound on the problem's worst cost as a function of n.

     PAUSE: Can the average cost be worse than the worst cost, or better than the best cost?

     Find the average cost (=worst cost) for the Towers of Hanoi.

     PAUSE: Show the cost to equal 2ⁿ - 1.

     Proof by Induction:

     1. Basic Step: HANOI makes one disk move when n = 1, so f(1) = 1. f(1) = 2¹ - 1. Therefore, f(n) = 2ⁿ - 1 when n = 1.
     2. Inductive Step: Suppose that for all k < n, f(k) = 2^k - 1. then since n > 1, from the recurrence we must have that f(n) = 2f(n - 1) + 1. But n > n - 1. Therefore f(n) = 2 (2^n-1 - 1) + 1 = 2ⁿ - 1.
     3. Hence, if the inductive assumption is true for all k < n then it is true for n as well. Thus, f(n) = 2ⁿ - 1 for all n.

   • Lower Bounds
     The smallest number of operations necessary to solve the problem over all inputs of size n is the lower bound. on the problem's worst cost. An upper bound is a measure of how bad a particular algorithm can be; a lower bound is a measure of how hard a particular problem is.
     Let g(n) = an upper bound and h(n) = a lower bound; If beyond some point g(n) - h(n) <= c, for some constant c, then there is no point looking for a better algorithm; up to a constant, A is as good a solution as is possible within M. A is worst case optimal for problem P.
     If g(n) - h(n) > c for any c, even for large n, but beyond some point g(n)/h(n) <= c, for some non-zero constant c then within M, A is worst case asymptotically optimal for P. [asymptotic upper bound: f(n) = O(g(n)) if there exists positive constants c, n₀ such that f(n) <= c g(n) for all n > n₀

     In HANOI, we must move every disk but the biggest at least twice and the the biggest at least once so 2n - 1 is a lower bound. But each time we move the biggest disk, we must also move all n-1 disks, so f(n) >= f(n-1) [f is non-decreasing].
     PAUSE: Use induction to show that f(n) >= 2ⁿ - 1.

   ---

5. Now What?
   if the upper and lower bounds match then stop,
   else if they're close enough or the problem isn't that important then stop,
   else if the model focuses on the wrong thing, then restate it,
   else if the algorithm is too fat then generate a slimmer algorithm,
   else if the lower bound is too weak then generate a stronger lower bound.
   repeat to perfection or exhaustion.
6. Napkin Mathematics
   log_xy = z «==» x^z = y «==»x^log_xy = y
   log_x(rs) = log_xr + log_xs   and   log_x(r/s) = log_xr - log_xs  and  lga^b = b lga

   Compare n! with 2ⁿ and 2²ⁿ
   Write their recurrence functions
   PAUSE: Use induction to show that n! >= 2²ⁿ for n >= 9.
   Binomial Theorem and Binomial coefficients
   Fibonacci
   Find the amount of work done by the code fragment in Figure 1.1 (pg.33)
   Summations
   PAUSE: Estimate the summation of (ai + b) from 1 to n.
   The subtract-and-guess or divide-and-guess strategy: To find the value of the sum f, pick a known function g and find a pattern in the terms f(n) - g(n) or f(n) / g(n)
   e.g. to find the summation of i from 1 to n, compare with g(n) where g(n) is summation of 1 from 1 to n and then divide
   PAUSE: What is the summation of n²
   How fast do the Fibonacci numbers grow?

7. Growth Rates
   Two functions of n have different growth rates if as n goes to infinity their ratio either goes to infinity or to zero. If their ratio stays near a non-zero constant then they are asymptotically the same function.
   Compare function in terms of the number of digits [pg. 39]
   Do all these functions have different growth rates? IF we take the ratio of any two, does the ratio go to zero or infinity? Or stay near a non-zero constant?
   Is there a constant so large that if we nultiply n by it, the resulting function is always large than n². PROVE IT!
   Order: lg lg n  lg n  lg²n  n^1/10  sqrt n  n  n lg n  n²  2ⁿ  n!  2²ⁿ  2^n!
   • Limits [lim f(n) as n approaches infinity is defined as: for all s > 0, there exists a c > 0 such that if n > 0 implies that r+s > f(n) > r-s
   • Order Notation

     f=o(g)	f is slower than g
     f=O(g)	f is no faster than g
     f=Q(g)	f is about as fast as g[f=O(g) and g=O(f)]
     f~g	f is as fast as g
     f=W(g)	f is no slower than g [g=O(f)]

     A function f is O of g if there are positive constants r and c such that f(n) <= r g(n) for all n bigger than c. [f =O(g)]
     o is like <; O is like <=; Q [theta] is like "roughly equal"; ~ is like= ; W [omega] is like >=

     Q(1)	constant
     Q(lg n)	logarithmic
     Q(lgc n, c>=1	polylogarithmic
     Q(nr)0<r<1	sublinear
     Q(n)	linear
     Q(nr1<r<2)	subquadratic
     Q(n2)	quadratic
     Q(n3)	cubic
     Q(nc, c>=1)	polynomial
     Q(rn, r>1)	exponential

   • Manipulating Order Notation
     lim f(n) / g(n) = r implies f = O(g)
     lim f(n) / g(n) = r > 0 implies f = Q(g)
     n = O(n²)
     PAUSE: Show that if n = o(n²) then (n²) is not O(n)
   • Differentiation [definition and examples]; l'Hopital's Rule
     Show that lg n = o(sqrt (n))
     Show that lg²n = o(n^1/10)

   ---

8. Back to Reality
   
• How big must the input be before it is better to use a slower growing algorithm? (constant multipliers)
• Misleading to perform arbitrary operations on functions (i.e. log of n² vs. 2^n/10: without logs functions are approx. = at 150, with logs approx. = at 2¹⁵⁰)
• How long should you spend figure out which function is "better"?
Should we forget about "infinitely growing" inputs? [if we do, then all algorithms are constant time!]
If the input is relatively small, then almost any algorithm will do [unless the problem is very common or very hard]. If the input is extremely large, then no algorithm will do.
9. Hard Problems
   • hiker problem
   • domino and chessboard problem
   • Prime #s.
     • Is 667 prime?
     • 2⁶⁷ - 1 = 147573952589676412927 = 193707721 x 761838257287
     • Is (2³⁵³+1)/3 prime?
     • NP complete problems [i.e. satisfiability problem - Can a proposition composed of variables that can only have two logical values ever be true (be satisfied)?]
   • Solving Hard Problems
     • dynamic programming
     • greedy algorithm
     • approximation algorithm
     • probabilistic algorithm - guaranteed to work most of the time
       Problem: Decide whether (6x² + 3x³ - x)³ + (6x² - 3x³ + x)³ = (6x²(3x² + 1))²
       Algorithm: Generate a random number and see if it satisfies the equation.
10. Coda - The Continent of Analysis
    • Can we learn all of the tools?
    • 3 kinds of hard but solvable problems: conceptual, analytical, and computationally hard