A Computer Science Tapestry Chapter 1Computer Science and ProgrammingWhat is Computer Science?Computer ScienceStoriesAlgorithms as Cornerstone of CSSearch, Efficiency, ComplexitySorting Experiment: why do we sort?Themes and Concepts of CSTheory, Language, ArchitectureAbstraction, Complexity, ModelsAlan Turing (1912--1954)Complexity: Travelling SalespersonComplexity ClassificationsAre hard problems easy?C.A.R. (Tony) Hoare (b. 1934)Creating a ProgramFrom High- to Low-level languagesLevels of Programming LanguageAlternatives to compilationWhat is digital?What is a computer?Chips, Central Processing Unit (CPU)Why is programming fun?A Computer Science Tapestry1.1A Computer Science TapestryChapter 1A Computer Science Tapestry1.2Computer Science and ProgrammingComputer Science is more than programmingThe discipline is called informatics in many countriesElements of both science and engineering•Scientists build to learn, engineers learn to build–Fred BrooksElements of mathematics, physics, cognitive science, music, art, and many other fieldsComputer Science is a young disciplineFiftieth anniversary in 1997, but closer to forty years of research and developmentFirst graduate program at CMU (then Carnegie Tech) in 1965To some programming is an art, to others a science, to others an engineering disciplineA Computer Science Tapestry1.3What is Computer Science?What is it that distinguishes it from the separate subjects with which it is related? What is the linking thread which gathers these disparate branches into a single discipline? My answer to these questions is simple --- it is the art of programming a computer. It is the art of designing efficient and elegant methods of getting a computer to solve problems, theoretical or practical, small or large, simple or complex. C.A.R. (Tony)HoareA Computer Science Tapestry1.4Computer ScienceArtificial Intelligence thinking machinesScientific Computing weather, cars, heart, modellingTheoretical CS analyze algorithms, modelsComputational Geometry theory of animation, 3-D modelsArchitecture hardware-software interfaceSoftware Engineering engineering, scienceOperating Systems the soul of the machineGraphics from Windows to HollywoodMany other subdisciplinesA Computer Science Tapestry1.5StoriesWho is Shawn Fanning and what did he do (19 years old)?Who is Marc Andreessen and what did he do (21 years old)?Who is Claude Shannon and what did he do (21 years old)?Who is Dmitry Sklyarov and what did he do (26 years old)?Who is Tim Berners-Lee and what did he do (35 years old)?Who is Kary Mullis and what did he do (39 years old)?A Computer Science Tapestry1.6Algorithms as Cornerstone of CSStep-by-step process that solves a problemmore precise than a recipeeventually stops with an answergeneral process rather than specific to a computer or to a programming languageSearching: for phone number of G. Samsa, whose number is 929-9338, or for the person whose number is 489-6569Are these searches different?If the phone book has 8 million numbers in it (why are there only 7.9 million phone numbers with area code 212?)How many queries to find phone number of G. Samsa?How many queries to find person with number 929-9338What about IP addresses?A Computer Science Tapestry1.7Search, Efficiency, ComplexityThink of a number between 1 and 1,000respond high, low, correct, how many guesses needed?Look up a word in a dictionaryFinding the page, the word, how many words do you look at?Looking up a phone number in the Manhattan, NY directoryHow many names are examined?How many times can 1,024 be cut in half?210 = 1,024, 220 = 1,048,576A Computer Science Tapestry1.8Sorting Experiment: why do we sort?Groups of four people are given a bag containing strips of paperon each piece of paper is an 8-15 letter English wordcreate a sorted list of all the words in the bagthere are 100 words in a bagWhat issues arise in developing an algorithm for this sort?  Can you write a description of an algorithm for others to follow?Do you need a 1-800 support line for your algorithm?Are you confident your algorithm works?A Computer Science Tapestry1.9Themes and Concepts of CSTheoryproperties of algorithms, how fast, how much memoryaverage case, worst case: sorting cards, words, examsprovable properties, in a mathematical sense Languageprogramming languages: C++, Java, C, Perl, Fortran, Lisp, Scheme, Visual BASIC, ...Assembly language, machine language,Natural language such as EnglishArchitectureMain memory, cache memory, disk, USB, SCSI, ...pipeline, multi-processorA Computer Science Tapestry1.10Theory, Language, ArchitectureWe can prove that in the worst case quicksort is bad doesn’t matter what machine it’s executed ondoesn’t matter what language it’s coded inunlikely in practice, but worst case always possibleSolutions? Develop an algorithm that works as fast as quicksort in the average case, but has good worst case performancequicksort invented in 1960introsort (for introspective sort) invented in 1996Sometimes live with worst case being badbad for sorting isn’t bad for other algorithms, needs to be quantified using notation studied as part of the theory of algorithmsA Computer Science Tapestry1.11Abstraction, Complexity, ModelsWhat is an integer?In mathematics we can define integers easily, infinite set of numbers and operations on the numbers (e.g.,+, -, *, /) {…-3, -2, -1, 0, 1, 2, 3, …}In programming, finite memory of computer imposes a limit on the magnitude of integers.•Possible to program with effectively infinite integers (as large as computation and memory permit) at the expense of efficiency•At some point addition is implemented with hardware, but that’s not a concern to those writing software (or is it?)•C++ doesn’t require specific size for integers, Java doesFloating-point numbers have an IEEE standard, required because it’s more expensive to do arithmetic with 3.14159 than with 2A Computer Science Tapestry1.12Alan Turing (1912--1954)Instrumental in breaking codes during WW IIDeveloped mathematical model of a computer called a Turing Machine (before computers)solves same problems as a Pentium III (more slowly)Church-Turing thesisAll “computers” can solve the same problemsShowed there are