A Computer Science Tapestry1.1Wake up with CPS 006Program Design and Methodology IJeff Forbeshttp://www.cs.duke.edu/courses/cps006/currenthttp://www.cs.duke.edu/csed/tapestryA Computer Science Tapestry1.2Computer Science and Programmingz 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 fieldsz 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 1965z 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 Sciencez Artificial Intelligence thinking machinesz Scientific Computing weather, cars, heart, modellingz Theoretical CS analyze algorithms, modelsz Computational Geometry theory of animation, 3-D modelsz Architecture hardware-software interfacez Software Engineering engineering, sciencez Operating Systems the soul of the machinez Graphics from Windows to Hollywoodz Many other subdisciplinesA Computer Science Tapestry1.5Storiesz Who is Shawn Fanning and what did he do (19 years old)?z Who is Marc Andreessen and what did he do (21 years old)?z Who is Claude Shannon and what did he do (21 years old)?z Who is Linus Torvalds and what did he do (21 years old)?z Who is Dmitry Sklyarov and what did he do (26 years old)?z Who is Tim Berners-Lee and what did he do (35 years old)?z Who is Owen Astrachan and what did he do (44 years old)?A Computer Science Tapestry1.6Algorithms as Cornerstone of CSz 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 languagez 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?z 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, Complexityz Think of a number between 1 and 1,000¾ respond high, low, correct, how many guesses needed?z Look up a word in a dictionary¾ Finding the page/word, how many words do you look at?z Looking up a phone number in the Manhattan, NY directory¾ How many names are examined?z 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?z 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 bagz What issues arise in developing an algorithm for this sort?¾¾zCan 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 CSz Theory¾ properties of algorithms, how fast, how much memory¾ average case, worst case: sorting cards, words, exams¾ provable properties, in a mathematical sense z Language¾ programming languages: C++, Java, C, Perl, Fortran, Lisp, Scheme, Visual BASIC,more?¾ Assembly language, machine language,¾ Natural language such as Englishz Architecture¾ Main memory, cache memory, disk, USB, SCSI, ...¾ pipeline, multi-processorA Computer Science Tapestry1.10Theory, Language, Architecturez 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 possiblez 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 1996z 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, Modelsz 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 doesz 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)z Instrumental in breaking codes during WW IIz Developed mathematical model of a computer called a Turing Machine (before computers)¾ solves same problems as a Pentium III (more slowly)z Church-Turing thesis¾ All “computers” can solve the same problemsz Showed there are problems that cannot be solved by a computerz Both a hero and a scientist/ mathematician, but lived in an era hard for gay peopleA Computer Science Tapestry1.13Complexity: What’s hard, what’s easy?z What is a prime number?¾ 2, 3, 5, 7, 11, 13, …¾ Largest prime?z 48112959837082048697z 671998030559713968361666935769zHow do we determine if these numbers are prime?¾ Test 3, 5, 7, …¾ If we can test one million numbers a second, how long to check a 100 digit #?z Why do we care?z 671998030559713968361666935767 is