The Science of Sudoku ---------------------------------------------------------------------- Design and analysis of algorithms Important properties of algorithms: correctness, efficiency (time and space), scalability, programmer's time, simplicity, modularity, maintainability, security, functionality, robustness, user-friendliness, extensibility, reliability, ---------------------------------------------------------------------- large numbers 10^80 atoms in the universe 10^40 flops on the fastest computer before sun dies ---------------------------------------------------------------------- sudoku: efficient solver 1: waste of time 2: fun, but irrelevant 3: fundamental to CS (+math+science) ---------------------------------------------------------------------- PLAN computational complexity asymptotic complexity efficient algorithms: P efficient verification: NP brute force reductions NP-completeness P vs NP: ? ---------------------------------------------------------------------- function: i -> o x,y -> x+y turing-machine steps (turing equivalence) solvability: halting problem (turing) -> computer program ---------------------------------------------------------------------- asymptotic complexity depends on implementation moore's law: density (-> speed) doubles every 18 months cannot go on for ever: 2004 speed stopped, now cores double still: physical limits: transistor >= atom, speed <= c asymptotic: define speed as #steps given function(size of input) ---------------------------------------------------------------------- addition: "greek" / "hindu" exponential / linear similar: sorting: permute and test O(n!) > O(2^n) quicksort: O(n*logn) complexity of a problem = complexity of best algorithm efficient: n, n*logn, n^3, ... (polynomial) inefficient: 2^n, 2^sqrt(n), n!, n^n ... ---------------------------------------------------------------------- Algorithms change the world Hoare - Quicksort Dijkstra - Dijkstra's algorithm | Shortest Path Cooley-Tukey - FFT Berlekamp Massey - Error correction Reed Solomon Knuth - KMP (Knuth Morris Pratt) string matching: ABC_ABCDEFGH ABC Page&Brin - PageRank ---------------------------------------------------------------------- P efficient algorithm for FINDING a solution ---------------------------------------------------------------------- what about Factoring 1541 = 23*67 2^67-1 = ? * ? <= O(2^sqrt(n)) 761838257287 * 193707721 147573952589676412927 travelling salesperson problem solving sudoku verification is easy: 23*67 -> 1541 (n^2, n*logn) sudoku: n^3 naive in common: finding a solution is hard (exponential or worse), but VERIFYING a solution is easy ((low-order) polynomial) NP (nondeterministic polynomial-time hard) brute force: generate-and-test every possible solution Fact: P subset NP Conjecture: P != NP (million dollar question) NP examples: Math: finding a proof for a statement Science: finding a theory explaining some data Engineering: finding a design given constraints IF P == NP -> all easy .. NP-completeness (efficient, polynomial) transformation between NP problems SAT is NP-complete Graph colouring is NP-complete Sudoku is NP-complete [Factoring: unknown?] ==> efficient Sudoku solver => P == NP [Quantum computing] Phase transition in optimization/search: some slides http://www.cs.cornell.edu/home/selman/ai-phys1/sld001.htm book: Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics, by Hartmann et al, 2005 ---------------------------------------------------------------------- http://en.wikipedia.org/wiki/Algorithmics_of_sudoku http://en.wikipedia.org/wiki/Mathematics_of_Sudoku http://en.wikipedia.org/wiki/Sudoku http://en.wikipedia.org/wiki/Insertion_sort http://makeyourmark.ac.nz/videos.html http://www.keanewzealand.com/wcnz/2009-awards-winners.html based on a public lecture given by Avi Wigderson a couple of years ago: http://math.ias.edu/~avi/ using bc: define factor(x) { auto i,max; max = sqrt(x)+1; for ( i = 3 ; i < max ; i += 2 ) { if (( x % i ) == 0) { return i; } } return -1; } . . 9 | 6 . . | . 1 . 8 2 . | . . . | . . . . . 6 | 8 9 2 | . . . ------+-------+------ 5 . 2 | 9 . 6 | 4 . 7 9 . 7 | 2 . 4 | 5 . 1 6 . 1 | 5 . 7 | 9 . 3 ------+-------+------ . . . | 4 7 8 | 2 . . . . . | . . . | . 9 4 . 6 . | . . 9 | 3 . . . 4 . | . . . | 6 3 . 9 . . | 7 . . | . . . . . 7 | . 6 5 | 2 . . ------+-------+------ . . . | . . . | . 7 . . 1 . | 9 . 3 | . 4 . . 2 . | . . . | . . . ------+-------+------ . . 3 | 8 5 . | 7 . . . . . | . . 9 | . . 3 . 9 1 | . . . | . 8 .