The Role of Science and Mathematicsin Software DevelopmentRobert SedgewickPrinceton UniversityIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsThe scientific methodis essential in applications of computation A personal opinion formed on the basis of decades of experience as a•CS educator•author•algorithm designer•software engineer•Silicon Valley contributor•CS researcherPersonal opinion . . . or unspoken consensus?IntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsUnfortunate factsMany scientists lack basic knowledge of computer scienceMany computer scientists lack back knowledge of science1970s: Want to use the computer? Take intro CS.2000s: Intro CS course relevant only to future cubicle-dwellersOne way to address the situation•identify fundamentals•teach them to all studentswho need to know them•as early as possibleIntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsOne way to address the situationTeach the same course to all science/engineering studentsAll students learn the importance of•modern programming models•the scientific method in understanding program behavior•fundamental precepts of computer science•computation in a broad variety of applications•preparing for a lifetime of engaging with computation www.cs.princeton.edu/introcsIntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsScience/engineering students at Princetontake the same intro CS course, most in the first yearGoals•demystify computer systems•empower students to exploit computation•build awareness of intellectual underpinnings of CS•Basic control structures•Standard input and output streams•Drawings, images and sound•Data abstraction•Use any computer, and the web•Applications programming•Understanding of the costs•Fundamental data types•Computer architecture•Computability and Intractabilitymodern programming modelrelevant CS conceptsIntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsExamples and assignmentsuse familiar easy-to-motivate applicationsIdeal programming example/assignment•teaches a basic CS concept•solves an important problem•appeals to students’ intellectual interest•illustrates modular programmingBouncing balls N-body Bose-EinsteinOOP is helpful data-driven programs are useful efficient algorithms are necessaryBouncing ballsimulation is easyIntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsUnderlying message: performance mattersin a large number of interesting applicationsSimple fact: quadratic algorithms are useless in modern applications•millions or billions of inputs•1012 nanoseconds is 15+ minutes•1018 nanoseconds is 31+ yearsSimple test: Doubling hypothesis•Perform experiments, measure T(N) and T(2N)•if T(2N)/T(N) ~ 4, need another algorithmLessons: 1. Efficient algorithms enable solution of problems that could not otherwise be addressed. 2. Scientific method is essential in understanding program performanceImportant lessons for•beginners•software engineers•scientists•[everyone]•Web commerce•Bose-Einstein model•String matching for genomics•Natural language analysis•N-body problem...[ long list ]IntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsThe scientific methodis essential in understanding program performanceScientific method•create a model describing natural world•use model to develop hypotheses•run experiments to validate hypotheses•refine model and repeatAlgorithm designer who does not experiment gets lost in abstractionSoftware developer who ignores cost risks catastrophic consequences modelhypothesisexperimentIntroduction1950s: uses scientific method 2000s: uses scientific method?IntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsPreliminary hypothesis (needs checking)Modern software requires huge amounts of codeIntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsPreliminary hypothesis (needs checking)Modern software development requires huge amounts of code butperformance-critical code implements relatively few fundamental algorithmsIntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsWarmup: random number generationProblem: write a program to generate random numbersmodel: classical probability and statisticshypothesis: frequency values should be uniform weak experiment:•generate random numbers•check for uniform frequenciesbetter experiment:•generate random numbers•use !2 test to check frequencyvalues against uniform distribution better hypotheses/experiments still needed•many documented disasters•active area of scientific research•applications: simulation, cryptography•connects to core issues in theory of computationV = 10random?modelhypothesisexperimentint k = 0;while ( true ) System.out.print(k++ % V);int k = 0;while ( true ){ k = k*1664525 + 1013904223); System.out.print(k % V);}0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 . . .textbook algorithm that flunks !2 test IntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsWarmup (continued)Q. Is a given sequence of numbers random?A. No.Q. Does a given sequence exhibit some property that random number sequences exhibit?Birthday paradox Average count of random numbers generated until a duplicate happens is about "V/2Example of a better experiment: •generate numbers until duplicate•check that count is close to "V/2•even better: repeat many times, check against distribution•still better: run many similar tests for other properties“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin” — John von NeumannV = 365average probesuntil duplicateis about 24IntroductionIntroductionMotivating exampleGrid graphsSearch methodsSmall world graphsAnalytic combinatoricsDetailed example: paths in graphsA lecture within a lectureIntroductionMotivating exampleGrid graphsSearch methodsSmall