DAA Answers 11 - 9 sixteen-mark answers (skeletons)

Explain an algorithm with an example. Definition -> characteristics -> three gcd methods (DAA-Q1, Q6).
Fundamentals of problem solving. Understand -> device -> exact/approx -> structures -> technique -> specify -> prove -> analyse -> code (DAA-Q5).
Important problem types. Sorting, searching, string, graph, combinatorial, geometric, numerical (DAA-Q34, Q35).
Analysis of efficiency. Time/space -> input size -> basic op -> growth -> cases -> notation -> recursive/non-recursive (DAA-Q10..Q25).
Asymptotic notations. O, Omega, Theta definitions -> classes -> useful property -> amortized -> little-oh (DAA-Q20..Q25).
Non-recursive analysis. Decide n -> basic op -> input dependence -> summation -> simplify (DAA-Q14..Q17).
Recursive analysis. Decide n -> basic op -> cases -> recurrence + initial condition -> solve (DAA-Q18, Q19, Q27..Q33).
Linear search in detail. Algorithm -> best 1 -> worst n -> average p(n+1)/2+(1-p)n (DAA-Q52).
Tower of Hanoi in detail. Rules -> recursive solution -> M(n)=2M(n-1)+1 -> M(n)=2^n-1 -> n=3 (7 moves) (DAA-Q19).