book

Discovering Computer Science

by Jessen Havill

June 2015

Intermediate to advanced

750 pages

19h 47m

English

CRC Press

Read now

Unlock full access

1.1 PROBLEMS AND ABSTRACTION1.2 ALGORITHMS AND PROGRAMS1.3 EFFICIENT ALGORITHMSOrganizing a phone treeA smoothing algorithmA better smoothing algorithm1.4 COMPUTERS ARE DUMBInside a computerMachine languageEverything is bitsThe universal machine1.5 SUMMARY1.6 FURTHER DISCOVERY
2.1 WELCOME TO THE CIRCUS2.2 ARITHMETICFinite precisionDivisionOrder of operationsComplex numbers2.3 WHAT’S IN A NAME?2.4 USING FUNCTIONSBuilt-in functionsStringsModules*2.5 BINARY ARITHMETICFinite precisionNegative integersDesigning an adderImplementing an adder2.6 SUMMARY2.7 FURTHER DISCOVERY

3.1 DATA ABSTRACTION3.2 VISUALIZATION WITH TURTLESDrawing with iteration3.3 FUNCTIONAL ABSTRACTIONFunction parametersLet’s plant a garden3.4 PROGRAMMING IN STYLEProgram structureDocumentationDescriptive names and magic numbers3.5 A RETURN TO FUNCTIONSReturn vs. print3.6 SCOPE AND NAMESPACESLocal namespacesThe global namespace3.7 SUMMARY3.8 FURTHER DISCOVERY
4.1 DISCRETE MODELSManaging a fishing pondMeasuring network valueOrganizing a concert4.2 VISUALIZING POPULATION CHANGES4.3 CONDITIONAL ITERATION*4.4 CONTINUOUS MODELSDifference equationsRadiocarbon datingTradeoffs between accuracy and timePropagation of errorsSimulating an epidemic*4.5 NUMERICAL ANALYSISThe harmonic seriesApproximating πApproximating square roots4.6 SUMMING UP4.7 FURTHER DISCOVERY4.8 PROJECTSProject 4.1 Parasitic relationshipsProject 4.2 Financial calculators*Project 4.3 Market penetration*Project 4.4 Wolves and moose
5.1 RANDOM WALKSA random walk in Monte CarloHistograms*5.2 PSEUDORANDOM NUMBER GENERATORSImplementationTesting randomness*5.3 SIMULATING PROBABILITY DISTRIBUTIONSThe central limit theorem5.4 BACK TO BOOLEANSShort circuit evaluationComplex expressions*Using truth tablesMany happy returns5.5 A GUESSING GAME5.6 SUMMARY5.7 FURTHER DISCOVERY5.8 PROJECTSProject 5.1 The magic of pollingProject 5.2 Escape!
6.1 COUNTING WORDS6.2 TEXT DOCUMENTSReading from text filesWriting to text filesReading from the web6.3 ENCODING STRINGSIndexing and slicingCreating modified stringsEncoding characters6.4 LINEAR-TIME ALGORITHMSAsymptotic time complexity6.5 ANALYZING TEXTCounting and searchingA concordance6.6 COMPARING TEXTS*6.7 GENOMICSA genomics primerBasic DNA analysisTransforming sequencesComparing sequencesReading sequence files6.8 SUMMARY6.9 FURTHER DISCOVERY6.10 PROJECTSProject 6.1 Polarized politics*Project 6.2 Finding genes
7.1 HOW TO SOLVE ITUnderstand the problemDesign an algorithmImplement your algorithm as a programAnalyze your program for clarity, correctness, and efficiency*7.2 DESIGN BY CONTRACTPreconditions and postconditionsChecking parametersAssertions*7.3 TESTINGUnit testingRegression testingDesigning unit testsTesting floating point values7.4 SUMMARY7.5 FURTHER DISCOVERY
8.1 SUMMARIZING DATA8.2 CREATING AND MODIFYING LISTSList accumulators, reduxLists are mutableTuplesList operators and methods*List comprehensions8.3 FREQUENCIES, MODES, AND HISTOGRAMSTallying valuesDictionaries8.4 READING TABULAR DATA*8.5 DESIGNING EFFICIENT ALGORITHMSA first algorithmA more elegant algorithmA more efficient algorithm*8.6 LINEAR REGRESSION*8.7 DATA CLUSTERINGDefining similarityA k-means clustering exampleImplementing k-means clusteringLocating bicycle safety programs8.8 SUMMARY8.9 FURTHER DISCOVERY8.10 PROJECTSProject 8.1 Climate changeProject 8.2 Does education influence unemployment?Project 8.3 Maximizing profitProject 8.4 Admissions*Project 8.5 Preparing for a 100-year floodProject 8.6 Voting methodsProject 8.7 Heuristics for traveling salespeople
9.1 TWO-DIMENSIONAL DATA9.2 THE GAME OF LIFECreating a gridInitial configurationsSurveying the neighborhoodPerforming one passUpdating the grid9.3 DIGITAL IMAGESColorsImage filtersTransforming images9.4 SUMMARY9.5 FURTHER DISCOVERY9.6 PROJECTSProject 9.1 Modeling segregationProject 9.2 Modeling ferromagnetismProject 9.3 Growing dendrites
10.1 FRACTALSA fractal treeA fractal snowflake10.2 RECURSION AND ITERATIONSolving a problem recursivelyPalindromesGuessing passwords10.3 THE MYTHICAL TOWER OF HANOI*Is the end of the world nigh?10.4 RECURSIVE LINEAR SEARCHEfficiency of recursive linear search10.5 DIVIDE AND CONQUERBuy low, sell highNavigating a maze*10.6 LINDENMAYER SYSTEMSFormal grammarsImplementing L-systems10.7 SUMMARY10.8 FURTHER DISCOVERY10.9 PROJECTS*Project 10.1 Lindenmayer’s beautiful plantsProject 10.2 GerrymanderingProject 10.3 Percolation
11.1 BINARY SEARCHEfficiency of iterative binary searchA spelling checkerRecursive binary searchEfficiency of recursive binary search11.2 SELECTION SORTImplementing selection sortEfficiency of selection sortQuerying data11.3 INSERTION SORTImplementing insertion sortEfficiency of insertion sort11.4 EFFICIENT SORTINGInternal vs. external sortingEfficiency of merge sort*11.5 TRACTABLE AND INTRACTABLE ALGORITHMSHard problems11.6 SUMMARY11.7 FURTHER DISCOVERY11.8 PROJECTSProject 11.1 Creating a searchable databaseProject 11.2 Binary search trees
12.1 MODELING WITH GRAPHSMaking friends12.2 SHORTEST PATHSFinding the actual paths12.3 IT’S A SMALL WORLD...Clustering coefficientsScale-free networks12.4 RANDOM GRAPHS12.5 SUMMARY12.6 FURTHER DISCOVERY12.7 PROJECTSProject 12.1 Diffusion of ideas and influenceProject 12.2 Slowing an epidemicProject 12.3 The Oracle of Bacon
13.1 DESIGNING CLASSESImplementing a classDocumenting a class13.2 OPERATORS AND SPECIAL METHODSString representationsArithmeticComparisonIndexing13.3 MODULESNamespaces, redux13.4 A FLOCKING SIMULATIONThe World ADTThe Boid ADT13.5 A STACK ADT13.6 A DICTIONARY ADTHash tablesImplementing a hash tableImplementing indexingADTs vs. data structures13.7 SUMMARY13.8 FURTHER DISCOVERY13.9 PROJECTSProject 13.1 Tracking GPS coordinatesProject 13.2 Economic mobilityProject 13.3 Slime mold aggregationProject 13.4 Boids in space
A.1 AN INTEGRATED DISTRIBUTIONA.2 MANUAL INSTALLATION
B.1 MATH MODULEB.2 TURTLE METHODSB.3 SCREEN METHODSB.4 MATPLOTLIB.PYPLOT MODULEB.5 RANDOM MODULEB.6 STRING METHODSB.7 LIST METHODSB.8 IMAGE MODULEB.9 SPECIAL METHODS

Content preview from Discovering Computer Science

It has often been said that a person does not really understand something until after teaching it to someone else. Actually a person does not really understand something until after teaching it to a computer, i.e., expressing it as an algorithm.

Donald E. KnuthAmerican Scientist (1973)

NUMBERS are some of the simplest and most familiar objects on which we can compute. Numbers are also quite versatile; they can represent quantities, measurements, identifiers, and are a means of ordering items. In this chapter, we will introduce some of the fundamentals of carrying out computations with numbers in the Python programming language, and point out the ways in which numbers in a computer sometimes behave differently ...