Intro to Computer Science
Intro to Computer Science CPSC 201
Popular in Course
Ms. Leora Smitham
verified elite notetaker
Mr. Tessie Labadie
verified elite notetaker
Mr. Tessie Labadie
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in ComputerScienence
This 35 page Class Notes was uploaded by Ms. Leora Smitham on Thursday October 29, 2015. The Class Notes belongs to CPSC 201 at Yale University taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/231020/cpsc-201-yale-university in ComputerScienence at Yale University.
Reviews for Intro to Computer Science
Report this Material
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: 10/29/15
CPSC 201 A Brief and Informal Introduction to the Lambda Calculus Paul Hudak Spring 2008 There are three kinds of expressions also called terms in the pure lambda calculus m variables Am e abstractions e1 e2 applications where m y etc are variables and e e1 etc are nested expressions lntuitively abstractions represent functions and applications represent the application of a function to its argument In this sense variable names are arbitrary so that for example Am m represents the same function as Ay y Syntactic conventions 1 e1 e2 e3 is short hand for e1 e2 e3 2 The binding of A extends as far to the right as possible overidden in the usual way by parentheses So Am m m is the same as Am m m but is different from Am m m A particular instance of a variable is free in a lambda expression if it is not bound by a lambda For example m is free in the expressions m and Ag m but not in Am m Because variables can be repeated care must be taken to know which variable one is referring to For example in this expression the underlined occurrences of x are free the others are not Ay m Am m m m A term is closed if it has no free variables otherwise it is open The only reduction rule of interest in this course is called beta reduction and is de ned by Am 51 52 6162 where the notation e1e2m denotes the result of substituting e2 for all free occurrences of m in el For example Am m Ay y Ay y M 90 90 M y 5 M y M 24 Am m Am y a y Am m However care must be taken to avoid name capture of bound variables For example this reduction would be wrong Am Ay y Ay y because the outer y is presumably different from the inner y bound by the lambda In cases like these the bound variable is renamed to obtain the correct behavior Am Ay y A2 y A reducible expression or redex is any expression to which the above beta reduction rule can be immediately applied For example Am Ay y z is not a redex but its nested expression Ay y z is The location of a redex relative to another is the point at which it begins in a left to right scan of the text Some expressions have more than one redex and it turns out to be important to decide which redex to reduce rst There are many different reduction strategies but the three of most interest in this course are 1 Normal order reduction Choose the left most redex rst 2 Applicative order reduction Choose the right most redex rst 3 Haskell evaluation more or less Choose the left most redex rst as in normal order reduc tion but only if it is not contained within the body of a lambda abstraction An expression with no redex is said to be in normal form Some expressions do not terminate using any of the above reduction strategies For example Ax m m Ax m m Ax m m Ax m m Ax m m Ax m m a Some terminate under normal order reduction but not under applicative order For example this expression Ax y m m Ax m has two redexes If we choose the right most one applicative order it will not terminate But if we choose the left most one it will reduce in one step to the expression y It turns out that if an expression has a normal form then normal order reduction will nd it In other words normal order reduction terminates most often When constants or primitive values and functions are desired special reduction rules can be added which create opportunities for other redexes Examples include 11 2 addition 12 a 3 a 1 multiplication s 2 head cons m ms m lists tail cons m ms ms oond true e1 eg a el conditional cond false 51 52 a 52 etc Alternatively we can simulate these primitives using just the pure lambda calculus 0 E fm m 1 E fm f m succ E nfm f n f m add E mnfz m f n f m cons E Amys s m y head E ll Amy m tail E ll Amy y 007111 E pca p c a true E ca 0 false E ca a In order to get the effect of recursion one can de ne what is called the Y combinator or xed point operator as Y E f Am 1 x Am 1 x Recursion is not something that is directly supported by the lambda calculus But any recursive de nition such as g E g can be rewritten as g E y A9g which is non recursive and is thus a valid lambda expression For example here is a recursive and then a non recursive de nition of the factorial function fact E An 00nd n 0 1 gtk n fact E n fact E Yf An 00nd 71 01 71E n CPSC 201 Course Lecture Notes Spring 2008 Day1 Jan14 Welcome and preliminaries o Are you in the right course distribute handout Email via classesv2 classesv2yaleedu Course website pluckycsyaleeducs201 Class on Friday this week and not next Monday TF Amittai Aviram see website for of ce hours TBD Two required texts Omnibus and SOE Moreorless weekly homework assignments plus two exams CPSC 201 is the hardest course to teach in the CS curriculum Primarily because this question is hard to answer What is computer science Is it a science a physical science a natural science Or is it more like mathematics or engineering One could make an argument for all or none ofthesel It is not the study of computers any more than astronomy is the study of telescopes Nor is it is the study ofprogramming any more than literature is the study of grammar Dewdney s approach our textbook is to give enough examples of cool ideas in CS that you will just know what it is kind of by osmosis in the same sense that one just knows pornography when one sees it Broadly speaking computer science is the study of information computation and communication The purpose of CPSC 201 is to give a broad overview of this There is another crosscutting theme that underlies CS and that is abstraction There is an interesting CACM article Vol 504 April 2007 called ls Abstraction the Key to Computing In my textbook ask the question What are the three most important ideas in programming to which I offerthe answer Abstraction abstraction abstraction Like the realestate question Functions are a good abstraction for programming because they imply computation taking an input and returning an output and determinacy one answer instead of many Haskell is particularly good at abstraction More on this later Abstraction is not that unfamiliar to the average person In fact there are often multiple levels of abstraction that we are familiar with Let s ask ourselves some simple questions How does a toilet work How does a car work How does a refrigerator work How does a microwave oven work ewwe For each of these we can describe a user interface version of how X works that is perfectly adequate for the user But it doesn t tell us what s under the hood so to speak We can then give a more concrete less abstract description of how something works and in some cases this is done in several steps thus yielding different levels of abstraction We can also ask ourselves computerrelated questions How does an iPod work How does a cell phone work How does a computer work How does the Internet work How does a particular software program work i Google or some other search engine ii Microsoft Word iii A video game iv A GUI mhwwe In this class we will try to answer a smorgasbord ofthese questions using different levels ofabstraction A key concept will be that of an algorithm an abstract recipe for computation We will use Haskell to actually execute our abstract algorithms Speaking of which Haskell was for many years considered an academic language In recent years it has become cool It has also become a practical language and many commercial aps that use Haskell are starting to appear See haskellorg for all you will ever need to know about Haskell Also start reading SOE We will start our tour of CS with hardware There are eightchapters in the Omnibus that cover hardware we will not cover all of them but will get through most And we will use Haskell to build hardware abstractions Reading Assignment the rst 2 chapters in SOE and chapters 13 28 and 38 in the Omnibus Day 2 Jan 16 In SOE I use multimedia to motivate FPHaskell I will ask you to read this stuff but in class I will use the Omnibus as a source of motivation instead Ok Boolean Logic Chapter 13 Named after the mathematician George Boole who did his work in the 1850 s Corresponds to digital circuits of today Why is digital good In any case the key idea is that there are just two Boolean values 1 and 0 Or True and False Black and white Life and death A Boolean function is a function that takes Boolean values as input and yields Boolean values as output The behavior ofa Boolean function can be described using a truth table Do the Omnibus multiplexer example Then do a half adder How many functions are there that take n Boolean inputs A 2 to the 2 to the n For example for n3 that s 256 for n4 that s 65536 A Boolean expression is made up of 0 1 Boolean variables and combinations of these using the operators AND OR and NOT Write truth tables for these Any truth table can be converted in to a Boolean expression by constructing the disjunctive normal form Give examples There is also a conjunctive normal form Mathematically all this establishes an algebra namely Boolean algebra consisting ofthe following axioms O and 1 are Boolean values such that x0 x and x1 x xy and xy are Boolean values xy yx and xy yx xyz xy xz and x yz xyxz xx 1 and xx O U39AFDNT This set of axioms is complete any true fact theorem about Boolean expressions can be deduced from the axioms Examples x1 1 xx x xx x Proof of 2nd one x x1 xxx xx xx xx O xx Show corresponding proof using truth table More importantly associativity Xyz Xi2 xy2 XYZ These theorems are harderto prove than you might think And are left as homework The axioms and theorems can be used to greatly simplify many expressions In particular the DNF s are usually not minimal Example the multiplexer The Boolean operators AND OR and NOT and others can also be written as a logic diagram or logic circuit Show them How many 2 input Boolean functions are there A 16 We can write diagrams forthem all Show this explain the exclusive or Using this idea we can draw a logic circuit for any Boolean expression Interesting fact The NAND gate alone is sufficient to build any circuits To see this first understand De Morgan s Laws XY X Y xY W 80 any sum xy can be replaced with x y Note also that NAND x x x 80 how do we do all of this in Haskell Introduce Bool type and give data decl for it Give data decl for a userdefined Bit type Work through and or hand etc functions Then de ne multiplexer Then de ne pairtype in Haskell Then de ne halfadder And a full adder Day 3 Jan 18 Friday instead of Monday because of MLK Combinational circuits have no loops and no state How do we get state Answer Loops But not all loops yield useful results Show NOT gate tied back on itself We can write an equation that describes this X X This equation has no solutions Q If we did this with a real logic gate what do you think will happen A Either oscillation or some value between 1 and Q lfwe wrote this X notB X in Haskell what would happen A Nonterminationll Let s look at something more useful Draw diagram oftwo NAND gates tied back on one another see Fig 382 Q What does this do Before answering let s write the equations that correspond to this Q RQ Q SQ If R and S are both 1 then there are two stable states Q could be 1 and Q 0 or vice versa More importantly we can force these two conditions by momentarily making R or 8 go to 0 This is called an R8 ipflop and is a simple kind of onebit memory Unfortunately unless we simulate continuous voltages and delays in wires etc we cannot simply write the above equations in Haskell and eXpect an answer In a computer it is more common that we use sequential circuits ie circuits that are clocked and typically have loops Draw diagram This begins with coming up with a clocked version ofthe RS ipflop which we can do like this Draw Fig 384 but put an inverter between R and S This is called D ip op ln Haskell we can take clocked ip ops and other kinds of clocked primitives as given ie we abstract away the details But we still need to represent clocks and in general signals that vary overtime We can do this using streams which are in nite lists in Haskell Give basic eXplanation of lists and streams and then go online to the le Circuitslhs Day 4 Jan 23 A more thorough tutorial on Haskell Haskell requires thinking differently elaborate X X1 in an imperative language is a command it says take the old value ofx and add 1 to it In contrast X X1 in Haskell is a de nition it says whatx is not howto compute it In this case X is de ned as a numberthat is the same as 1 plus that number ie it is the solution to the equation X X1 But in fact there is no solution to this equation and thus X is unde ned and Haskell will either not terminate or give you a runtime error if you try to execute it So how does one increment X Elaborate a introduce new de nition say y or b just use X1 where you need it Generally speaking no side effects The implications ofthis run deep For example there are no iteration loop constructs while until etc lnstead recursion is used Also IO needs to be done in a peculiar way more later Example Factorial write mathematical de nition first Data structures Haskell has a very general mechanism for de ning new data structures We saw one example Bit show again The builtin list data type has special syntax but is othenNise nothing special Elaborate in steps start with integer lists then say character lists Then point out that they have the same structure so let s use polymorphism to capture the structure example ofabstraction Then make connection to Haskell s lists including syntax X x etc Another builtin data structure is tuples lfthere were no special syntax we could do data Pair a b Pair a b ab data Triple a b c Triple a b c abc etc etc Discuss patternmatching XXs x Xy etc Now introduce type synonyms rst for String then for Sig ie Bit Suppose now we want to a ip every bit in a stream and b uppercase every character in a string Elaborate write the monomorphic functions to do this Now note the repeating pattern Elaborate distinguish repeating stuff from changing stuff introduce variables to handle the changing stuff Then develop code for the map function Point out the use of polymorphism and higherorder functions Note In Circuits I de ned notS Sig gt Sig notS XXs notB X notS xs but this is more easily de ned as notS xs map notB xs Discuss the syntax and semantics oftypes talk about currying Then point out notS map notB As another example de ne lift2 from the Circuits module andS XXs yys andB X y andS xs ys orS XXs yys orB X y orS xs ys nandS XXs yys nandB X y nandS xs ys norS XXs yys norB X y norS xs ys Note repeating pattern let s capture it using higherorder functions and polymorphism lift2 I agtbgtc gt a gt b gt c lift2 op XXs yys op X y lift2 op xs ys ln Haskell this is actually called zipWith So now andS orS nandS norS xorS Sig gt Sig gt Sig andS lift2 andB orS lift2 orB nandS lift2 nandB norS lift2 norB In nite lists Go back to the equation X x1 Then write xs 1 xs Explain why these are different one has a solution the other doesn t Now de ne some useful functions on in nite lists head tail take drop repeat cycle Also note that all the Sig functions andS orS etc work perfectly well with in nite lists Q Can we use map with an in nite list A Sure Example take 20 map notB xs Day 5 Jan 28 Let s review our approach to studying computers from the ground up 0 We studied and noticed the equivalence between binary logic combinational digital circuits and Boolean Algebra We used Haskell functions to simulate them this is an abstraction We noticed that when feedback was added indeterminacy and inconsistency could arise but by avoiding inconsistency we could use the indeterminacy as a vehicle for memory or state 0 To model feedback circuit delays need to be taken into account Instead of doing that directly in Haskell we choose instead to de ne sequential clocked circuits using in nite Bit streams another abstraction c We need to study sequential circuits in more detail To help understand streams better let s look at another example the in nite Fibonacci stream from Chapter 14 in SOE Elaborate In the Circuits module we use infinite streams Sig Bit to simulate sequential circuits ie circuits that change overtime in particular simulating clocked circuits Recall that x notB x is not welldefined any more than x 1 x is Similarly xs notS xs is not welldefined there is no Sig Bit that satis es this equation On the other hand xs Zero notS xs is well de nedll Elaborate draw a stream diagram Note that it is equivalent to the clock value in Circuits Recall now the desired behavior of a D ip op When the clock goes high it grabs the data on the input which should appear on the output on the next step if the clock is low it retains the value that it last had To remove indeterminacy we also assume that the initial out is zero dff Sig gt Sig gt Sig dff dat clk let out Zero orS andS dat clk andS out notS clk in out Elaborate draw stream diagram work through example input This is the hardest de nition that you will have to understand If you can gure this out you are golden Note that a D ipflop only carries one bit of information We d like to remember more and thus we cascade them together to form registers Draw diagram ofa fourbit register Then write Haskell code gt type Sig4 Sig Sig Sig Sig gt reg4 Sig4 gt Sig gt Sig4 gt reg4 d3d2d1d0 clk gt dff d3 clk gt dff d2 clk gt dff d1 clk gt dff d0 clk Similarly we d like to de ne 4bit adders multiplexers and so forth What can we do with these larger units Here s one example a counter one4 7 l carry in zero add4 l l l clk reg4 l l l l V Elaborate Work through timing diagram Then see Haskell version in the Circuits module Also go over the BMquot Day 6 Jan 30 How does one do other things with numbers such as subtract multiply and divide To do subtraction we can use two scomplement arithmetic a number is represented in binary where the most signi cant bit determines whether the number is positive or negative A number is negated by taking the one s complement ie ipping all the bits and adding one For example assume 4bit numbers sign ie 5 bits 01111 31 01110 30 oooo1 1 00000 0 11111 1 the one s complement of 11 11 is 0000 and 00001 0001 11110 2 39139ooo1 31 10000 32 the weird number note that there is no 32 Note that the twocomplement of 0 is zero Q What is the two s complement of32 A 32ll Note that using a 5bit adder n n 0 as it should For example 00101 5 11011 5 00000 0 Soto compute a b just do a b in two scomplement arithmetic Give two examples one with positive result the other negative Q How do you compute the two s complement of a number A Compute the one s complement and add one Q How do you compute one s complement A Use inverters but ifone wants to do it selectively then use XOR gates Draw circuit diagram Note that using 8bit say building blocks means we have 7bit signed numbers And the carryin can be used to perform the negation What about multiplication We could do it sequentially as in the Circuits module but how about combinationally To do this we could simulate the standard way of doing longhand multiplication For example 110 6 101 5 110 1100 11110 30 Q How many bits does the result ofan nbit multiplication have A 2n Draw circuit diagram to mimic ab for 4 bit words 0 Need a 5bit 6bit and 7bit adder 0 Word a is gated by b0 b1 b2 and b3 at each stage 0 At rst stage b0 and b1 gate both inputs 0 At each stage a is shifted by adding a zero at LSB In practice even more sophisticated circuits are used to do all of this better even addition mention lookahead for carry and to do other operations such as division In a computer we sometimes want to add sometimes multiply and so on And we want to do so on different pieces of data For your homework you are required to design a circuit that takes a single instruction and does one of eight things with it Look at Assignment 2 online Ask if there are any questions in particular regarding Haskell Von Neumann Computers The von Neumann computer is an abstract version of the modernday digital computer Sometimes also called a Random Access Machine A more concrete but still fairly simple and abstract version ofthis is the SCRAM Simple but Complete Random Access Machine described in Ch 48 of the Omnibus Show overhead transparency of Fig 481 Time permitting explain concepts of microcode machine code assembler code and high level code Day 7 Feb 4 Amittai s Lecture From Amittai I went over problems 1 and 3 of HW2 and then went to Chapter 48 figuring that the review of Chapter 48 would be a useful way of covering the ideas in Problem 2 I also reviewed the differences between multiplexers demulitplexers encoders and decoders and why decoders are so important in building a SCRAM or a machine such as the one in Problem 2 since I had noticed some confusion among some students about that Also clarified the function of registers Day 8 Feb 6 Chapter 17 describes SCRAM from a more abstract point ofview namely from the point ofview of machine code This is yetanother abstraction you can forget about MBR and MAR etc and focus instead on just the memory the AC accumulator the PC program counter and the instructions Note Chapter 17 makes one other assumption namely that the memory is divided into two sections one for code and the other for data Ch 17 gives an example of a program for detecting duplicates in an array of numbers Your homework is to add together all the elements of an array Note 0 Any constants that you need even the integer 1 say must be loaded into a memory data location Any van39ablesthat you need also need a memory data location To do indexing you need to use indirection through a memory data location ie the index is itselfa variable give example 0 All conditional branches need to be translated into a test for zero in the accumulator ie use the JMZ instruction Ch 17 also gives the highlevel pseudocode for the removingduplicates algorithm Q How does one get from this code to RAL A Using a compiler In practice the situation is slightly more complex Draw diagram of Program in Highlevel Language gt Compiler gt Assembly Language Program gt Assembler gt Object Machine Code gt Linker gt Executable Binary Code gt Computer Note RAL is an example ofa Machine Language the concept ofan Assembly Language is only a slight elaboration of a Machine Language to include for example symbolic names for addresses Key concept The compiler assembler and linker are all examples of compilation or translation ofone language into another The final executable is then actually executed or in a technical sense interpreted by the computer But one could also use a virtual machine or interpreter to execute higherlevel code A virtual machine or interpreter is just another program but instead of translating its input program into some other program it actually executes it Examples 0 The RAL interpreterthat I provide for Assignment 3 o The JVM or Java Virtual Machine which is an example ofa bytecode interpreter The virtual machine for CIL Common Intermediate Language used in the NET framework into which C VB C and other languages are compiled One key advantage ofvirtual machines interpreters is that they are more secure You never want to download a exe le unless you know for sure that it is safe One can more easily prevent malicious activity with a virtual machine since the program does not have control over the raw machine Also programs are smaller can be shipped over the internet easily eg Java applets One key disadvantage is that they run slower Often by a factor of 10 or more To learn more about compilers and interpreters take CPSC 421 by the same name Point out some ofthe challenges in writing a good compiler Also CPSC 430 Formal Semantics takes a more abstract view of language interpretation For now we will look more closely at the RAL Interpreter Abstractly the state of the machine consists ofthe AC PC and data memory The program is xed 80 execution interpretation amounts to keeping track of this state one operation at a time Work through an example We can do this in Haskell quite straightfonNardly Study the RAL Interpreter on line Day9Feb11 We have in about three weeks covered the spectrum from digital logic to sequential circuits to random access machines to assembly language to high level languages Finite Automata FA Is there are more abstract notion of computation Perhaps the simplest is something called a nite automaton lntuitively a FA is a bunch of little circles that represent states and lines between the circles that represent transitions between states triggered by input symbols plus a single initital state and a set of nal states Formally an FA is a vetuple QZ6qoqf Elaborate Now note 1 A FA is said to accept a particular sequence of input symbols if it ends up in a nal state when started from the initial state othenNise it is rejected 2 The set ofall input sequences accepted by a FA is called the language accepted or recognized by the FA For an FA A this is written LA 3 LA may be infinite but we can often describe it in nite terms The key is the use of a repetition notation specifically 001 represents zero or more repetitions ofthe sequence 001 4 We also need alternation concatenation juxtaposition and the empty sequence 5 Can a FA recognize any language The answer is no The class of languages accepted by a FA is called Regular Languages 6 The grammar for a regular language is called a regular expression which for a binary alphabet is de ned as a O and 1 are RE s b lfa and B are RE s so is ab and ab c lfa is an RE so is a 7 Every RE can be recognized by a FA conversely every FA can be described as an RE Note the similarity of RE s to Boolean logic is this signi cant Work through some examples or RE s and the corresponding FA Q lfwe treat an FA as a black box and we know its input alphabet can we determine what language it recognizes Or equivalently can we determine its grammar or internal structure A No Elaborate via example However if we know how many states it has then the answer is yes See Chapter 14 but we will probably not cover this in detail Another interesting fact We can try to generalize FA s by allowing non deterministic transitions between states basically add outgoing arcs that have the same transition symbol But this does not help the class of languages recognized by nondeterministic FA s NFA s is the same as that of deterministic FA s DFA s Here is an example ofa language that cannot be recognized by a FA palin dromes wcenter mark Try writing a grammar for it or constructing a FA for it Q What is the problem here Hint Has to do with state A FA has a nite state thus the namell We can add output thus creating a Meay Machine Elaborate show transitions but that doesn t help We need unbounded memory at the abstract level this is done with a tape PushDown Automata PDA A PDA has a tape on which it can do one oftwo things 0 Advance the tape and write a symbol or o Erase the current symbol and move back a cell Elaborate show transitions as in Fig 73 Give example palindromes wcenter marker PDA s are more powerful than FA s the class of languages that they except is called deterministic contextfree languages which is a superset of regular languages Furthermore nondeterminism buys us something with this class of automata nondeterministic PDA s recognize nondeterministic contextfree languages which is an even larger class of language What if we allow the tape to be read and written in arbitrary ways and directions Elaborate show the transitions as in Fig 77 Then we come up with two other classes of machines o If we put a linearfactor bound on the size of the tape then we have a linearbounded automaton which recognizes the class of contextsensitive languages o If we place no bound on the tape size then we have a Turing Machine which recognizes the class of recursivey enumerable languages Putting this all together yields what is known as the Chomsky Hierarchy Draw Table on page 43 Interestingly the Turing Machine is the most powerful machine possible equivalent in powerto a RAM and given its infinite tape more powerful than any computer in existence today Day10 Feb131 Chapter 23 is about generative grammars which are really no different from ordinary grammars but they are used differently A grammar describes a language one can then either design a recognizer or parser for that language or design a generatorthat generates sentences in that language A generative grammar is a fourtuple NTnP where o N is the set of nonterminal symbols 0 T is the set of terminal symbols 0 n is the initial symbol 0 P is a set ofproductions where each production is a pair XY often written X gt Y where X and Y are words over the alphabet N U T and X contains at least one nonterminal A Lindenmayer system or Lsystem is an example of a generative but is different in two ways 0 The sequence of sentences is as important as the individual sentences and o A new sentence is generated from the previous one by applying as many productions as possible on each step a kind of parallel production Lindenmayer was a biologist and mathematician and he used Lsystems to describe the growth of certain biological organisms such as plants and in particular algae The particular kind of Lsystem demonstrated in Chapter 23 has the following additional characteristics o It is contextfree the lefthand side of each production ie X above is a single nonterminal o No distinction is made between terminals and nonterminals with no loss of expressive power why o It is deterministic there is exactly one production corresponding to each symbol in the alphabet Go over Problem 2 in the homework Haskell hacking Go over PPT slides for Chapters 5 and 9 in SOE Day 11 Feb 18 Go over solution to Assignment 4 spend as much time on Haskell as needed Day 12 Feb 20 This week Chapter 31 in Omnibus Turing Machines At the top ofthe Chomsky Hierarchy is the Turing Machine the most powerful computer in the Universe Although woefully impractical the TM is the most common abstract machine used in theoretical computer science Invented by Alan Turing famous mathematician in the 1930 s mention Turing Award and the Turing Test In terms of language recognition a TM is capable of recognizing sentences generated by recursively enumerable languages We will not study that in detail rather we will consider a TM as a computer it takes as input some symbols on a tape and returns as output some presumably other symbols on a tape Draw diagram In that sense a TM is a partial function f 2 gt 2 where Z is the tape s alphabet A TM program is a set of 5tuples qsq s d where o q in Q is the currentstate o s in Z is the current symbol underthe head ofthe TM 0 q is the next state 0 s in Z is the next symbol to be written in place of s and o d is the direction to move the head left right or stop Q and Z are finite The program can be more conveniently written as a nitestate automaton where the labels on the arcs also convey the symbol to write and the direction to move Example Unary subtraction Example Unary multiplication as described in Omnibus 39 How small can the alphabet be and still have full power of TM 39 Two Perhaps not surprising How small can the set of states be and still have full power of TM 39 Two This is surprising Does adding more tapes make a TM more powerful No but it does make it more ef cient Does making the tape semiin nite make the TM less powerful No Pogtogtogtp The Omnibus has a proofthat an ntape machine is no more powerful than a onetape machine Day 13 Feb 251 0 Go over solutions to Assignment 5 0 Begin working through the handout on the lambda calculus o Announce Midterm exam will be on Wed May 5 Day 14 Feb 271 Finish going overthe handout on lambda calculus Day 15 March 3 Go over solution to Assignment 6 Chapter 59 ofthe Omnibus The Halting Problem The Uncomputable Q If I give a completely rigorous specification ofa problem whose answer is yes or no is it always possible to write a computer program to solve it The answer is no There are some really simple yesno problems called decision procedures that do not have a solution there exists no computer program no algorithm to solve them The simplest ofthese is called the Halting Problem Write a program that given a description ofanother program will answer yes if that program terminates and no ifit does not terminate There is no such program and it can be proven in the context of Lambda Calculus or Turing Machines or whatever Here is an informal proof based on functional programming Assume that we have a solution called halts to the Halting Problem so that haltsPD True ifrunning P on D halts and False ifrunning P on D loops Now construct two new programs selfHaltsP haltsPP funnyP if selfHaltsP then loop else halt Now consider funnyfunny if selfHaltsfunny then loop else halt if haltsfunnyfunny then loop else halt This is a contradiction Thus our original assumption the existence of halts must have been wrong Mention more formal proof based on Turing Machine in Ch 59 ofthe Omnibus Day 16 March 5 Midterm exam Proctored by Amittai Day 17 March 24 Welcome back Return and discuss midterm exam Algorithms and Complexity Read Chapters 1 11 15 35 and 40 in the Omnibus Chapter 7 of SOE I will supplement this with some notes on complexity Kinds of efficiency resource utilization Time Space Number of Processors Money l Number of messages ie communication costs etc Understandability maintainability ougnAooN x We will concentrate in the next few weeks on time and space efficiency more on the former Some problems are inherently dif cult Consider 1 Finding the shortest route that visits each of 300 cities called the traveling salesman problem Sort a 300element list called sorting Find the prime factors of a 300digit number called factoring Find a phone number in a phonebook of 300 billion names called lexicographic search hook Problems 1 and 3 above take millions of years to solve given current technology whereas problems 2 and 4 take only a few milliseconds Specifying Efficiency Just as we want to specify functional correctness we also want to specify ef ciency One way is just to say program p takes 234 seconds But this is too speci c in two ways 1 It doesn t take into account input size 2 It depends too much on the particular machine complier phase of the moon etc We can do better by 1 Parameterizing the complexity measure in terms of input size 2 Measuring things in terms of abstract steps 80 we can say for example that for an input of size N program P executes 19N27 steps However this still isn t abstract enough because usually we are only interested in orderof magnitude estimates of complexity The collapse of these complexity measures is usually achieved by something called the bigO notation which effectively removes constant factors and lowerorder terms For example 6N 196N27 1OON these are all linear in N ie ON 6N2 5N26N7 quadratic in N ie ON2 5N N132N123N11 proportional to N13 ieON13 5N 10NN1 exponential in N ie OaN log2Nlog10N logarithmic in N ie 0 log N Definition of BigO Notation Rn has order ofgrowth fn written Rn Ofn if there is some constant k for which Rn s kfn for a suf ciently large value of n But note 1 Complexity measures depend on assumptions about what is a valid step or operation For example if sort was a valid operation then sorting would take 01 operations 2 Constant factors can matter For example 105 N gt N2 for fairly large values of N 3 Complexity ofalgorithms is done abstractly complexity of programs is more concrete and depends on a careful understanding ofthe operational semantics ofour language which may be nontrivial Kinds of Complexity Measures 1 Worst case complexity given worstcase assumptions about the inputs 2 Average case complexity given averagecase assumptions about the inputs 3 Best case complexity given bestcase assumptions about the inputs Upper and Lower Bounds Sorting can be done in ON log N steps but can we do better A problem has a lower bound of Ln ifthere is no algorithm for solving the problem having lower complexity Absence of an algorithm requires a proof A problem has an upper bound of Un ifthere exists an algorithm for solving the problem with that complexity Existence ofan algorithm requires the algorithm So finding an algorithm establishes an upper bound But lower bounds amount to proving the absence of such an algorithm lfthe upper and lower bounds are equal then we have found an optimal solution The search for upper and lower bounds can be seen as approaching the optimal solution from above and below Problems for which lower bound upper bound are said to be closed OthenNise they are open leaving an algorithmic gap Open and closed thus have dual meanings Day 18 Mar 261 Review 0 Worst case average case best case 0 Big O notation 0 Upper and lower bounds 0 Optimal algorithm Point out that constants can matter Discuss bubblesort and a way to improve it by noting that at each step the list is partially sorted Doesn t improve complexity class but improves constant factor Detailed case study MinMax algorithm find the minimum and maximum elements in a list Iterative version in Haskell what are the types iterMinMax xzxs iMM x x xs iMM min max min max iMM min max xzxs l xltmin iMM x max xs iMM min max xzxs l xgtmax iMM min x xs Consider the number of comparisons Cn needed for iteerlianlax In the worst case each iteration requires 2 comparisons and there are n iterations Therefore Cn 2n Alternatively here is a divide and conquer solution in Haskell what is its type chinMax x xx chinMax xlx2 if xlltx2 then xlx2 else x2xl chinMax xs let minl maxl chinMax leftHalf xs min2 max2 chinMax righthalf xs in if minlltmin2 then minl else min2 if maxlgtmax2 then maxl else max2 What is the complexity of this We can write a set of recurrence equations that describe the number of comparisons 01 0 02 1 Cn 2 Cn2 2 which for simplicity assumes that n is a power of2 and thus is always divisible by 2 We can arrive at a closed form solution to these equations by first guessing that the solution has the form Cn knd Plugging this in we get Cnknd2Cn22 2kn2d2 kn2d2 ied2d2 sod2 Now plugging this into the equation for C2 C22kd2k21 So k32 Therefore a closedform solution to Cn is Cn 3n2 2 This is a modest improvement over the 2n comparisons given earlier Here is a list of common recurrence equations and their solutions C1 O Cn Cn2 1 Solution Cn log n C1 O Cn Cn1 1 Solution Cn n1 C1 O Cn 2 Cn2 1 Solution Cn n1 C1 O Cn 2 Cn2 n Solution Cn n Log n Day 19 Mar 31 Go over solutions to Assignment 7 NPcomplete problems Omnibus Chapters 34 41 54 Describe the SAT problem satis ability ofa Boolean product of sums both as an assignment problem and as a decision procedure Ask ifanyone can come up with an algorithm to solve the problem Mention that Chapter 31 discusses a recursive algorithm that is better than the obvious one However no one knows of any algorithm whose worstcase complexity is better than O2 In other words the best upper bound is O2quot Interestingly the best lower bound is polynomial So the algorithmic gap is huge Oddly perhaps note that a solution to SAT can be checked trivially in polynomial time just plug in the truth assignments and evaluate the term As another example considerthe problem of 3coloring a graph again two versions the assignment version and the decision version It has the same lower and upper bounds same algorithmic gap same simplicity of checking a solution This problem is abbreviated G3C Indeed there is a large class of problems for which 1 No known algorithm betterthan O2 No lower bound betterthan usually On Checking a solution is trivial On There is a huge search involved involving long sequence choices If we had a magic coin that knew the right move to make at every choice point we could solve these problems in polynomial time 91th This class of problems is known as NPC or NPComplete Other examples include path nding traveling salesman and bin packing placing a number of objects into say a knapsack so is to minimize the occupied space NP means nondeterministic polynomial which refers to a nondeterministic Turing Machine that can successfully guess at the right move at each step thus reducing an exponential search space to a polynomialtime search A problem that is NP complete is a member ofthe class of problems that are in NP and have the above properties and are all reducible to one another The completeness comes from the fact that a If we could solve any one of these problems in better than exponential time then we could solve all ofthem that way b An exponential time lower bound for one of them would apply to all In other words they are all both equally easy and equally hard This fact is established by a process called reduction Definition Problem P1 reduces to problem P2 if solving P2 also solves P1 Definition A polynomialtime reduction from P1 to P2 is a polynomialtime transformation ofan input to P1 to an input to P2 such that P2 s answer is correct for P1 More speci cally suppose AlgB solves B and fis a polynomialtime reduction from A to B Then the following algorithm solves A AlgA lnputX 1 Compute y fx 2 Use AlgB on input y 3 If AlgBY says yes then answer yes othenNise no Example suppose I want to crack an egg l have a way to crack a walnut perhaps with a sledge hammer so I use that method I have thus reduced the problem of cracking an egg to that of cracking a walnut And cracking a walnut is thus at least as hard as cracking an egg but of course it may be harder Now suppose we have a problem P we wish to show is in NPC All we need are two problems possibly the same P1 and P2 that are already known to be in NPC Then 1 Reduce P to P1 ie P can t be any harderthan P1 2 Reduce P2 to P ie P can t be any easier than P2 Then by transitivity ofreductions P is an element of NPC Only doing 1 above is fairly useless Note that all polynomial time algorithms can be reduced to an NPC problem Only doing 2 above establishes so called NP hardness which is usually the key point but without 1 we don t know ifa good solution to NPC will help us solve Pl Does P NP P problem with polynomial time solutions This is probably the best known open problem in Computer Science Most theoreticians believe that P does not equal NP but it hasn t been proven yet Day 20 Apr 2 Recall the G30 problem Review what a graph is There is an algorithm for converting any instance of G3C to an instance of SAT For each vertex vi in G output riyibi For each edge viv in G output rir yiy bibj This transformation has the property that solving the SAT problem will solve the G30 problem why Note 0 To say that no two adjacent vertices have the same color is to say rirj yiyj bib which by deMorgan s law isjust rirj YiYj bibj The constraint riyibi allows a vertex to be more than one color But if such an assignment satis es the Boolean expression that just means the vertex could be any ofthose colors Example consider singleton graph with one vertex and no edges This is an example ofa reduction from one problem to another and is a common technique used in theoretical computer science In case of NPcomplete problems they are all reducible in polynomial time to one another and therefore are equivalently hard or equivalently easy In general to show that a problem P is in NPC we must nd two problems P1 and P2 that are already known to be in NPC Then 1 Reduce P to P1 ie P can t be any harderthan P1 2 Reduce P2 to P ie P can t be any easier than P2 Note 0 P1 and P2 may be the same problem but often aren t 0 Establishing 1 shows that P is no harderthan any problem in NPC 0 Establishing 2 shows that P is at least as hard as any problem in NPC and is therefore NP hard Harder problems Some problems are provany exponential for example nding a winning strategy in many kinds of board games It s interesting to note that the solutions themselves are usually exponential eg an exponential number of moves in a board game Also there are problems that are even harder than exponential For example 0 Presburger arithmetic forall x exists yz st xzy exists w wwy This is doubly exponential 2 to the 2 to the n W818 a logic fortalking about sets of positive integers wexistential and universal quantification etc This logic has no solution having kfold exponential complexity for any k But it is still decidable This is called nonelementary Space complexity is also important In the end we have a bunch of complexity classes PTIME P solvable in polynomial time NPTIME NP solvable in nondeterministic polynomial time PSPACE solvable in polynomial space NPSPACE etc EXPTIME EXPSPACE Note that if something takes XSPACE then it must also take at least XTIME since just creating that much space takes an equivalent amount of time And thus we have a complexity hierarchy Show slide of picture of complexity hierarchy How do we deal with intractability 0 Could focus on doing well on typical problems rather than worst case 0 Could look for solutions that are near optimal perhaps within some tolerance For example the traveling salesman problem is easily solvable if we allow twice optimal 0 Could look for probabilistic solutions that give good perhaps even optimal results most of the time Day 21 April 7 Go over solution to Assignment 8 Arti cial Intelligence When a problem is intractable heuristics can be used to come up with approximate solutions These heuristics often come from our intuitions about how humans solve problems thus the phrase arti cial intelligence Example computer vision read Chapter 19 of Omnibus Brie y explain the techniques used in Chapter 19 to understand the three dimensional structure ofa 2D projection of a scene Day 22 April 9 Another example ofartificial intelligence Programs to play games Read Chapter 6 of the Omnibus Discuss the minimax algorithm draw a game tree on blackboard and work through the example from the Omnibus Then discuss alphabeta pruning using the same example Go over Assignment 9 explain the game of Macala Kalah and show the code provided to play the game Day 23 April 141 New topic Program Verification Read Chapter 10 in the Omnibus and Chapter 11 in SOE Go over PowerPoint slides of Chapter 11 in SOE Day 24 April 161 Go over solution to Assignment 9 Program veri cation continued Finish slides from Chapter 11 in SOE Day 25 April 211 Computer Music read Chapters 20 and 21 of SOE Go through PowerPoint slides for those chapters Day 26 April 231 Go over solution to Assignment 10 Explain how to run MDL programs from SOE code in GHCi Finish going over computer music slides for Chapter 21 Discuss nal exam CPSC 201 MidTerm Exam Spring 2008 Your Name Harm Haskell This is a closed book closed notes closed computer exam You have 75 minutes to complete your work You may write on the back ifyou need the room Point allocations are indicated and there are 100 points in all Plan your time accordingly Problem 1 16 points True or False T A Turing Machine can solve problems that my laptop cannot F A Turing Machine can solve problems that the Lambda Calculus cannot T The NOR gate is universal with it I can define any Boolean function T ln Boolean logic X yz xyxz T A D ipflop is like a onebit memory F A full adder adds two full 8bit bytes T The two s complement of O is 0 A combinational circuit is one made up of combinations of smaller circuits ie it is a modular design T RAL is an example ofa machine language sometimes also called an assembly language T FiniteState Automata and Regular Expressions are two sides of the same com F A Nondeterministic FiniteState Automaton is more powerful than a Deterministic FiniteState Automaton T A Pushdown Automaton PDA can be simulated by a Turing Machine T A PDA can recognize a palindrome but only if it has a center marker ie an odd number of symbols T Normalorder reduction in the Lambda Calculus terminates whenever applicativeorder reduction does F It is possible to write a program to determine if two Turing Machines compute the same value 39l39l Problem 2 12 points a Write a Boolean logic expression for the following truth table ABC ABC ABC ABC b Simplify the above expression as much as possible A B C BC AB Also ok ABC ABC AB 0 Draw a circuit diagram corresponding to this Boolean expression obvious should use correct symbols for inverter and and or gates ok to use more than two inputs but would prefer binary gates Problem 3 12 points Prove that the two s complement ofa number when added to the original number yields 0 Solution Suppose we have an nbit number b The 2 s complement is the 1 s complement 1 If we represent the 1 s complement as b then we are interested in computing b1 b But since addition is commutative and associative we can rewrite this as b b 1 Now note that b b 2n 1 Adding one to that yields 2 But that number requires n1 bits where the leftmost bit is 1 and the others are 0 Thus ifwe throw away the left most bit we get 0 QED Problem 4 12 points Draw a combinational circuit diagram for a 4bit multiplier e given two 4bit numbers a and b the circuit should compute the 8bit product ab You may assume that as building blocks you have adders of whatever width that you like 4bit 5bit 6bit whatever Problem 5 12 points Write grammars that describes the following o Signed decimal numbers ofthe form 35 42 314159 1062 27 1000 etc Leading zeros are Ok too 0 Properly nested balanced parentheses For example these should be accepted etc whereas these should not 0 0 0 etC Note A regular expression can be used to de ne the rst whereas a contextfree grammar will be needed to de ne the second Solutions Forthe numbers let num be the regular expression 01 2345789 Then the regular expression result that we want is nu quotll In For the parentheses we need a contextfree production p n p nquot Problem 6 12 points Consider a Turing Machine with alphabet 1 234a that starts with a tape containing one to four consecutive a s on it with the head position initially on the leftmost a Write a TM program that counts the number of a s on the tape and writes the total just to the right ofthe sequence of a s Solution Start in state 0 The symbol b means a blank Current state current symbol new symbol new state head direction Oaa1R 1b19Hw 1aa2R 2b29H 2aa3R 3b39H 3aa4R 4b49H 4a49Hmt Of course a visual diagram is also an Ok solution Problem 7 12 points Suppose that we generalize pairs in the Lambda Calculus to triples by de ning tripe Aa Ab Ac At t a b c Define selectors rst second and third in the Lambda Calculus such that rst triple X y z 9 X second triple X y z 9 y third triple X y z 9 2 Solutions rst At t Aa Ab Ac a second At t Aa Ab Ac b third At t Aa Ab Ac c Problem 8 12 points Define Haskell functions as follows A function fromNum that takes an integer argument n and returns an in nite list of successive numbers starting at n For example fromNum 5 9 567 A function twice that takes a functional argument fand a value X and applies fto X twice For example twice 1 5 9 7 Solutions fromNum n n fromNum n1 twice fX ffX
Are you sure you want to buy this material for
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'