### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Introduction to Computing Explorations in Language, Logic, and Machines CS 1120

UVA

GPA 3.71

### View Full Document

## 19

## 0

## Popular in Course

## Popular in ComputerScienence

This 61 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 1120 at University of Virginia taught by Westley Weimer in Fall. Since its upload, it has received 19 views. For similar materials see /class/209664/cs-1120-university-of-virginia in ComputerScienence at University of Virginia.

## Popular in ComputerScienence

## Reviews for Introduction to Computing Explorations in Language, Logic, and Machines

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15

Glue Photons PNP DNA Helix Photomosaic from cover of Nature 15 Feb 2001 made by Eric Lander Lambda Calculus is a Universal Computer IZIZIZIZIZIZIZIZIZIZIZIZIZIZIZIZIZIZIZIZI ReadNVrite Infinite Tape Mutable Lists Finite State Machine ers Processing Way to make decisions if Way to keep going Meaning of Numbers 42ness is something who s successor is 43ness 42ness is something who s predecessor is 41 ness Zero is special It has a successor oneness but no predecessor OneSlide Summary The lambda calculus is a universal fundamental model of computation You can view it as the essence of Schemequot It contains terms and rules describing variables function abstraction and function application It is possible to encode programming concepts such as true false if numbers lists etc in the lambda calculus Lambda calculus can simulate Turing machines Quantum computers and nondeterminsitic Turing machines can try many options at once They are not more powerful than normal Turing machines The Complexity Class F contains tractable problems that can be solved in polynomial time The Complexity Class NP contains problems for which solutions can be verified in polynomial time Does P NP We don39t know 51 million if you know What is 42 fortytwo XLII cuarenta y dos Meaning of Numbers pred succ N gt N succ pred N gt N succ pred succ N gt succ N zero zero gt T zero succ zero gt F Is this enough Can we define add with pred succ zero and zero add E Myif zero xy add pred x succ y Numbers are Lists zero 2 null pred E cdr succEkx cons Fx IThe length of the list corresponds to the number value Making Pairs define makepair x y lambda selector if selector x y define carofpair p p t define cdrofpair p p f A pair is just an if statement that chooses between the car then and the cdr else Can we define lambda terms that behave like zero zero pred and succ Hint what if we had cons car and cdr Liberal Arts Trivia Religious Studies In Sunni Islam the Five Pillars of Islam are five duties incumbent on Muslims They include the Profession of Faith Formal Prayers and Giving Alms Name the remaining two pillars 10 cons and car cons E Xx y zzxy Example cons M N Mlylzzxy M N gt XylzzMy N gt lzzMN carzkppT szy39x Example car cons M N 2 car MZMN E kpp T MZMN gt I MZMN T gt I TMN gt My x MN gt I y MN gt M 12 Cdr tOO Null and null cons E Myzzxy carEApp T nullEMT 7 E Cdr E App F null Mx Ky z F Example Example Cdr C0 5 M N null null gt M x Ky z F M T cdr MJMN hpp F MJMN gt B TbyMIF gt B KZJMN F gt BT gt B FMN gt B N m m Null and null Counting null EMT 0 Enuu nuquot E 1 E cons F 0 2 E cons F 1 Example39 3 E cons F 2 null cons M N gt Mx ky z F MzMN gt B M39Z Mkay39M39 F succ E Mc0ns F x gt BOW39M39 F MN pred E Mcdr x gt B F 42 xy My y MyMny My y MyMzxy My y MyMzxy My y MyMzxy My y My Lambda Calculus IS a Un1versal Computer zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y My ZIZIZIZIZIZIZIZIZIZIZIZIZIZIZIZIZ IZIZIZI zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y My zz xy My y I I I My zzxy My y My zzxy My y My zzxy My y My Tape 7 MM MM MM quot L223 Ky 96223 y 352 y 52 III El Finite State Machine y y y 22 xy y y y zzxy y y y zzxy y y Fnlle Stale Machlne Numbers to keep track of State My zzxy My y My zzxy My y My zzxy My y My processing 7 2zxy My y My zz xy My y My zz xy My y My zz xy Way of making decisions if My y My zzxy My y My zz xy My y My7ZZ xy way to keep QCan MyyMT Equivalent Computers l term variable l erm term i term l A variable term can simulate AyMs 7w M y E v where v does not occur inM MNgt BMx N Lambda Calculus can simulate Turing Machine Universal Computer Lambda Calculus can simulate a Turing Machine Everything a Turing Machine can compute Lambda Calculus can compute also Turing Machine can simulate Lambda Calculus we didn t prove this Everything Lambda Calculus can compute a Turing Machine can compute also ChurchTuring Thesis this is true for any other mechanical computer also Quantum Physics for Dummies Light behaves like both a wave and a particle at the same time o A single photon is in many states at once Can t observe its state without forcing it into one state Schrodinger s Cat Put a live cat in a box with cyanide vial that opens depending on quantum state Cat is both dead and alive at the same time until you open the box Mm ws 309 Server Semiquot L y 23 Liberal Arts Trivia Biology Chemistry While rendered fat obtained form pigs is known as lard rendered beef or mutton fat is known as this It is used to make animal feed and soap Historically it was used to make candles it provided a cheaper alternative to wax Before switching to vegetable oil in 1990 McDonald39s cooked fries in 93 this and 7 cottonseed oil 20 What about nonmechanical computers 22 Quantum Computing Feynman 1982 Quantum particles are in all possible states Can try lots of possible computations at once with the same particles In theory can test all possible factorizationskeyspathsetc and get the right one In practice very hard to keep states entangled once disturbed must be in just one possible state 24 Qubit Regular bit either a 0 or a Quantum bit 0 1 or in between p probability it is a 1 A single qubit is in 2 possible states at once If you have 7 bits you can represent any one of 27 different states If you have 7 qubits you have 27 different states at once Nondeterministic Computing 1 11 WP 1 Write 1 In39PUt 1 Start MOVe a Write 1 Move a Input There can be multiple transitions on the same input NTM takes all of them at once Each gets its own independent copy of the tape If any path finds halting state that Quantum Computers Today Several quantum algorithms Shor s algorithm factoring using a quantum computer Actual quantum computers 5qubit computer built by IBM 2001 Implemented Shor s algorithm to factor World s most complex quantum computation 15 5 3 DWave 16qubit quantum computer 2007 Solves Sudoku puzzles To exceed practical normal computing need gt 50 qubits Adding another qubit is more than twice as hard 26 Two Ways of Thinking about Nondeterminstic Computing Omniscient allknowing machine always guesses right the right guess is the one that eventually leads to a halting state Omnipotent allpowerful machine can split in two every step all resulting machines execute on each step if one of the machines halts its tape is the output is the result 33521 Computability Liberal Arts Trivia Geography Is a nondeterministic TM more powerful than a deterministic TM This secondlongest river in the United States flows form Lake Itasca in Minnesota to the Gulf of Mexico Forty percent of North America39s ducks geese swan and wading bird species use it as a migration corridor It serves as the shared border for ten states contains over 29 locks and dams and generates more than a billion dollars a year in revenue from recreational uses including over 600 water oriented sites Computability Is a nondeterministic TM more powerful than a deterministic TM No We can simulate a nondeterminstic TM with a regular TM B1 Speed Is a nondeterministic TM faster than a deterministic TM B2 Speed Is a nondeterministic TM faster than a deterministic TM Unknown This is the most famous open problem in CS B3 Pegboard Problem Pegboard Problem Input a configuration of n pegs on a cracker barrel style pegboard Output if there is a sequence of jumps that leaves a single peg output that sequence of jumps Otherwise output false How hard is the Pegboard Problem B5 Problems and Procedures To know a O f bound for a problem we need to find a f procedure that solves it The sorting problem is O n log 11 since we know a procedure that solves it in n log n 0 To know a 20 bound for a problem we need to prove that there is no procedure faster than that solves it We proved sorting is 2n log n by reasoning about the number of decisions needed How much work is the Pegboard Problem Upper bound 0 0 11 Try all possible permutations Lower bound 2 Q 11 Must at least look at every peg Tight bound 8 What do you think 57 How much work is the Pegboard Problem Upper bound 0 0n Try all possible permutations Lower bound 2 907 Must at least look at every peg Tight bound 8 No one knows Complexity Class P Tractable Class F problems that can be solved in a polynomial 0nk for some constant k number of steps by a deterministic TM Easy problems like sorting making a photomosaic using duplicate tiles and simulating the universe are all in P 59 Liberal Arts Trivia Astronomy This space telescope was launched into orbit by the Space Shuttle Discovery in 1990 After having its incorrectlyground main mirror replaced in 1993 it has helped to make breakthroughs in astrophysics Notable are its Ultra Deep Field image which details the universe39s most distant objects and its help in determining the ultimate expansion of the universe the eponymous constant 40 Complexity Class NP Class NP Problems that can be solved in a polynomial number of steps by a nondeterministic TM Omnipotent If we could try all possible solutions at once we could identify the solution in polynomial time Omniscient If we had a magic guesscorrectly procedure that makes every decision correctly we could devise a procedure that solves the problem in polynomial time 41 NP Problems Can be solved by just trying all possible answers until we find one that is right Easy to quickly check if an answer is right Checking an answer is in P o The pegboard problem is in NP We can easily try n different answers We can check if a guess is correct in On check all n jumps are legal 42 Is the Pegboard Problem in P Orders of Growth simulating 7 7mng n i No one knows We can t find a O nk solution g 39 quot We also can t prove one doesn t WE pegboard puzzle n 2 2 lt n eXISt 2 27 r if quicksort 43 44 pegboard Pegboard puzzIe iDDDDDD 7 DEquot quot puzzle Emu 7 7mng n Bunnnn 7 5DDDD 7 g 2 Bnnnnn 7 intractable ADDDD 7 nlngn r riquot2 m manna 7 Q 7x7 3 o 2A annnn 7 g tractable 39E zannnn 7 m 7 ma 2 3 E E U39 HE simulatinguniverse 3 mil 12131415 iBi7iEiBZD W I do nothing that a man of unlimited funds superb physical I I endurance and maximum scienti c knowledge could not do 39 39 insertsort Batman may be ableto solve intractable problems but 12345678910111213141516 qu39d soquot computer solentlsts can only solve tractable ones for large n 45 46 loglogscale time n V since o If the fastest procedure to solve a B Bang problem is 92quot or worse Moore s Law doesn t help much P 2022 Every doubling in computing power my J n2 increases the solvable problem size W 1 nlogn 1 1 W 39 47 48 Complexity Classes Class P problems that can be solved in polynomial time by deterministic TM Easy problems like simulating the universe are all in P Class NP problems that can be solved in polynomial time by a nondeterministic TM Includes all problems in P and some problems possibly outside P like the Pegboard puzzle 49 Problem Classes if P 2 NP Simulating Universe 0n3 Find Best n How many problems are in the n class in n e How many problems are in P but not in the n class in nite How many problems swung Emir NP but not n log n Pegboard in nite 0n and Qn 51 PNP ls P different from NP is there a problem in NP that is not also in P If there is one there are infinitely many Is the hardest problem in NP also in P If it is then every problem in NP is also in P The most famous unsolved problem in computer science and math Listed first on Millennium Prize Problems 1M an automatic A in this course 0 and probably all CS courses at UVA 53 Liberal Arts Trivia Psychology This Swiss philosopher and natural scientist is known as the great pioneer of the constructivist theory of knowing His four stages of development include infancy preschool childhood and adolesence Each stage corresponds to the child39s understanding of reality eg conservation abstract reasoning during that period 50 Problem Classes if P NP Simulating Universe 0n3 Find Best n How many problems em are in the n class in nite How many problems are in P but not in the n class in nite How many problems 50mg iii NP butnot 80 10g n Pegboard o 9 M 52 NPComplete NPComplete is the class of problems that are the hardest problems in NP Cook and Levin proved that 3SAT was NP Complete 1971 If 3SAT can be transformed into a different problem in polynomial time than that problem must also be NPcomplete Pegboard ltgt 3SAT Either all NPcomplete problems are tractable in P or none of them are 54 NPComplete Problems Easy way to solve by trying all possible guesses If given the yes answer quick in P way to check if it is right If given the no answer no quick way to check if it is right No solution can t tell there isn t one No way can t tell there isn t one This part is hard to prove requires showing you could use a solution to the problem to solve a known NPComplete problem Human Genome Race Francis Collins Director of Graig Venter President of Celera Genomics UVa CLAS 1970 San Mateo College Yale PhD Almost courtmartialed Tenured Professor at U Denied tenure at SUNY Michigan Buffalo Gene Reading Machines One read about 700 base pairs Butdon t know where they are on the chromosome Read TACCCGTGATCCA ReadZ TCCAGAATAA Read 1 ACCAGAATACC I 55 57 I AGGCATACCAGAATACCCGTGATCCAGAATAAGC Most Important ScienceTechnology Races 1930405Decryption Winner British Reason Bletchley Park had computers and Alan Turing Nazi s didn t 19405 Atomic Bomb Winner US Reason Heisenberg miscalculated US had better physicists computers resources 19605 Moon Landing Soviet Union vs US Winner US Reason Many better computing was a big one Nazis vs British Nazis vs US Actual Genome 59 56 ding the Genome 58 Liberal Arts Trivia Greek Myths The Sphinx is said to have guarded the entrance to the city of Thebes and to have asked a riddle of wouldbe travelers The Sphinx originally from Ethiopia is said to have been sent by Hera or Ares Oedipus solved her riddle and is thus seen as a threshold figure helping to transition between the old religious practices and the new Olympian gods State the Riddle of the Sphinx and its answer 60 Common Superstring Input A set of n substrings and a maximum length k Output A string that contains all the substrings with total length S k or no if no such string exists IACCAGAATACCI TCCAGAATAA Egt TACCCGTGATCCA 1126 ACCAGAATACC T CCAGAATAA TACCCGTGATCCA ACCAGAATACCCGTGATCCAGAATAA 61 Common Superstring In NP Easy to verify a yes solution just check the letters match up and count the superstring length In NPComplete Similar to Pegboard Puzzle Could transform Common Superstring problem instance into Pegboard Puzzle instance 63 Give up No way to solve m2 15 an NPComl H problem best 395 known solutions being 02quot for n z 20 Million 65 Common Superstring Input A set of n substrings and a maximum length k Output A string that contains all the substrings with total length S k or no if no such string exists IACCAGAATACCI ITCCAGAATAAI Egt TACCCGTGATCCA 1125 Not possible 62 Human Genome 3 Billion base pairs 600700 bases per read 8X coverage required gt 8 3000000000 650 36923076 1213 So n z 37 Million sequence fragments Celera used 272 Million reads but could get more than 700 bases per read 64 Approaches Human Genome Project Collins Change problem Start by producing a genome map using biology chemistry etc to have a framework for knowing where the fragments should go Celera Solution Venter Approximate we can t guarantee finding the shortest possible but we can develop clever algorithms that get close most of the time in On log n 66 Sex Religion Politics Obinib L cbist Clyurcl l i OneSlide Summary The substitution model for evaluating Scheme does not allow us to reason about mutation In the environment model A name is a place for storing a value define cons and function application create places set changes the value in a place Places live in frames An environment is a frame and a pointer to a parent frame The global environment has no parent To evaluate a name walk up the frames until you find a definition A golden age is a period when knowledge or quality increases rapidly 2 Outline Golden Ages Names and Places Environment Model Interested in random weekly emails about available CS 150 tutoring Send email to the course staff or me to get on that list The Real Golden Rule Why do fields like astrophysics medicine biology and computer science have endless golden ages but fields like rock n roll 19621973 or whatever was popular when you were 16 music 17751825 philosophy 4OOBC3SOBC art 18751925 soccer 19501966 baseball 19251950 movies 19201940 have short golden ages Think about it over the break Ymma THE B Iowa Golden Ages or Golden Catastrophes Malthusian Catastrophe Reverend Thomas Robert Malthus Essay on the Principle of Population 1798 The great and unlocked for discoveries that have taken place of late years in natural philosophy the increasing diffusion of general knowledge from the extension of the art of printing the ardent and unshackled spirit of inquiry that prevails throughout the lettered and even unlettered world have all concurred to lead many able men into the opinion that we were touching on a period big with the most important changes changes that would in some measure be decisive of the future fate of mankind Malthus Postulates I think I may fairly make two postulata First that food is necessary to the existence of man Secondly that the passion between the sexes is necessary and will remain nearly in its present state These two laws ever since we have had any knowledge of mankind appear to have been fixed laws of our nature and as we have not hitherto seen any alteration in them we have no right to conclude that they will ever cease to be what they now are Malthus Conclusion Assuming then my postulata as granted I say that the power of population is indefinitely greater than the power in the earth to produce subsistence for man Population when unchecked increases in a geometrical ratio Subsistence increases only in an arithmetical ratio A slight acquaintance with numbers will show the immensity ofthe first power in comparison of the secondquot Malthusian Catastrophe o Population growth is geometric 8kquot kgt 1 o Food supply growth is linear n What does this mean as n gt co Food per person food supply population n e kquot As n approaches infinity food per person approaches zero Liberal Arts Trivia American Studies This American social activist and leading figure of the woman39s movement crafted the Declaration of Sentiments ts presentation at the first women39s rights convention in Seneca Falls is often credited with initiating the first woman39s suffrage movement in the USA Beyond voting rights her work addressed parental and custody rights employment and income rights property rights divorce laws and birth control Liberal Arts Trivia Classics and Drama o This ancient Greek tragedian playwright wrote Ajax Antigone Trachinian Women Oedipus the King Electra Philoctetes and Oedipus at Colonus He influenced the development of the drama by adding a third actor reducing the importance of the chorus in the presentation of the plot and putting a greater emphasis on character development lthus Fallac Malthus Fallacy He forgot how he started The great and unlooked for discoveries that have taken place of a rs in natural hi so h me increasin diffusion of general knovlalelg e from the aft sic of Increasing knowledge of farmlng wea wer t 5 art of printing me ardent and forecasting plant domestication genetic unshac ed spirit ofinquiry mat prevails engineering pest repellants distribu on throughout the lettered and even unlettered e world Golden Age of Food Production Agriculture is an endless golden age field production from the same land increases as 8002quot hanne G rowi ng Corn Corn Yield g o I S 3 elkquot V 2 An 5te 5 e lane mono 2005 mm vl l 39 ll l Dnundsuerarre pounds peracre 3 ll u l Mlchael Pollan s Upcoming Malthusian Exam le Norman Borlau p g Catastrophes Famer of me Green Revolution nwnrmwmnmn Nob Peace Prize Presidential Medal of Freedom 39 Human W ongressional Gold Medal one of five to win all con ump on 0 5 three India39sPadma Vibhushan fossll fuels grows m Man e hennoom ayw werehavvvngavmndSayingwemnewaswlngto as 805 fairly w Stan2 Norman we womrlg He mweo m Mexico and lived among the people quotquot mereuntllheflguredouthowmlmpmve meoutnu mefamler omat large k uke Log demnmnne mennemoonemnyemmm noewneen s avwlthP l magmmln m uoeneww eatstvalnsmat Amiable fuel 5 manned men om mu a mm mm mnan m e man he new 2 mm elnlnewmnewmncnne neeaalnemeeme constant 7 W W l on nlneem m lineageeenw one 2 n n new man y lohehaosaveoaollllonveovle We nnmw mm mm moon on 5 en no mm men we a We lee m Nan my we upmseslyevmmm l Penn Jillette on the show Penn amp Teller Malthus was wrong about 2 Also Nuances in same can mm medicine quotwhy i expemnw mm and swam and paiiiai chanves ea Nvuiman in ma rm reduced m isk i in nuquot quotW i Cornucopian View Few Femurce are reaiiy nite An Scienti c Lning eem tn have endiem guideri age We hupe Human ingenuity and ecunumic arid DEIUUC Win aive prubiem befure niey pecarne caiama he rNu Brie Win 52 the iasi gaiiuri ar gas fur2 35 Kayquotsian View The best way to predict the future is to invent it Alan Kay Liberal Arts Trivia French Literature Tni 19 quotcenmry Frencn writer and puiiticai acLiViLwa an expunent ufthe Rprnanuc muvement in France Twu uf ni Vuiume a de i cze are par 5 acciairned arid nei a d in Charge When picking rnaiaix pick a na age eld that i abuut tn erit ri guideri age rThiS requires Visi i i and luck May it afe by picking an endiex guideri age rieid c i a gaad cnaice fur mini ii guiden L hurt iLiberal Arts Trivi Mathematics iii a areao He e greatet Frencn Duet omide air France ne i erhap Den knawn fumes Miserable arid OUP39DGWP N de Paris Buriu Dumb Give Vaijeari primrier number Review Names Places Mutation A name is a place for storing a value A define creates a new place A cons application creates two new places the car and the cdr A frame is a collection of places An environment is a frame and a pointer to a parent environment The global environment has no parent set name expr changes the value in the place name to the value of expr Environments I ltprimitivegt I I null ltprimitivenullgt I global environment The global environment points to the outermost frame It starts with all Scheme primitives gt define x 3 gt 26 Environments amp Procedures I ltprimitivegt I null ltprimitivenullgt I global I environment The global environment points to the outermost frame It starts with all Scheme primitives gt define double lambda x x x gt How To Draw Procedures A procedure needs both code and an environment Think of makeincrementer where are x and y 0 define makeincrementer x lambda y x y We draw pictures like this Environment Ointer environment parameters y body x y Procedures enVifOHmem null ltpnmitivenullgt environment parameters x body x x gt define double lambda x x x Application Old rule Substitution model Apply Rule 2 Constructed Procedures To apply a constructed procedure evaluate the body of the procedure with each formal parameter replaced by the corresponding actual argument expression value x Vin w x Programming 744994 wit 74 State amp Golden Ages Iquot A W OneSlide Summary The substitution model for evaluating Scheme does not allow us to reason about mutation In t environment model A name is a place for storing a value define Cons and function application create places set changes the value 39n a lace Places live in frames An environment is a frame and a 39 te a parent frame The global environment has no parent To evaluate a name walk up me frames until you find a definition A galden age is a period when knowledge or quality increases rapidly Outline Names and Places set and friends Environment Model Golden Ages Interested in random weekly emails about available CS 150 tutoring Send email to the 0 staff or me to get on that list There will not be normally scheduled lab hours or break office hours over spn ng Your Exam 1 grade will be visible on the Automatic Adjudication website Names and Places o A name is not just a value it is a place for storing a value o define creates a new place associates a name with that place and stores a value in that place define X 3 me Lecture 3 Evaluation Rule 2 Names If the expression is a name it evaluates to the value associated with name gt define two 2 gt two that Bang set set bang changes the value associated with a place gt define x 3 gt x 3 gt set x 7 gt x 7 set should make you nervous gt definex 2 gt nextx 3 Before set all procedures gt nextx were pure functions except 4 for some with sideeffects gt X The value of f was the 4 same every time you evaluated it Now it might be different Evaluation Rules gt define x 3 gt nextx x 7 or 8 gt x nextx 9 Defining nextx define nextx set x x 1 X define nextx lambda 0 begin set x X 1 X syntactic sugar for Evaluation Rules gt define x 3 gt nextx x 7 or gt x nextx DrScheme evaluates application subexpressions left to right but Scheme evaluation rules allow any or10 or10 order setcar and setcdr g 39ne pa cons 1 2 1 2 setcar p v Replaces the car of the cons p with v setcdr p v Replaces the cdr of the cons p with VThese should scare you even more then set E3 12 gt define pair cons 1 2 gt define pair cons 1 2 gt pair gt pair 12 12 gt setcar pair 0 a gt SEtCar Pair 0 pair gt car pair gt car pair gt cdr pair gt cdr pair 2 2 gt setcdr pair 1 gt pair 01 I I definemapproclst Functional vs Imperative p 39fEQEHZLE JOZUJLarIa Solution map proc cdr Ist Functional Solution A procedure that takes a procedure of one argument and a A procedure that takes a procedure and list as l t d t l t f th lt arguments and replaces each element in the list 15 an re ums a 15 o e new 5 with the value of the procedure applied to that produced by applying the procedure to element each element in the list de ne map fist de ne map proc Ist if null Ist void ifnu Ist null begin cons proc car Ist setcar Ist f car st map proc cdr st map f cdr Ist Programming with Mutation gt map square intsto 4 Mutation Changes Everything gt define i4 intsto 4 13 gt inap square i4 g We can no longer talk about the value of gt 5 an expressmn 1 4 9 16 g The value of a give expression can change We need to talk about the value of an gt define i4 intsto 4 expression in an execution environment gt map square l4 execution environment context so far 14 9 16 The order in which expressions are evaluated now matters euoi10un2 gt4 1234 Why Substitution Fails gt define nextx set x x 1 x gt define x O gt lambda x x x nextx 2 Substitution model for evaluation would predict nextx nextx begin set x x 1 X begin set x x1x begin set 0 0 1 0 begin set 0 0 1 0 0 0 0 Liberal Arts Trivia Rhetoric o This type of values debate traditionally places a heavy emphasis on logic ethical values and philosophy It is a oneonone debate practiced in National Forensic League competitions The format was named for the series of seven debates in 1858 for the Illinois seat in the United State Senate Names and Places A name is a place for storing a value define creates a new place cons creates two new places the car and the cdr set name expr changes the value in the place name to the value of expr setcar pair expr changes the value in the car place of pair to the value of expr 23 Liberal Arts Trivia Astrophysics According to this 1915 theory be specific the observed gravitational attraction between masses results from the warping of space and time by those masses This theory helps to explain observed phenomena such as anomalies in the orbit of Mercury that are not predicted by Newton39s Laws and can deal with accelerated reference frames It is part of the framework of the standard Big Bang model of Cosmology Very Scary The old WHERE THE WILD THINGS llRElllT substitution r model does not explain Scheme programs that contain mutation We need a new environment model Lambda and Places lambda x also creates a new place named x The passed argument is put in that place How are these places different gt define x 3 gt lambda x x 4 4 gtX 24 Location Location Location Places live in frames An environment is a frame and a pointer to a parent environment All environments except the global environment have exactly one parent environment global environment has no parent Application creates a new environment Environments I ltprimitivegt I null ltprimitivenullgt I global environment The global environment points to the outermost frame It starts with all Scheme primitives gt define x 3 gt Procedures global environment null ltprimitivenullgt double 7 gt define x 3 gt define double lambda x x X gt Environments ltprimitivegt null ltprimitivenugt global environment The global environment points to the outermost frame It starts with all Scheme primitives 26 Evaluation Rule 2 Names A name expression evaluates to the value associated with that name To find the value associated with a name look for the name in the frame associated with the evaluation environment If it contains a place with that name the value of the name expression is the value in that place If it doesn t the value of the name expression is the value of the name expression evaluated in the parent environment if the current environment has a parent Otherwise the name expression evaluates to an error the name is not defined 28 How to Draw a Procedure A procedure needs both code and an environment We ll see why soon We draw procedures like this Environment pointer environment parameters x body x x How to Draw a Procedure for artists only Environment pointer m Procedures global environment ltprimitivegt null ltprimitivenullgt each parameter and operand values Evaluate the body in the new environment environment parameters x body x x gt double 4 8 B5 X X Input parameters in mOuth Procedure Body gt environment define double parameters X lambda x X x body xx B1 B2 Application New Application Rule 2 ld l b d l 1 Construct a new environment whose 39 O ru e39 5 St tuuon m0 e parent is the environment to which the environment pointer of the applied Apply Rule 2 Constructed Procedures procedure points To ipply a ConStrUCted procedure 2 Create places in that frame for each eva uate the body of the procedure With parameter containing the value of the each formal parameter replaced by the corresponding operand expression corresponding actual argument expreSSion value 3 Evaluate the body in the new 39 environment Result is the value of the application B3 34 Construct a new I Ei imem 1 Construct a new I f1 azimh enVironment parent is enVironment parent is procedure s environment procedure s environment pOinter pOinter Make places in that 2 Make places in that frame with the names of X 39 3 frame with the names of each parameter and operand values 3 Evaluate the body in the new environment gt define x 999 1 Construct a new environment parent is procedure s environment pointer 2 Make places in that frame with the names of each parameter and operand values 3 Evaluate the body in the obal wiroriment 1 environment o l parameters x 1 Construct a new environment parent is procedure s environment pointer 2 Make places in that frame with the names of each parameter and operand values 3 Evaluate the body in the global v omn 1 environment o l parameters x new environment body lambda y new environment body lambda y X y X y gt define x 999 gt define x 999 gt define adder x gt define adder x lambda Y X Y lambda Y X Y gt define addtwo adder 2 157 38 1 Construct a new El imem 1 Construct a new f1 azimh environment parent is procedure s environment pointer 2 Make places in that frame with the names of each parameter and operand values 3 Evaluate the body in the new environment gt define x 999 gt define adder x lambda Y X Y gt define addtwo adder 2 l environment o l parameters x body lambda y MID environment parameters y body x y 59 environment parent is procedure s environment pointer 2 Make places in that frame with the names of each parameter and operand values 3 Evaluate the body in the new environment gt define x 999 gt define adder x lambda Y X Y gt define addtwo adder 2 1 environment o l parameters x body lambda y X y environment parameters y body x y 40 1 Construct a new global MromnaN environment parent is procedure s environment pointer 2 Make places in that frame with the names of each parameter and operand values 3 Evaluate the body in the new environment gt define x 999 1 environment o l parameters x body lambda y X 31 gt define adder x lambda Y X Y gt define addtwo adder 2 e nvironment parameters y gt addtwo 6 body x y 1 Construct a new global vironmh environment parent is procedure s environment pointer 2 Make places in that frame with the names of each parameter and operand values 3 Evaluate the body in the new environment gt addtwo 6 8 gt define x 999 1 environment o l parameters x body lambda y X y gt define adder x lambda Y X Y gt define addtwo adder 2 environment parameters y body x y Liberal Arts Trivia Statistics o In probability theory and statistics this indicates the strength and direction of a linear relationship between two random variables A number of different coefficients are in different situations the best known of which is the Pearson productmoment coefficient Notably this concept does not imply causation Liberal Arts Trivia Music o This baroque keyboard instrument is the spiritual predecessor of the pianoforte It produces a sound by plucking a string when each key is pressed but unlike the piano it lacks responsiveness to keyboard touch and thus fails to produce notes at different dynamic levels Jan Vermeer rain Science39s Endless Golden Age D k A l39 H M B i C K H D l i Astrophysics lfyou re goin tou g 2 your computer to si ulate enon in the OIdScientist THE WORLD IS FLAT indisputable evidence inside creases your volume by a factor of 1000quot astrophysics simulation in e notation ISTHE MOON MADE IF EHEESE Sciunlixu m m Astrophysics If you re going to use your computer to simulate some phenomenon in the universe then it only becomes interesting if you change the scale of that phenomenon by at least a factor of 10 For a 3D simulation an increase by a factor of 10 in each of the three dimensions increases your volume by a factor of 1000 How much work is astrophysics simulation in 8 quotOtatloni When we doubietne size oflhe 8 simulation the work oclupiesi 11 Just like oceanograpny octopi simulations L V Orders of Growth 3 Simulating universe irrsertsurt n findrbesl Orders of Growth 1400000 1200000 sirnulating 1000000 800000 600000 400000 200000 49 Astrophysics and Moore s Law Simulating universe is n3 Moore s law computin power doubles every 18 mont s Dr Tyson to understand something new about the universe need to scale by 10x How long does it take to know twice as much about the universe 50 Knowledge of the Universe Knowledge of the Universe I de ne computingpower nyears doubling every 18 months 1587 every 12 months ggzzsrse ly 39 gaggi h define computingpower nyears de ne simulationwork scale scale scale scale if z nyears 0 1 7 Simulation is O nquot3 Work 1587 computingpower nyears 1 013291 quotquot 9 l l l 3 de ne knowledgeof universe scale log10 scale 3 393939 knowledge of the universe is log 10 the scale of uniirerse We can simulate SlmUaflon 5 90 WOfk define findknowledgeofuniverse nyears deflne SlmUIatlonWork scale define findbiggest scale scale scale scale scale today can simulate size 10 universe 1000 work if gt simulationwork scale 1000 define log10 x log x log 10 log is base e computingpower nyears knowledge of the universe is logw the scale of universe scale 1 We can simulate findbiggest scale scale 1 deflne knOWIEdgeOfUmverse scale 390010 scale knowledgeofuniverse findbiggestscale 1 51 52 gt findknowledge of universe 0 10 The Endless Golden Age gt findknowledge of universe 1 1041392685158225 000 two things are gt findknowledge of universe 2 infinite the universe 11139433523068367 and human Golden Age period in which gt findknowledge of universe 5 knowledge quality of something doubles 1322219294733919 stupidity and Im uickl gt findknowledge of universe 10 not sure about the q y 15527578315815739 former At any point in history half of what is gt findknowledge of universe 15 20 Albert Einstein known about astrophy51cs was discovered gt findknowledge of universe 30 l 3005609445360 in the prev10us 15 years ggilnldgl ggw egaeggginiverse 60 Moore s law today but other advances gt ndknowledgeofuniverse 80 VWlthere beany mystery previously telescopes photocopiers clocks 6348717927935257 left in the Universe when agriculture etc you die 53 54 EndlessShort Golden Ages Endless golden age at any point in history the amount known is twice what was known 15 years ago Always exponential growth kquot k is some constant n is number of years Short golden age knowledge doubles during a short golden period but only improves linearly most of the time Usually linear growth n n is number of years 55 Computing Power 19692008 in Apollo Control Computer Units ED EIEIEI EIEIEIW Moore s Law computing power roughly doubles every 18 months I I 6 lt2 395 6 lt2 e e e equot e g e e e e w 6 6 56 Computing Power 19691990 in Apollo Control Computer Units veggies sagas 42 Nag g age a 57 g Goaldenage O 6 U I 55 o i 57 i 457 L 4 Changed goalkeeper g 357 passbackrule m 0 3e 8257 e 27 o 015 1 E HHHHHHHHHHHHHHHHNN a DkaDkDXDKDkaDkaDkaDkaDkaDOO gt WWWU39IU39IU39IC AC ANNNCXJCXJOOOOO 58 Endless Golden Age and Grade Inflation 0 Average student gets twice as smart and wellprepared every 15 years You had grade school teachers maybe even parents who went to college 0 If average GPA in 1977 is 200 what should it be today if grading standards didn t change 59 Grade Inflation or Deflation 200 average GPA in 1977 gentle C 2 better students 19771992 2 better students 19922007 149 population increase Virginia197651M Virginia 2006 76M 074 increase in enrollment Students 1976 10330 Students 2006 13900 Average GPA today should be 882 but our expectations should also increase 60 Micrust T e Internet SC OnaD Types amp k M Networkin n Outline Administration StaticCharme Typechecking Networking History Latency Bandwidth Switching The Internet Stru39ctu red Lab in Dynamic Web Sites Small Hall Today bring a laptop if W11 ha v Q Student Comments I am displeased with the course in general I was expecting a course that showed how computing concepts relate to the liberal arts While that is true to some extend this class feels more like a straight programming class DrScheme is not intuitive and makes this course much harder than 101 and 201 without really giving more information Managing expectations is the key to happiness OneSlide Summary A type is a possibly infinite set of values Each type supports a set of valid operations Types can be latent or manifest static or dynamic strong or weak We can change the Charme interpreter to support manifest program visible types A network is a group of three or more communicating entities Bandwidth is the throughput of a communication resource measured in bits per second Latency is the time delay between the moment when communication is initiated and the moment the first bit arrives measured in seconds In circuit switching a path through a network is reserved high qualityofservice used in telephones In k switching each packet is routed individually internet postal service 2 Administrivia Start P58 and PS9 Now PS9 Team Requests due Friday April 10 h 1 CS Department Fireside Chat TODAY Wednesday Apr 8 530pm MEC 205 Worth 2 points of Extra Credit on Exam 2 Kinga39s Web Fault Research Survey httpwwwcsvirginiaedukld5rwebfault Worth 2 points of Extra Credit on Exam 2 Plus possibly SSS 2009 Computing and Communication Scholarship for Undergraduate Women httpwwwcsvirginiaeduccscholarship 1000 merit scholarship due June 30 h More Student Comments I am displeased that the answer to question eight in this problem set require a lot of thinking and writing code for only one point of the assignment Irony The goal was to make it reasonable to not do all of the problem set I am displeased that I have to make a dynamic website which will take a lot of time and likely be our hardest assignment Yes the final project will be hard Even More Student Comments I am displeased that some people are opting not to do the problem sets I am not a computer science major and this is the first cs class I have ever taken but I still think it is important for everyone to branch out and learn new things Although some people may say that they will never use this stuff again you never know Currently zero students have opted out of the problem sets Changes Vote Ignore all reading quiz grades I will show my knowledge of the material elsewhere We will add answers to the textbook next year By hiring students Come talk to me and I will give you six free final project ideas You can drop the lowest PS grade CProcedureType class CProcedureTypeCType def initsef args rettype selfargs args selfrettype rettype def strsef return quotquot strsefargs quot gt quot strsefrettype quotquot def isProcedureTypeself return True def getReturnTypeself return selfrettype def getParametersself return selfargs def matchessef other return otherisProcedureTvpe0 coo mNNNUJAU39IU39IO Displeased N Course and problem sets are hardlongfrustrating Reading quizzes Two exams final too much work at end Switch languages learning on our own Book remains dry confusing and without answers Don39t know what to do for PS9 It still takes too long to get help in office hours Cannot drop lowest PS grade IDLE sucks Other CPrimitiveType class CPrimitiveTypeCType def initsef s selfname s sef return selfname def isPrimitiveTypeself return True def matchesself other return otherisPrimitiveTypeO and selfname othername class XY means X is a subclass of Y 10 CProcedureType class CProcedureTypeCType def initsef args rettype selfargs args selfrettype rettype def strsef return quotquot strsefargs quot gt quot strsefrettype quotquot def isProcedureTypeself return True def getReturnTypeself return selfrettype def getParametersself return selfargs def matchessef other return otherisProcedureType and selfgetParametersOmatchesothergetParametersO and selfgetReturnType0matchesothergetReturnTypeO 12 CProductType class CProductTypeCType def initself types seftypes types def strself def isProductTypeself return True def matchesself other CProductType class CProductTypeCType def initself types seftypes types clef strself def isProductTypeself return True def matchesself other if other isProductType st seftypes ot othertypes if enst enot fori in range0 enst if not stimatchesoti return False reached end of loop gt all matched return True return False Types of Types Latent anifest change grammar represent types Dynamically Checked Statically CheCked typecheck expressions before eval Liberal Arts Trivia Linguistics This Chinese language dialect Yuet Yu or Yue Yu is popular in Hong Kong Macau and southern mainland China It retains more tones and consonant endings from older varieties of Chinese that have been lost to other modern Chinese dialects Its rarelyused written form contains many characters not used in standard written Chinese See 2nd here 14 Liberal Arts Trivia Dance This closed position 3A time standard ballroom dance featuring gliding steps and rotations It became fashionable in Vienna in the 17805 and shocked many when it was first introduced unlike the popular folk dances of the time it was a couples dance that involved the leader clasping the follower about the waist This gave it a dubious moral status in the eyes of the gentry Bonus My uncle Walter goes 16 Adding Type Checking def evalLoop initializeGlobalEnvironment while True for expr in exprs typ typecheckexpr globalEnvironment if typ and typisError print quotType errorquot typgetMessageO else res mevalexpr globalEnvironment if res l None print strres 18 39 39 E 39 t Stat1C CheCk ng cai sgtopegcyfgr1value pair for each variable def typecheckexpr env if isPrimitiveexpr return typePrimitiveexpr elif isConditionalexpr return typeConditionalexpr env elif isLambdaexpr return typeLambdaexpr env elif isDefinitionexpr typeDefinitionexpr env elif isNameexpr return typeNameexpr env elif isApplioationexpr return typeApplicationexpr env else evalError quotUnknown expression quot strexpr def addVariableself name typ value selfframename typ value def lookupPlaceself name if selfframehaskeyname return selfframename elif selfparent return selfparentlookupPlacename else return None def lookupVariableTypeself name place selflookupPlacename if place return place0 else return CErrorTypequotName not foundquot def lookupVariableself name return selflookupPlacename1 Static Type Checking def typecheckexpr env if isPrimitiveexpr return typePrimitiveexpr daftypeNamdeXPrv env elif isConditionalexpr return envlooku pVariableTypeexpr return typeConditionaKexm env elif isLambdaexpr return typeLambdaexpr env elif isDefinitionexpr typeDefinitionexpr env elif isNamelexpr return typeNameexpr env elif isApplioationexpr return typeApplicationexpr env else evalError quotUnknown expression quot strexpr Typechecking Names def evalDefinitionexpr env name expr value mevalexpr4 env typ CTypefromParsedexpr3 envaddVariablename typ value 21 22 def typeDefinitionexpr env Stat C C heck n g assert isDefinitionexpr ifenexpr 5 def typecheckexpr env evalError quotBad de nition squot strexpr if isPrimitiveexpr name expr1 return typePrimitiveexpr if isinstancename str elif isConditionalexpr if expr2 l 3939 return typeConditionalexpr env evalError quotDefinition missing type squot strexpr Elif iSLambdaexpri typ CTypefromParsedexpr3 return typeLambdaexpr env etyp typecheckexpr4 env elif isDefinitionlexpr de ne square Number gt Number if not typmatohesetyp typeDefinitionexpr env evalErrorquotMistyped definition name typ etyp Elif i8Nameexpri elifisinstancemame list return typeNameexpr env evalError quotProcedure de nition syntax not implemented Elif iSAppllcatl0neXPri else evalError quotBad definition squot strexpr Tatum typeAppIicationexpr enV else evalError quotUnknown expression quot strexpr Example define x Number hello Example define y Number 2 3 23 24 class Procedure def initsef params typ body env selfparams params selfbody body selftyp typ selfenv env def getParamssef scigydp o return selfparams def getParamTypesself return selft def getBodyself return selfbody def getEnvironmentself return selfenv defstrsef return quotltProcedure s sgt strsefpararns strsefbody def evalLambdaexpr env assert isLambdaexpr if eriexpr 3 evalError quotBad lambda expression s strexpr params expr1 paramtypes paramnames assert eripararns 3 0 fori in range0 enparams3 name paramsi3 assert paramsi3 1 paramnamesappendname typ CTypefromParsedparamsi32 paramtypesappendtyp return Procedureparamnames paramtypes expr2 env lambda X Number 25 26 def typeLambdaexpr env 39 39 355mm da W Static Type Checki ng if Ienexpr 3 evalError quotBad lambda expression squot strexpr this is a bit tricky we need to quotpartiallyquot apply it def typecheckexpr env to nd the type of the body if isPrimitiveexpr newean EnVironmentenV return typePrimitiveexpr 12m gmegsp ld elif isConditionaexpr paramtypes 1 Study me return typeConditionaexpr env assert enparams 3 0 for Exam 239 ellf IsLambdaexpr ion In range0 lenparams3 return typeLambdaexpr env Eggilggglgii gm elif isDefinitionexpr typ CTypefromParsedparamsi32 uglisil Jaergglgleimgxpr env paramnamesappendmame 3 paramtypesappendtyp return typeNameexpr env newenvaddVanablename typ None ellf IsApplIcatIonexpr resum lpe WPeCheCWeXPrlzlv newenv return typeApplicationexpr env return CProcedureTypeCProductTypeparamtypes resulttype else evalError quotUnknown expression strexpr 28 Typechecking an Application def typeApplicationexpr env proctype typecheckexpr0 env if not proctypeisProoedureTypeO evalErrorquotApplication of nonprocedure quot strexpr0 optypes map lambda op typecheckop env expr1 optype CProductTypeoptypes if not optypematchesproctypegetParametersO evalErrorquotParameter type mismatch prootypegetParametersO optype return prootypegetReturnTypeO square Number gt Number Example 1 square 5 Example 2 square hello Static Type Checking def typecheckexpr env if isPrimitiveexpr return typePrimitiveexpr elif isConditionalexpr return typeConditionalexpr env elif isLambdaexpr39 return typeLambdaexpr env elif isDefinitionexpr typeDefinitionexpr env elif isNameexpr return typeNameexpr env elif isApplicationexpr return typeApplioationexpr env else evalError quotUnknown expression quot strexpr Typechecking Primitives def typePrimitiveexpr if isNumberexpr return CPrimitiveType39Number39 elif isinstanceexpr bool return CPrimitiveType39Boolean39 elif callableexpr return findPrimitiveProcedureTypeexpr e se 3555 False This is a kludgey procedure that looks through the global environment to find the matching procedure and returns its type B1 Static Type Checking def typecheckexpr env if isPrimitiveexpr return typePrimitieexpr elif isConditionalexpr return typeConditionalexpr env elif isLambdaexpr return typeLambdaexpr env elif isDefinitionexpr typeDefinitionexpr env elif isNameexpr return typeNameexpr env elif isApplicationexpr return typeApplicationexpr env else evalError quotUnknown expression quot strexpr Left as possible Exam 2 question 52 StaticCharme StaticCharmegt 1 t Error Parametertype mismatch expected Number Number given Number Boolean StaticCharmegt define squareNumber gt Number lambda xNumber x x StaticCharmegt square t Type error Parameter type mismatch expected Number given Boolean StaticCharmegt define badretNumber gt Number lambda x Number gt x 3 Error Mistyped definition badret declared type Number gt Number actual type Number gt Boolean 53 Who Invented the Internet Who Invented Networking 55 What is a Network A network is a group of three or more connected communicating entities Beacon Chain Networking Thus from some faraway beleaguered island where all daylong the men have walls the smoke goes up to heaven but no sooner has the sun gone down than the light from the line of beacons blazes up and shoots into the sky to warn the neighboring islanders and bring them to the rescue 39n thequot Sh39ps39 Iliad Homer 700 BC cnaln pr peaeun s slgnaled Agarnrnernrlorl s return 12nnac spread on Greek peaks over sunkrn Chappe s Semaphore Network l if Flrst LlrlE Parls m Lllle1794 Moblle sernapnore relegrapn Used ln the cnrnean war 185371856 Liberal Arts Trivia Mathematics The this of a function at a chosen input value describes the best linear approximation of the function near that input point If this can be applied to a function infinitely many times the function is called smooth The this is also given by the limit as the difference in in ut approaches zero of the ratio of the difference between the function values of two nearby inputs to the difference between those two nearby inputs Pony Express April 1860 October 1861 Missouri to California 10 days 1015 miles per horse 100 miles per rider 400 horses total 11 Pay 1 at a law Government and Network ng Chappe wanted a commercial network methodsthat mudlfy establlshed hablts lien hurts mus1 frurnthe older methods Few e n Those ln pDWEYWlll nu make nu enun u suppun w lrlvErlilurl unless ll ean helpth m u augmen helr puwen and even when they du suppun nJhelr elluns are usually lnsulllelennu alluwthenewldeastubefullyekplulted ClaudeChappe1EZA rmally e ne month m one yea n a lne urltlnntu lntlnn Francs French Law passed ln 1837 made prlvate netwprklng lllEgal Liberal Arts Trivia Religious Studies Among the truths said to have been realized by Siddhartha Gautama Buddha during his experience of enlightenment are these 1 The Nature of Suffering hint almost everything 2 Suffering39s Origin hint desire 3 Suffering39s Cessation hint freedom from craving 4 The Way Leading to the Cessation of Suffering hint Noble Eightfold Path What are these things collectively know as Measuring Networks Latency Time from sending a bit until it arrives seconds or seconds per geographic distance Ban dwi dth How much information can you transmit per time unit bits per second 43 Improving Latency Fewer transfer points Longer distances between transfer points Semaphores how far can you see clearly o Curvature of Earth is hard to overcome Use wires electrical telegraphs 1837 Faster transfers Replace humans with machines Faster travel between transfers Hard to beat speed of light semaphore network Electrons in copper about 13rd speed of light 45 if NATIONAL LAMBDARA About Mamhmmg 5mm suppnn FwRazumhays Anilialedijzcls Heseuvaanlei Ho N N NLH Services map quot m Fig Ocean Pa kElHEi e mus am new 5 mm 15339 mm we a new 47 Latency and Bandwidth Napoleon s Network Paris to Toulon 475 mi Latency 13 minutes 165 per mile What is the delay at each signaling station how many stations to reach destination At this rate it would take 1 hour to get a bit from California Bandwidth 2 symbols per minute 98 possible symbols so that is 13 bits per minute How fast can signalers make symbols t this rate it would take you about 9 days to get p58zip 44 How many transfer points between here and California 46 tracert K 39rraeert wwwcs berkeley ed Tracing route to hyperionesterkeleyedu 16922960105 over a maximum of 30 hops 7 3 rol t larwa e 54 1aver3 hous e at lar39l o 1 losarhous r B7 an an Atl a n m rureeva ueLneiey nuu sodarbrr rll EEcs Berkeley Em sbdZaJEEC kelayJEDlJ 169229 59 226 s hyperion cs aerkeley mm 169 229 60105 48 gammzasaginaamwm 106m 39 seoo 80 mae arm gt 3 4285 swim 99 458 am t A 3amp1 gimp A Bandwidth How much data can you transfer in a given amount of time 49 50 A B C D lmprovmg Bandw1dth Morse Code quot quotquot quotquot quot39 F G H Faster transmission Represent letters with series of Train signalers to move semaphore flags faster Short and long eleomoal pulses I J K L Use something less physically demanding to transmit Bigger pipes N O P Have multiple signalers transmit every other letter at the same time Q R S T Better encoding Figure out how to code more than 98 symbols with semaphore signal U V W X Morsecode18405 quot quot39 quot quot39 Y Z 51 Circuit Switching Reserve a whole path through the network for the whole message transmission Paris Once you start a transmission know you will have use of the network until it isfinished But wastes network resources Nantes 53 Packet Switching Use one link at a time I I l a B0 rges I x I I I Paris Lyon Toulon lnteneave messages send whenever the next link is free Nantes 54 Circuit and Packet Switching Land Telephone Network back in the old days Circuit when you dial a number you have a reservation on a path through the network until you hang up The Internet Packet messages are broken into small packets that find their way through the network link by link The First internet 1800 Sweden and Denmark worried about Britain invading Edelcrantz proposes link across strait separating Sweden and Denmark to connect their signaling telegraph networks 1801 British attack Copenhagen network transmit message to Sweden but they don t help Denmark signs treaty with Britain and stops communications with Sweden Okay so who invented the Internet 55 57 59 i nternetwork An internetwork is a collection of multiple networks connected together so messages can be transmitted between nodes on different networks 56 First Use of Internet October 1969 First packets on the ARPANet from UCLA to Stanford Starts to send quotLOGINquot but it crashes on the G 20 July 1969 Live video bw and audio transmitted from moon to Earth and to millions of televisions worldwide 58 The Modern Internet Packet Switching Leonard Kleinrock UCLA thinks he did Donald Davies and Paul Baran Edelcrantz s signalling network 1809 Internet Protocol Vint Cerf Bob Kahn Vision Funding JCR Licklider Bob Taylor Government Al Gore first politician to promote Internet 1986 act to connect government networks to form Interagency Network 60 Available within the network will be functions and services to which you subscribe on a regular basis and others that you call for when you need them In the former group will be investment guidance tax counseling selective dissemination of information in your field of specialization announcement of cultural sport and entertainment events that fit your interests etc In the latter group will be dictionaries encyclopedias indexes catalogues editing programs teaching programs The World W39Ide Web testing programs programming systems data bases and most important communication display and modeling programs All these will be at some late date in the history of networking systematized and coherent you will be able to get along in one basic language up to the point at which you choose a specialized language for its power or terseness J C R Licklider and RobeitW Taylor The Computer as a Communication Dewce April 1968 61 62 The World Wide Web World Wide Web Success Tim BemersLee CERN Switzerland World Wide Web succeeded because it was First web server and client 1990 Simple Didn t attempt to maintain links just a common way to name things Uniform Resource Locators URL I httprwwwc5virginiaeduics150indexhtml Service Hostname File Path Established a common language for sharing information on computers Lots of previous attempts Gopher WAIS Archie Xanadu etc HyperText Transfer Protocol 63 64 HyperText Transfer Protocol HTML HyperText Markup Language Server Language for controlling presentation of web pages GET cs150 ndexhtm HTTP10 Uses formatting tags ltmrnlgt Enclosed between lt and gt all Not a universal programming language Proof no way to make an infinite loop Client Browser HTML HyperText Markup Language 65 66 HTML Grammar Excerpt Document 1 lthtmlgt Header Body ltlhtmlgt Header I ltheadgt HeadElements ltlheadgt HeadElement HeadElements HeadElement 17 lttitlegt Element lttitegt Body ltbodygt Elements ltlbodygt t lement Elements ltpgt Element ltlpgt Make Element a paragraph Element ltcentergt Element ltlcentergt Center Element horizontally on the page Element ltbgt Element ltlbgt Display Elementin bold Element Text What is a HTML interpreter 67 Popular Web Site Strategy 1 Static Authored Web Site Drawbacks Have to do all the f already have enough Twinkleexperiment websites Web Programmer Content Producer 68 Popular Web Site Strategy Dynamic Web Applications Web Programmer Content Producer eBay in 1997 rttpMeb archive urgWeblBBTEIElAEIEIlAABrttpWW ebay uml Dynamic Web Advanta es 0 Users do most of the work 0 If you re lucky they might even pay you for the privilege not using UVa s servers Disadvantages 0 Lose control over the content you might et sued for things your users 0 t o Have to know how to program a web application eBay in 2007 70 Dynamic Web Sites Programs that run on the client s machine Java JavaScript Flash etc language must be supported by the client s browser so they are usually flaky and don t work for most visitors Used mostly to make annoying animations to make advertisements more noticea Occasionally good reasons for this need a fancy interface on client side like Google Maps Programs that run on the web server Can be written in any language just need a way to connect the web server to the program Program generates regular HTML works for everyone Almost Every useful web site does this 71 Dynamic Web Site GEI39 mm Wva 5 Virginia edulcsl SEIhuushungry Client Web Browser HTML Interpreter 72 uncomputability OneSlide Summary Vlruses I o In a proof by contradiction to show that A cannot exist you show that A implies the existence of X some knowntobeimpossible thing To show that A is undecidable or uncomputable pick X to be the halting problem ie halts Determining if a program is a worm or a virus is undecidable Sad face Objectoriented programming encapsulates state and methods together into objects This hides implementation details cf inheritance while allowing methods to operate on many types of input 2 Outline From the blaming the victim dept 39 PrOOf By Some but by no means all or even most students expect the Contradiction TAs to help them get started on a problem when they don39t know how to begin UndeCidabilit eve y At this point in CS 150 this is unacceptable Examples l have not made this clear so let me do so now Worms and Viruses GDP 0 Happiness in CS 150 managing expectations You should not expect that merely spending time on an assignment will cause you to master it cf entitlement Sketchpad I S I Merely spending time at a piano won t make you a pianist Imu a You are not doing yourself any longterm favors eg PARC exam2 the final if you can39t even get started without the Smalltalk TAS Concrete Suggestions o If a problem initially mystifies you Review lecture notes from Class 4 slide 35 de ne paradox Informal Proof 2 Step back and take out a piece of paper halts paradox 3 Write down the inputs and their types list int etc I f 4 Write down the outputs and their types OOp orever 5 Write down some example inputoutput pairs 6 Is it a recursive rocedure or not p If paradox halts the if test is true and 7 If it is what gets smaller Hint pick one of the inputs I I f d h I I 8 Does it have any conditional behavior If so what It eva uates to 00p orever It oesn t a t39 9 Write out in your own words in English what the procedure I should do If paradox doesn t halt the if test if false 10 Come to Weimer39s office hours and it evaluates to t It halts I have instructed the TA39s to skip what should I do questions from people who cannot show 29 on a piece of paper 5 6 Proof by Contradiction Goal Show A cannot exist 1 Show Xis nonsensical 2 Show that if you have A you can make X 3 Therefore A must not exist X paradox A halts algorithm Evaluatesto3 Problem Input A procedure specification P Output true if evaluating P would result in 3 false otherwise gt evaltothree 39lambda 2 1 t gt evaltothree 39lambda 2 2 f ls Evaluates to 3quot computable Undecidability Proof Suppose we could define evaluatesto3 that decides it Then we could define halts de ne halts P evaluatesto3 lambda begin P 3 lif t it evaluates to 3 so we know P must halt I if f the only way it could not evaluate to 3 is if P doesn t halt Note assumes P cannot produce an error How convincing is our Halting Problem proof define paradox if halts paradox loopforever t If contradicthalts halts the if test is true and it evaluates to loopforever it doesn t halt If contradicthalts doesn t halt the if test if false and it evaluates to t It halts This proof assumes Scheme exists and is consistent Scheme is too complex to believe thiswe need a simpler model of computation in two weeks Proof by Contradiction Goal ShowA cannot exist 1 Show X is nonsensical 2 Show that if you have A you can make X 3 Therefore A must not exist X halts algorithm A evaluatesto 3 algorithm HelloWorld Problem Input An expression specification E Output true if evaluating Ewould print out Hello World false otherwise Is the HelloWorld Problem computable Uncomputability Proof Suppose we could define printshelloworld that solves it Then we could define halts de ne halts P printshelloworld begin removeprints P print Hello World Liberal Arts Trivia British History This 9681016 king of England spent the majority of his reign in a defensive war against Danish invaders His nickname means quotevil counselquot quotbad planquot quotfollyquot or ill advised in Old English The invective is actually focused on those around him who were expected to provide the young king with good advice quotquot From Paul Graham s Undergraduation My friend Robert learned a lot by writing network software when he was an undergrad One of his projects was to connect Harvard to the Arpanet it had been one of the original nodes but by 1984 the connection had died Not only was this work not for a class but because he spent all his time on it and neglected his studies he was kicked out of school for a year When Robert got kicked out of grad school for writing the Internet worm of 1988 I envied him enormously for finding a way out without the stigma of failure It all evened out in the end and now he s a professor at MIT But you ll probabl o apier if you don t go to that extreme it caused him the time I3 years ofprobation 400 hours of community service 10000 ne Proof by Contradiction Goal Show A cannot exist 1 ShowX is nonsensical 2 Show that if you have A you can make X 3 Therefore A must not exist X halts algorithm A printshello world algorithm 14 Liberal Arts Trivia Modern Cinema and English Language Name the twotime Emmy awardwinning actor who appeared in movies with titles synonymous to these Fiber Fabrication Immoral Metropolis Fail Difficult Invincible The RightToRemainSilent Component Catastrophe The DistanceFromKevinBacon Awareness Worm Detection Problem Input A program P and input I Output true if evaluating P I would cause a remote computer to be infected Virus Detection Problem Input A program specification P Output true if evaluating P would cause a file on the host computer to be infected Morris Internet Worm 1988 Computer Security Paradoxes P fin erd g ls isvirus computable Program used to query user status Worm also attacked other programs Change Password I nop400 pushl 68732f pushl 6e69622f movl Entarvuurcurrentand new passwnrds spr10 pushl 0 pushl 0 pushl r10 pushl 3 movl curremasswurd m SPaP chmk 53b New passwuru isworm P I should evaluate to t mm so39lnrnemp mr Worm infected several thousand computers 10 of Internet in 1988 The old and new passwards are not same OK Cancel Uncomputability Proof Uncomputability Proof Suppose we could define isvirus Then dgf39n haltS P isVirus de ne halts P ambda 0 isvirus Iambda begin removeinfects P infectfiles begin removeinfects P t Since it is a virus we know infectfiles was Can we make remove lnfect es evaluated and P must ha infects f The infectfiles would not evaluate so P Yes just remove all le writes must not halt l Solving Undecidable Problems No perfect solution exists Conclusion Undecidable means there is no procedure that 39 Antl39Vlrus Programs cannOt eXlStl 1 Always gives the correct answer er ArtLOfFCVomr o and also 2 Always terminates g Re arch an f Peter39Szor39 Must give up one of these to solve I 39 undecidable problems Giving up 2 is not acceptable in most cases Must give up 1 Or change the problem eg detect file infections during an execution Actual isvirus Programs Proof Recap Give the wrong answer sometimes False positive say P is a virus when it isn t If we had isvirus we could define halts False negative say P is safe when it is We know halts is undecidable Database of known viruses if P matches one Hence we can t have isv1rus Of these It 5 a quot5 Thus we know isvirus is undecidable Clever virus authors can make viruses that change each time they propagate Emulate program for a limited number of steps if it doesn t do anything bad assume it is safe PreHistory MIT s Project Whirlwind 194719605 1 M n History of 39 39 ObjectOriented Programming Jay Forrester Why Whirlwind Whirlwind Innovatio From an earlier class o 39 7 V 7 60000 50000 10000 Ma netic Core Memory first version used vacuum tubes the rst computer that operated in real time used video displays for output and the rst that wa ot simp y an ele ronic replacement of older mechanical systems Its development led directly to the Unite States Air Force39s Semi Automatic Ground Environment em and indirectly to almost all 29 business computers and minicomputers in the 196 s 0 1940 1950 1960 1970 1980 1990 2000 2010 2020 Sketchpad Ivan Sutherland 1963 PhD thesis supervised by Claude Shannon Interactive drawing program Light pen Turing Award 1988 Objects in Sketchpad In the process of making the Sketch pad system operate a few very general functions were developed which make no reference at all to the specific types of entities on which they operate These general functions give the Sketchpad system the ability to operate on a wide range of problems The motivation for making the functions as general as possible came from the desire to get as much result as possible from the programming effort involved For example the general function for expanding instances makes it possible for Sketchpad to handle any fixed geometry subpicture The rewards that come from implementing general functions are so great that the author has become reluctant to write any programs for specific jo s Each of the general functions implemented in the Sketchpad system abstracts in some sense some common property of pictures independent of the specific subject matter of the pictures themselves Ivan Sutherland Sketchpad a ManMachine Graphical Communication System 1963 major influence on Alan Kay developing GOP in 19705 Liberal Arts Trivia Music This traditionallyfemale vocal range lies below mezzosoprano and is usually viewed as the deepest female singing voice The typical range lies between the F below middle C F3 to two Fs above middle C F5 Ruth in Gilbert and Sullivan39s Pirates of Penzance and Lel in RimskyKorsakov39s The Snow Maiden are example operatic roles Components in Sketchpad Liberal Arts Trivia Geography Name the most populous metropolitan area on Earth It contains 23 special wards each one of which is t t 1 39ll39 35 mi 71011 d as a CI eople It e Simula Considered the first objectoriented programming language Language designed for simulation by Kristen Nygaard and OleJohan Dahl Norway 1962 Had special syntax for defining classes that package state and procedures together Counterin ShnL a class counter integer count begin procedure reset count 0 end procedure next count count 1 end integer procedure current current count end end Don t worry about what anybody else is going to do The best way to predict the future is to invent it Really smart people with reasonable funding can do just about anything that Dynabook1972 Just a model Aan Kay 1971 BYTE Maga ne August 1981 doesn t violate too many of Newton s Laws XEROX Palo Alto Research Center PARC 19705 Bitmapped display Graphical User Interface Steve Jobs paid 1M to visit PARC bought their stock and returned to make Apple LisaMac Ethernet First personal computer Alto PostScript Laser Printers ObjectOriented Programming Dynabook1972 Tablet computer Intended as tool for learning Kay wanted children to program it also Hallway argument Kay claims you could define the most powerful language in the world in a page of code Proof Smalltalk Scheme is as powerful but takes two pages Before the end of CS 150 we will see an equally powerful language that fits in 1A page snmuam Everything is an object Objects communicate by sending and receiving messages Objects have their own state which may contain other objects How do you do 3 4 send the object 3 the message 4 Puzzles Costs and Sneezewort OneSlide Summary 0 We can solve a game by recursively enumerating all legal moves from a position stopping when we39re left with a winning board or no more possible moves 0 The basic recursive computation of Fibonacci can take quite a while There are faster ways 0 We can formally measure and evaluate the cost of a computer program We abstract away details such as processor speed and instead measure how the solving time increases as the input increases Outline o That Cursed Pegboard Jumps legal moves winning o Sneezewort and Fibonacci o Cost of computing Fibonacci o Cost of sorting J M Solving the Peg Board Game o Try all possible moves on the board o Try all possible moves from the positions you get after each possible first move o Try all possible moves from the positions you get after trying each possible move from the positions you get after each possible first move Example Board Grey de ne greyrows 5 de ne greyholes list makeposition 1 1 make position 2 1 makeposition 2 2 makeposition 3 2 de ne greyboard make board greyrows greyholes Filter Remove define filler pred lsl if nun isl nul r pred car lst pred rslrue kee 1 cons car isl filler proc cdr 150 filler pred cdr lst pred is false 1man define removehole lst posn filter lambda pos not sameposition pos posn lst J u m ps move creates a list of three positions a start the posn that the jumping peg starts from ajump the posn that is being jumped over and end the posn that the peg will end up in define makemove start jump end list start jump end define getstart move first move define getjump move second move define getend move third move executemove evaluates to the board after making move move on oar define executemove board move addpeg removepeg removepeg board getstart move getjump move getend move Finding a Winning Strategy How is winning 2 person games eg chess poker different h Vl nning position Pegboard Puzzle Blue Circle Hole Position 41 42 43 44 51 52 53 54 55 How do we find all possible jumps that land in a given target hole Pegboard Puzzle 11 22 31 32 33 42 44 51 52 53 54 55 How do we find all possiblejumps that land in a given target hole 10 Pegboard Puzzle 11 21 22 32 41 42 43 44 52 54 65 How do we find all possible jumps that land in a given target hole All Moves into Target 393939 generatemoves evaluates to all possible moves that move a peg into 393939 the position target even if they are not contained on the board define generatemoves target map lambda hops let hop1 car hops hopZ cdr hops makemove make position getrow target car hop1 getcol target cdr hop1 l l l l makeposition getrow target car hopZ getcol target cdr hop2 target list cons cons Z 0 cons 1 0 right of target hopping left cons cons 2 0 cons 1 0 left of target hopping right cons cons 0 2 cons 0 1 below hopping up cons 0 2 cons 0 1 above hopping down cons 2 2 cons 1 1 above right hopping downleft cons cons 2 2 cons 1 1 above left hopping downright l l cons 2 2 cons 1 1 below right hopping upleft cons cons 2 2 cons 1 1 below left hopping upright m All Possible Moves Legal Move d f H bl b d define legalmove move gggzrgg osg e39moves oar A move is valid if map generatemoves boardmoles holesm o the start and end positions are on the board 0 there is a peg at the start position define appendall Ist 0 there is a peg at the jump position if null 3980 nu 0 there is not a peg at the end position append car Ist appendall 0dr st and onboard board getstart move onboard board getend move Butonly legal if start and end are positions Peg board getSEWt m0Ve on the board containing pegs Peg board getJump m0Ve Note could use apply append instead of appendall net board getend move 13 14 All Legal Moves define legalmove move de ne allpossiblemoves board HA move is validif All Legal Moves de ne legalmove move de ne allpossiblemoves board A move is valid if appenda 39 o the start and end positions are on the board appenda 3939 o the start and end positions are on the board map generate oves 3939 0 there is a peg at the start position map generatemoves 3939 0 there is a peg at the start position we zis2izgz39siizzix stim new ii 2222ieiz39ziiizzisz izim and on board board gel sla ove and onboard board gelslarl move onboard board gelend move onboard board gel end move peg board gel sla ove peg board gel sla e peg oard geljum move peg board geljump move nol peg board gelend move nol peg board gelend move define legalmoves board define legalmoves board filter legalmove allpossiblemoves board Winnin Becoming a Genius g POSition A C Try all possible legal moves How do we tell if a board is in a winning position Mnning position iswinningposition define boardsquares board countsquares boardrows board define countsquares nrows if nrows 1 1 nrows countsquares nrows 1 define iswinningposition board length boardholes board boardsquares board 1 All Cracker Barrel Games starting with peg 2 1 missing Solve Pegboard define solvepegboard board findfirst winner board legalmoves board define findfirstwinner board legalmoves returns a list of moves that will solve the given board if null legalmoves if iswinningposition board null Found winning game no moves needed f A losing position no more moves let result solvepegboard executemove board car egalmoves if result winner not 0 cons car legalmoves result this move wins findfirst winner board cdr legalmoves try rest All Cracker Barrel Games starting with peg 2 1 missing Pegs Number Fraction of Cracker Barrel Pegs Number Fraction of Cracker Barrel Left of Ways IQ Rating Left of Ways Games In Rating 1 1550 001 You re Genius 1 1550 001 You re Genius 2 20686 015 You re Purty Smart 2 20686 015 You re Purty Smart 3 62736 046 Just Plain Dumb 3 62736 046 Just Plain Dumb 4 46728 033 4 46728 033 5 5688 004 Just Plain 5 5688 004 Just Plain 6 374 0 0027 E g noramoose 6 374 00027 EQ39no39ra39moosequot 7 82 000058 7 82 000058 Leaving 10 pegs requires much 10 2 000001 lt 10 2 000001 more brilliance than leaving 1 Liberal Arts Trivia History This 20thcentury Amen can inventor is credited with the phonograph the carbon telephone transmitter the practical electric light and the phrase Genius is one percent inspiration ninetynine percent perspiration He fought against Nikola Tesla39s alternating current in the socalled War of the Currents 23 Liberal Arts Trivia Physics Count Alessandro Antonio Anastasio Volta was a 19thcentury Italian physicist Volta studied what we now call capacitance developing separate means to study both electrical potential Vand charge Q and discovering that for a given object they are proportional His experiments in animal electricity in which two different metals were connected in series with frog39s legs eventually led to his most famous discovery What was it 24 Alie m men byEen Mumsun and szPe evsun Sneezewort Achillea ptarmica is real fficacious in the inflaming of the braine and is 3 on here the wizard is desirous of producing hotheadedness and recklessnessquot Order of the Phoenix p15 Sneezewort39s pattern of development displays the Mamba byJamweJeun ampWenev Huyges F b quota sequeme39 35 a Sneezewort G rowth Sneezewort Numbers erst Tune Umt Secund Tune Umt orrshuut m by Jessma 3251 EH2quot C avke Cuu d WE mude Sneezewun wnh P83 cude7 m e Fibo Results gt bo 2 I gt bo 3 gt bo 4 3 gt bo 10 55 gt bo 60 Still working AIeast we mysth bmeMySemenuv and Save Nepaugh gt require ibrary quottracessquot gt trace bo bo gt bo 3 bo 3 bo 2 bo 1 1 2 eumLeAm 2 by Rache Lethhmy and Andvee Vuun man 5 A mm WWW ime 5 Mm missiiim imbab Moms iimeZ iii iimbai iii 2m 2 a Tu caicuiaie NIB 5 We caicuiaied i3 buA itiihs WM bu 2tiihss WM WU 3mm mimsmi WW ha 1 2h 25 iii 8 caiisiu him iihuis 2 i5 Huw ihshy caiisiu caicuiaie iihu 607 FastFibo Results gt fast bo 10 gt time fast bo 61 cpu time 0 real time 0 go time 0 2504730781961 Sn Diiginai iihuwuuiu take at ieas12 5 Tiiiiiuii sppiisstiuhs 2 5 GHz cumpuiev duesZ 5 siiioh simpie upsistiuhs psi 525mm suZ 5 Tiiiiiuii sppiisstiuhs upsistiuhstsks innn ssssh s Essh sppiisstiuh unihu invuiVES hundYEdS sisiihpis upsistiuhs gt d2 J A hpica isbms mass is 2 5 hiogisms gt usiihs massruirvabbiiz 5 gt massruirvabbii Vasir bu ism massruireanh 6A5 3663321113 gt massruirvabbii asir bu12Dmaseuireanh 22326696395795693 The Earth s mass is 5 0 x 1m this mas 24 hg sruireanh 5 Expi in 24 Accnrding ts Banacu s mudei a er i255 thsh 1n yEarSi rabbits Wnuid Dutrweigh the Esithi Beware the Bunnies Beware the Sneezewortll t1 fastfibo de ne fast a n de ne fibhelper a b Ie iflt le 0 b b helper b a b Ieit 1 bhelper1 1 n 2 The Earth s mass is 5 n X mm hg gt usiihs massruireanh 5 Expi mm A tpicsiisbm s mass is 2 5 hiogisms usiihs massruirvabbiiz 5 gt masguirvabbii iasMbuEElD massruireanh 6A5 3663321113 gt masguirvabbii Vast bu izu msssutssnh 22326696395795693 gt Accnrding ts ashsssi39s mudei a er i255 thsh 1n yEarSi rabbits Wnuid Dutrweigh the Esithi Evaluation Cost Measuring Cost Actual running times vary according to How fast a processor How does the cost scale 1 with the size of the input you have If the input size increases 39 0 mm mem W by one how much longer you have will it take7 Where data is located 39 in memory If the input size doubles 39 HOW hot it is 43 WW 9 how much longer will it What else is running Moore s Law computing power doubles take Untitled 39 etc every 18 mmths Nokomis McCaskill Chris Hooe 157 38 Cost of Fibonacci Procedures Cost of Fibonacci Procedures de ne bo n define fastfibo n de ne bo n define fastfibo n if or n 1 n 2 de ne bhelper a b left if or n 1 n 2 define f bhelper a b left 1 base case If left 0 a 035 39f left 0 bo n 1 b bo n 1 b bo n 2 fibhelper b a b left 1 bo n 2 f bhelper b a b left 1 fibhelper1 1 n 2 fibhelper1 1 n 2 Input fibo fastfibo Input fibo fastfibo m q mk m q mk m1 m1k m1 qlt1gt m1k m2 at least qz m2k m2 at least qz m2k lt1gt 1 sqrt 5 2 The Golden Ratioquot 1618033988749895 fast bo 61 fast bo 60 1618033988749895 159 40 The Golden Ratio More Golden Ratios httplwwwfenkefengorgessaysm18004htm by Oleksiy Stakhov Nautilus Shell 41 42 Liberal Arts Trivia Medicine Nicolae Paulescu was a 20th century physiologist and professor of medicine He is considered the true discoverer of hormone that causes most of the body39s cells to take up glucose from the blood His first experiments involved an aqueous pancreatic extract which when injected into a diabetic dog proved to have a normalizing effect on blood sugar levels Name the hormone 43 Liberal Arts Trivia Sailing Name the collection of apparatus through which the force of the wind is transferred to the ship in order to propel it forward this includes the masts yardarms sails spars and cordage PS2 Question define findbesthand hands car sort hands higherhand define findbest Ist of if 1 length Ist car Ist pickbetter cf car Ist findbest cdr Ist cf define pickbetter of numi num2 if of numi num2num1 num2 define findbest hand hands findbest hands higherhand Which is better and by how much 45 Simple Sorting Can we use findbest to implement sort Yes Use findbest lst to find the best Remove it from the list Adding it to the answer Repeat until the list is empty by Victor Malaret Folami Wlliams 46 Simple Sort of comparison function define sort Ist cf simple sort if null Ist Ist let best findbest Ist cf cons best sort delete Ist best cf delete Ist x lter not eq x 47 Sorting Hands de ne sort Ist cf if null Ist Ist let best ndbest Ist cf cons best sort delete Ist best cf de ne sorthands Ist sort Ist higherhand 48 Sorting define sort lst cf if null Ist lst let best findbest lst cf cons best sort delete lst best cf define findbest lst cf if 1 length lst car lst pickbetter cf car Ist findbest cdr Ist cf define pickbetter cf num1 num2 if cf num1 num2 num1 num2 How much work is sort 49 Sorting Cost 0 What grows in the number of elements in st 0 How much work are the pieces findbest delete 50 Sorting Cost 0 What grows in the number of elements in st 0 How much work are the pieces findbest work scales as 11 increases by one delete work scales as 11 increases by one 0 How many times does sort evaluate findbest and delete 51 Sorting Cost 0 What grows in the number of elements in st 0 How much work are the pieces findbest work scales as 11 increases by one delete work scales as 11 increases by one 0 How many times does sort evaluate findbest and delete n 0 Total cost scales as 52 Sorting Cost 0 What grows in the number of elements in st 0 How much work are the pieces findbest work scales as 11 increases by one delete work scales as 11 increases by one o How many times does sort evaluate findbest and delete n 0 Total cost scales as n2 53 Sorting Cost define sort Ist cf if null Ist Ist let best findbest Ist cf cons best sort delete Ist best cf define findbest Ist cf if 1 length st car Ist pickbetter cf car Ist findbest cdr Ist cf If we double the length of the list the amount of work approximately quadruples there are twice as many applications of findbest and each one takes twice as long 54 PS4 M39itten can he turned in urin structured of ce hours Quickest Sorting and Double Deltas Monday Feb 23 and Wednesday Feb 25 MEC 205 until 530pm Build and program Lego Mindstorms robot to remotely sense and navigate a barren environment and retrieve a life pod from a crater Exam 1 Extra Credit either show up and watch one day or write paragraph about how to do it OneSlide Summary Insertsort is nl worst case reverse list but is n best case sorted list A recursive function that divides its input in half each time is often in log n o If we could divide our input list in half rapidly we could do a quicker sort nlog n Sorted binary trees are an efficient data structure for maintaining sorted sets British codebreakers used cribs guesses brute force and analysis to break the Lorenz cipher Guessed wheel settings were likely to be correct if they resulted in a message with the right linguistic properties for German eg repeated letters 3 Outline Insertsort Going halfsies Sorted binary trees Quickersort WWII Codebreaking Pigkyp Graded During Structure Hours Today How much work is insertsort define insertsort Ist of if null Ist null insertone car Ist insertsort cdr Ist cf cf define insertone el Ist of if null Ist list el if of el car st cons el Ist cons car Ist insertone el cdr Ist cf How many times does insert sort evaluate insertone n times once for each element running time of insert one is in n insertsort has running time in nz where n is the number of elements in the input list Which is better ls insertsort faster than bestfirstsort AccuPOPTM Probability of Precipitation 39 l l l i 38 32 32 81 5 a 63 BP11P 11P2A 2A5A SABA BAi iA Mon gt insertsort lt revintsto 20 1234567891011121314151617181920 Requires 190 applications of lt gt insertsort lt intsto 20 1234567891011121314151617181920 Requires 19 applications of lt gt insertsort lt randint list 20 0111619 23 26 3132 32 34 42 45 53 63 64 8182 84 84 92 Requires 104 applications of lt bestfirstsort vs insertsort 0 Both are nz worst case reverse list 0 Both are nz when sorting a randomly ordered list But insertsort is about twice as fast 0 insertsort is n best case ordered input list quickerinsert using halves define quickerinsert el lst cf if null lst list el just like insertone if null cdr st if cf el car lst cons el lst list car lst el let front rsthalf lst back secondhalf lst if cf el car back append quickerinsert el front cf back append front quickerinsert el back cf gt bestfirstsort lt intsto 20 1234567891011121314151617181920 Requires 210 applications of lt gt bestfirstsort lt randintlist 20 44161819 20 23 32 36 5153 59 67 69 73 75 82 82 88 89 Requires 210 applications of lt Can we do better quickerinsert lt 88 list 1 2 3 5 6 23 63 77 89 90 Suppose we had procedures firsthalf lst secondhalf lst that quickly divided the list in two halves 10 Evaluating quickersort gt quickerrlnsert lt 3 llsM 24 5 7 4 2 4 5 7 de ne quickerinsert el Isl cf if null Isl list el if null cdr Isl if cf el car Isl lt339l lt35 qtllckerrlll en ltprocedule tracedltgt 3 1 2 4 lt3 l cons ellsl T list car Isl e 3 4 let rrom rsthalf Isl V 7 back secondhalf Isl Elm insert ltproceduretraced ltgt 3 1 2 ind el car back f append quickerinsert el from cf back lt 3 2 append ron quickerinsert el back c0 quickerrlnsertltprocedure tracedrltgt 3 2 lt 3 2 MT 323 Every time we call quicker jgfj 7 insert the length of the list is 234 57 approximately halved 12 How much work is quickersort Liberal Arts Terlai Each time we can de ne quickerinsert el isi cf 39 The argan tree found ifriulllsilisiel in Morocco has a quickerinsert the size of If gull lcdrlstl anan y Ist halves So doubling 39 Ezo sifis knobby twisted trunk that lhe 83928 Oflhe St only lellliirlilliairl39isi2ilialflsi allows these animals to climb increases the number of backsecondhalfls calls by 1 ifcfelcarback it eaSily The animals eat the d 39 k 39 rt If i b k 25533199111 Elms I m 23 fru1t which has an qLIIC er inser e EC C List Size quickerinsert applications lndlgeStlble nUt InSIde WhICh g is collected by farmers and g i used to make argan oil handy 16 5 in cooking and cosmetics but pricey at 45 per 500 ml Liberal Arts Trivia Scandinavian Studies This capital of and largest city in Denmark is Remembering Logarithms situated on the islands of Zealand and Amager 10gb n 2 x means bx n It is the birthplace of Neils Bohr Soren Kierkegaard and Victor Borge The city39s origin What is 10g2 1024 as a harbor and a place of commerce is reflected in its name Its original designation What 395 logio 1024 from which the contemporary Danish name is derived was Kopmannaehafn quotmerchants39 ls loglon in 9log2 n harborquot The English name for the city is derived from its similar Low German name 16 Changing Bases Number of Applications Assuming the list is wellbalanced 1 n 2 1 1 b 1 n the number of applications of 0gb ng ng quickerinseit is in log n where n Ifkand bare is the number of elements in the 09nstantsv input list this is constant logzn E loglon E 10g n I No need to include a constant base within asymptotic operators I 18 quickersort de ne quickerinsert el Isl cf de ne quickersort lst cf if quotUN7 395 H51 6I if null lst null 0 N W 3950 qui cker inselt of 22353450 car lst list car Isl e quickersort cdr lst cf Iel frorll rsthalf ISO back secondhalflsl if cf el car back append quickerinsert el front cf back append ronl quickerinsert el back c0 quickersort using halves would have running time in n log n ifwe have firsthalf secondhalf and append procedures that run in constant time Is there a fast firsthalf procedure No at least not on lists To produce the first half of a list length n we need to cdr down the first n2 elements So firsthalf on lists has running time in n quotNothing yell quot ow about you Nemon 23 Orders of Growth 14000 12000 10000 8000 6000 4000 2000 71 0 1 9 17 25 33 41 49 57 65 73 B1 89 97105 20 Making it faster We need to either 1 Reduce the number of applications of insertone in insertsort Impossible need to consider each element 3 Reduce the number of applications of quickerinsert in quickerinsert Unlikely each application already halves the list 5 Reduce the time for each application of quickerinsert Need to make rsthalf secondhalf and append faster than n Sorted Binary Trees left a right A tree containing all elements X such that cf X el is true A tree containing all elements X such that cf X el is false 24 Tree Example null null null null null nu cfislt Tree Example Where would we put 3 Cf is lt null null null null null null 26 Representing Trees Representmg Trees define maketree left el right M and right are trees 6 cons el cons left right null is atree define treeelement tree 9 6 car tree tree must be a nonnull tree define treeleft tree CI car cdr tree quotas mu be a 39 quot55 maketree maketree maketree null 1 null 2 define treeright tree null cdr cdr tree tree must be a nonnull tree maketree null 8 null 27 28 insertonetree define insertonetree cf el tree if null tree maketree null el null if cf el getelement tree maketree insertonetree cf el getleft tree getelement tree getright tree maketree getleft tree getelement tree insertonetree cf el getright tree rig rees lfthe tree is null make a new tree with el as its element and no le or Otherwise decide if el sh 39 the le or right subtree insert it into that ree but leave the other subtree unchanged ould be in How much work is insertonetree de ne insertonetree cf el tree if null tree maketree null el null if cf el getelement tree mak e Each time we call insertonetree the size of the tree approximately halves if it is well inseneltree cf el getleft tree getelement tree getright tree balanced maketree getleft tree getelement tree Each application is inserteltree cf el getright tree 39 constant time The running time of inserteltree is in 8 log n where n is the number of elements in the input tree which must be wellbalanced quickerinsertone define quickerinsertone cf lst if null lst null insertonetree of car lst quickerinsertone cf cdr lst No change other than using insertone treebut evaluates to a tree not a list 0 1 O 2 O 5 O 8 0 B1 Liberal Arts Trivia Classics This ancient Greek epic poem traditionally attributed to Homer is widely believed to be the oldest extant work of Western literature It describes the events of the final year of the Trojan War The plot follows Achilles and his anger at Agamemnon king of Mycenae It is written in dactylic hexameter and comprises 15693 lines of verse It begins u vw quotxcl c Gcc x I39InAn39l39d em AxtA oq oDAou vnv F pupi39 Axaloiq quotxAye39 enkcv B3 Lorenz Wheels 12 wheels 501 pins total set to control wheels Work to break in pw so real Lorenz is 411253 1 quintillion 1018 times harder B5 Lorenz B2 Liberal Arts Trivia Literature Name the author of the Age of Innocence 1920 The novel describes the upper class in New York city in the 18705 and questions the mores and assumptions of society The title is an ironic comment on the polished outward manners of New York society when compared to its inward machinations The authors was the first woman to win the Pulitzer Prize for Literature Code Breaking Intuition Suppose we are using a simple letter substitution cipher ie replace every A with Q etc You intercept these two messages pf150 szchgre varapr sebz Nqn naq thyvq gb Dhnaghz szchgvat naq gur Jbeyq qur Jro pf150 szchgre varapr sebz Nqn gb gur Jbeyq qur Jro What does the first one say What hints did you have 36 Breaking Fish Gov39t Communications HQ learned about first Fish link Tunny in May 1941 British codebreakers used Fish to refer to German teleprinter traffic Intercepted unencrypted Baudotencoded test messages August 30 1941 Big Break Operator retransmits failed message with same starting configuration Gets lazy and uses some abbreviations makes some mistakes 0 SPRUCHNUMMERSPRUCHNR Serial Number 57 Cribs Know C1 C2 intercepted ciphertext C1 9 C2 M1 9 M2 Don t know M1 or M2 But can make some guesses cribs SPRUCHNUMMER Sometimes allies moved ships sent out bombers to help the cwptographers get good cribs Given guess for M1 calculate M2 M2 C1 9 C2 9 M1 Once guesses that work for M1 and M2 K1M1 C1M2 C2 B9 Intercepting Traffic Set up listening post to intercept traffic from 12 Lorenz Fish links Different links between conquered capitals Slightly different coding procedures and different configurations 600 people worked on intercepting traffic 41 Two Time Pad Allies have intercepted C1 M1 3 K1 C2M2 K1 Same key used for both same starting configuration Breaking message c1 ec2 M1 K1 M2 K1 M1 M213 K1 9K1 M1 3 M2 Reverse Engineering Lorenz From the 2 intercepted messages Col John Tiltman worked on guessing cribs to find M1 and M2 4000 letter messages found 4000 letter key K1 Bill Tutte recent Chemistry graduate given task of determining machine structure Already knew it was 2 sets of 5 wheels and 2 wheels of unknown function Six months later new machine structure likely to generate K1 40 Breaking Traffic Knew machine structure but a different initial configuration was used for each message Need to determine wheel setting Initial position of each of the 12 wheels 1271 possible starting positions Needed to try them fast enough to decrypt message while it was still strategically valuable I This is what you did for PS4 except with fewer wheels I 42

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.