CSCB36H3 Final: CSCB36 All Notes
19 Nov 2012
School
Department
Course
Professor
Document Summary
Proving that a formula or a statement is correct for all values, eg. n(cid:88) i=0 i = n(n + 1) Leads to proving iterative and recursive algorithms cor- rect: algorithm correctness. Software engineering: program veri cation, i. e. , proving that a program or algorithm meets its speci cations and that it eventually will terminate: regular expressions and finite state machines. Language processing: regular expressions are the foun- dation of tools such as perl, grep, awk, emacs, vi. Compiler technology: compilers parse programs and use regular expressions to do so. Cscb36 curriculum!proof by induction!algorithm correctness!iterative algorithms!recursive algorithms!formal languages!regular (dfa)!context-free (pda)!recurrence relations!iterative!divide and conquer!cscb63!cscc73!cscc63!cscb63!cscc73!mmmmm Suppose we have a swiss chocolate bar consisting of a number of squares arranged in a rectangular pattern. The task is to split the bar into small squares with a minimum number of breaks. Make an educated guess, and prove it by induction. Formula: l w chocolate bar needs l w 1 breaks = number of small squares -1.
