DAA Answers 10 - 28 two-mark answers

Need to study algorithms: know standard algorithms and analyse efficiency; cornerstone of CS.
Algorithmics: the study of algorithms; the core of computer science.
Algorithm: unambiguous instructions; required output for any legitimate input in finite time.
Notion diagram: problem -> [algorithm] -> answer.
Euclid formula: gcd(m,n)=gcd(n,m mod n) until 0; gcd(m,0)=m.
Three gcd methods: Euclid, consecutive integer, middle-school.
Problem solving: understand, device, exact/approx, structures, technique, specify, prove, analyse, code.
Design technique: a general approach applicable to many problems.
Pseudocode: natural language + programming constructs, more precise/concise.
Efficiency types: time and space.
Problem types: sorting, searching, string, graph, combinatorial, geometric, numerical.
Geometric problems: closest-pair, convex-hull.
Analysis steps: input size, units, orders of growth, best/worst/average.
Basic operation: most time-consuming op, usually innermost loop.
Running time: T(n) ~ cop x C(n).
Exponential growth: 2^n, n!.
Worst case: input for which the algorithm runs longest.
Best case: input for which it runs fastest.
Average case: typical/random input; not the mean of best and worst.
Amortized: n operations cost much less than n x worst-case of one.
O: t(n)<=c.g(n) for n>=n0.
Omega: t(n)>=c.g(n) for n>=n0.
Theta: c1.g(n)<=t(n)<=c2.g(n) for n>=n0.
Useful property: O(g1)+O(g2)=O(max{g1,g2}).
Efficiency classes: 1, log n, n, n log n, n^2, n^3, 2^n, n!.
Algorithm visualization: images conveying operation, performance, speed.
Two variations: static and dynamic (animation).
Order of growth: performance as a function of input size n.

Home|Contents|Prev|Next|Top|Chat