Algorithms - general.md (1168B)
1 +++ 2 title = "Algorithms - general" 3 +++ 4 5 # Algorithms - general 6 7 some problems can’t be solved, some can, and some efficiently. 8 efficiency is speed, power, security, etc. but in this class mainly speed. 9 10 example algorithm — Euclid’s greatest common divisor. 11 12 - two non-negative numbers a ≥ b 13 - if b = 0, return a 14 - if b ≠ 0, then find gcd of b and (a mod b) 15 16 important aspects: 17 18 - correctness — does it output what it should? 19 - termination — does it eventually produce output? 20 - efficiency/complexity: how much time/memory does it use 21 22 complexity as a function of input 23 24 - time: how long does it take? 25 - space: how much space does it use? 26 - counting elementary steps, if n is size of input, a function of n is the number of steps 27 - approach — worst-case asymptotic time complexity 28 - function T(n) giving time complexity for input of size n 29 - want to know what happens to T as n gets very large 30 31 need to know how to: 32 33 - give the intuition of the algorithm 34 - give the pseudo-code for the algorithm 35 - apply the algorithm 36 - adapt the algorithm 37 - analyse correctness of the algorithm 38 - analyse (worst-case) time complexity of the algorithm