A sequence of unambiguous instructions for solving a problem, giving a required output for any legitimate input in finite time. Properties: Input (zero or more), Output (at least one), Definiteness (clear steps), Finiteness (terminates), Effectiveness (basic steps). File 1 adds: feasible, flexible, efficient, language-independent.
Practical: know a standard set of algorithms, design them, analyse efficiency. Theoretical: algorithms are the cornerstone of computer science. Algorithmics = the study of algorithms; the core of computer science, relevant to most of science, business and technology.
Pseudocode mixes natural language and programming constructs; more precise and concise than natural language. Algorithm = the process/steps, language-independent. Pseudocode = a way to write it; no strict syntax, not standardised. Pros: easy to convert/read/modify, errors spotted early. Cons: no standard, translation errors, does not show design.
Three ways: natural language, flowchart, pseudocode. Conventions: // comments; { } blocks; identifiers start with a letter; no explicit types; records; assignment :=; TRUE/FALSE with AND/OR/NOT; loops (while, for..step, repeat-until); conditionals (if-then, if-then-else, case); read/write; Algorithm Name(params).
Understand the problem -> capabilities of the device -> exact vs approximate -> data structures -> design technique -> specify -> prove correctness -> analyse -> code and test. Notes: correct = works for all legitimate inputs; algorithm + data structures = program; correctness proved by induction.
gcd(m,n) = largest integer dividing both. (a) Euclid: gcd(m,n)=gcd(n, m mod n) until m mod n=0; gcd(m,0)=m. (b) Consecutive integer: t=min{m,n}; test divisibility; decrement t. (c) Middle-school: prime-factorise each, take common factors the minimum number of times, multiply. All satisfy finiteness, definiteness, effectiveness.
A general approach to solving problems algorithmically, applicable to many problems. Examples: brute force, divide & conquer, greedy, decrease & conquer, dynamic programming, transform & conquer, backtracking.
Using images to convey information about an algorithm's operation, performance, or speed. Static: a series of still images. Dynamic (animation): continuous, movie-like.
Pros: effective communication, easy debugging, easy/efficient coding, language independence. Cons: time-consuming for complex problems, hard to follow complex logic. "Algorithm" derives from al-Khowarizmi.