CS1JC3 F21 Midterm Questions PDF

1JC3 FINAL EXAM QUESTION PREP DOCUMENT LAYOUT Concept Questions Haskell/Coding Questions Code/resources to solve questions Previous Year Midterm Questions TIPS: Notice how Dr. Farmer answers most questions with little detail in some cases, so don’t worry about spending time duri...

1JC3 FINAL EXAM QUESTION PREP DOCUMENT LAYOUT Concept Questions Haskell/Coding Questions Code/resources to solve questions Previous Year Midterm Questions TIPS: Notice how Dr. Farmer answers most questions with little detail in some cases, so don’t worry about spending time during the exam explaining your answer. Just answer the question. (I.E there is no point using ‘because’) Even if questions aren’t exact, look for patterns. FOR EXAMPLE: What is the type of the Haskell function below? The answer is in the form of type -> type -> type DON'T EXPECT ALL ANSWERS TO BE HERE. Thanks to everyone who contributed and good luck! - Sohaib If by chance some of these questions pop up in the exam… you all got a 95%+ average in hs… use your common sense, paraphrase, and don’t copy word for word (if possible ofc). CONCEPT QUESTIONS QUESTION ANSWER In Haskell, what is the main difference between a tuple and a The members of a tuple may have different types, while the list? members of a list must have the same type. What is the type of the Haskell function below? Bool -> Bool -> Bool -> Bool ifThenElse a b c = if a then b || c else b && c Why is Gottfried Leibniz considered a great computer engineer? Leibniz invented the Staffelwalze, the first machine that could do addition, subtraction, multiplication, and division. With respect to programming languages, what advantage does Interpretation is better than compilation for developing and interpretation have over compilation? debugging code. What is the difference between a boolean expression and a A boolean expression is an expression that denotes a boolean predicate? value, while a predicate is a function whose output is a boolean value. What is the name of the model of computation developed by Combinatory logic. Haskell Curry? What is the calculus ratiocinator? A computing device imagined by Leibniz for determining the truth or falsity or statements written in characteristica universalis. What did Alan Turing discover about the limits of computing? That there are decision problems that cannot be solved by Turing machines. Give an example of a boolean function that cannot be defined "not" (negation). using just the boolean functions "and" and "or"? Why is the code x == y not effective for testing whether two The values of floating points numbers are approximations, so numbers x and y are the same number when they are represented two equal numbers may be approximated by slightly different as floating point numbers? floating points numbers. Suppose that person A is sending a document to person B. A encrypts the document using A's private key. Person B would like person A to digitally sign the document using public key encryption. How does person A do this? There is a structural induction principle corresponding to every To prove that a property holds for all members of the algebraic algebraic type. What is this induction principle used for? type. What is the purpose of the domain name system (DNS)? The domain name system is for naming individual hosts and collection of hosts in a hierarchical fashion. For what kind of users are graphical user interfaces usually best Novice users. suited? GUIs are best for casual/non-technical users that do not need much access to different functionalities of the programs. This is because GUIs are easy and intuitive to use and are not as powerful as command lines interfaces. Suppose that person A is sending a secret key to person B that B decrypts the secret key using B's private key. person A has encrypted using public key encryption. How does person B decrypt the secret key? The Internet has the structure of a bipartite graph. What are the The nodes are the hosts and physical networks and the edges are nodes and edges in the graph? the network interfaces between the hosts and physical networks. Why is it easier to test a function without side effects than a The environment in which a function is executed must be treated function with side effects? as an input when the function has side effects, but the environment can be ignored when the function has no side effects. In the two's complement representation of the integers using 8 127 bits, what is the value of -2 - 127? Who showed for the first time that there are undecidable Alonzo Church. decision problems? What property must a list have in order to use binary search on The list must be sorted. it? In Haskell, what is the main difference between the Float and Float represents a finite number of rational numbers, while Rational types? Rational represents all rational numbers. Give an example of a number x with 0.6 < x < 0.7 that is 0.625 represented exactly as a member of type Float? What did Alan Turing discover about the limits of computing? That there are decision problems that cannot be solved by Turing machines. What is the type of 2 * 3 in Haskell? Num a => a Who showed that the truth values and the operations on them George Boole like "or" and "and" have an algebra structure like numbers do? What value is returned in Haskell when underflow occurs during -0.0 or 0.0. the evaluation of an expression of type Float or Double? What are the major kinds of thinking included in computational Mathematical, engineering, scientific, and artistic thinking. thinking? Who invented regular expressions? Stephen Kleene Why are the positive rational numbers with the usual order < not There are infinite decreasing sequences of positive rational Noetherian? numbers such as 1/2, 1/3, 1/4,.... What is the name of the model of computation developed by Turing machines Alan Turing? Where did the word "algebra" come from? The word "algebra" comes from the word "al-jabr" in the name of Mohammad Al-Khwarizmi's book on solving linear and quadratic equations. What is a type error? A type error is a mismatch between the expected type of an input to a function and the actual type of the input. Why is the Haskell programming language called "Haskell"? The Haskell programming language is named after the famous American logician Haskell Curry. How could the Ariane 5 disaster have been avoided? The Ariane 5 disaster could have been avoided by verifying whether the Ariane 4 software works correctly for Ariane 5. Fill in the blank. The integrity of a file can be protected by write controlling ________ access to the file. Who first showed that Gottfried Leibniz' dream about computing Alonzo Church. is an impossibility? What is the difference between the theoretical and practical The theoretical limits of computing are the limits of computing limits of computing? with unlimited temporal and spatial resources, while the practical limits of computing are the limits of computing with a fixed amount of time and space. There is a structural induction principle corresponding to every To prove that a property holds for all members of the algebraic algebraic type. What is this induction principle used for? type. How could the Patriot Missile disaster have been avoided? The Patriot Missile disaster could have been avoided by choosing the unit of time to be a value that is exactly represented as a binary floating-point number. What kind of file is a Unix root account not allowed to access? The root account can access all files. Why is code for a conventional encryption algorithm often made So the public can judge the strength of the algorithm by its own available to the public? analysis. Which of the three kinds of induction is strong induction? Strong induction is of ordinal induction principle. At what TCP/IP layer is the Internet a virtual connectionless Internet layer network? How does the copy, modify, compare, and generalize (CMCG) The short-term cost is that it produces a more general solution method trade short-term cost for long-term gain? than is needed, while the long-term gain is that the more general solution can solve more problems in future than the original  solution. What is the main service that a domain name server provides? It maps a given DNS name to the collection of IP addresses that the name denotes. Why are the integers with the usual order < not Noetherian? There are infinite decreasing sequences of integers such as -1, -2, -3,.... How many values will an algebraic type have if it is recursive? Infinitely many values. Why can QuickCheck in general not be used to prove that a QuickCheck only checks that the property holds for a random function satisfies a given property? selection of inputs. This is not a proof since not all inputs are checked. In what sense is weak induction weaker than strong induction? Weak induction provides a weaker induction hypothesis than strong induction. For what kind of users are command-line interfaces usually best Expert users. suited? What is a literal? An expression whose syntactic form literally indicates its value. What kind of address is used to route UDP segments? UDP protocol ports What is a client in the client-server model? A client is a process that requests services from a server process. How many outputs can a function have for a given input? At most one. In Haskell, how many values of type Int represent the number 0? 1. To show that a recursive definition of a function makes sense, Natural numbers or any other values that are well-ordered. what kind of values need to be assigned to the inputs of the function? Why is Emmy Noether noteworthy? Emmy Noether is a woman who by luck and determination  became a superb mathematician when women were considered not capable of being mathematicians. What is an example of a law of multiplication that is not obeyed Associativity law. by floating point arithmetic? Give an example of a boolean function that can be used to define “nand” or “nor” every boolean function What is the name of the model of computation developed by The name of the model of computation developed by Alonzo Alonzo Church? Church is called lambda calculus, which is based on function application and abstraction. What is the type of 2 * 3 in Haskell? Num a => a. What is an example of a law of addition that is not obeyed by An example of this is that multiplication is not associative for floating point arithmetic? floating point arithmetic. (Associative law) What was the Staffelwalze (Stepped Reckoner) and why is it It was a machine invented by Leibniz for doing addition, noteworthy? subtraction, multiplication, and division. It was the first device that could perform all four of these basic arithmetic operations. What value is returned in Haskell when overflow occurs during -Infinity or Infinity. the evaluation of an expression of type Float or Double? Give an example of a number x with 1.3 < x < 1.4 that is 1.375. represented exactly as a member of type Float? What is underflow in floating point arithmetic? Underflow is when the result of an expression is -0.0 or 0.0 which occurs when a value is too close to zero to be represented in a floating point representation.  Underflow in floating point arithmetic occurs when the output of an operation on floating point numbers is too small of a positive number to be represented as a floating point number or too large of a negative number to be represented as a negative floating point number What is the characteristica universalis? A universal language for expressing scientific ideas that Leibniz spent his life working on. Why is Gottfried Leibniz a great computer scientist? Leibniz had the creativity and courage to hypothesize that, with the right language and the right computing device, any problem could be solved by computation. What is the difference between a procedural program and a A procedural program is a sequence of commands (imperative declarative program? statements) that say how to do the computation, while a declarative program is a sequence of definitions and goals (declarative statements) that say what the computation should do. What is overflow in floating point arithmetic? Overflow in floating point arithmetic occurs when the output of an operation on floating point numbers is too small or too large to be represented as a floating point number. Why is there no QuickCheck function in an imperative language QuickCheck only works when functions are guaranteed to be like Java? side-effect free. If the language is imperative, this means that functions are able to alter or modify the state of the data, making it hard to implement testing functions (since the function might change the stats of the data that is used by other helper functions, ruining the test). What is the hexadecimal number FD8 in decimal? 4056 What is the decimal number 888 in hexadecimal? 378 Where did the word "algorithm" come from? The word "algorithm" comes from "Algoritmi", the Latin name for Mohammad Al-Khwarizmi. In what kind of packet does a UDP datagram travel when An IP datagram crossing the Internet? Why is it better in Haskell to use a newtype instead of a product The newtype is more efficient at run time than the product type. type with a single constructor of the form C t? What kind of address is used to route network frames? The physical address is used to route network frames Give an example of a monoid that is not commutative. (S,e,++) where S is a set of strings over an alphabet, e is the empty string, and ++ is the concatenation operation. Why are both conventional encryption and public key encryption Conventional encryption is needed to encrypt the documents, needed to safely send large secret documents over the Internet? and public key encryption is needed to encrypt the secret key for the convention encryption algorithm so that it can be sent over the Internet. What kind of address is used to route TCP segments? TCP protocol ports. What kind of address is used to route UDP segments? UDP protocol ports. Fill in the blank. The confidentiality of a file can be protected Read by controlling ________ access to the file. What kind of encryption does the SSH protocol use? Both conventional and public key encryption. What is type checking? Type checking determines if there are any type errors (i.e., type mismatches) in computer code. Why is the Turing test called the "imitation game"? The purpose of the test is to see if a software system can imitate a human so well that an observer cannot tell if the system is a human or not. What is a server in the client-server model? A server is a process that provides servers over a network to clients. It listens at a reserved TCP or UDP port to allow network communication with clients. A server may consist of a group of processes or threads. What is a truth table? A truth table is a tabular presentation of the input-output relation of a boolean function. Who showed that the truth values and the operations on them George Boole. like "or" and "and" have an algebra structure like numbers do? Who developed algorithms for performing arithmetic using the Mohammad Al-Khwarizmi. Hindu-Arabic system? Why are the methods of a Haskell type class a little language? A solution to a problem written using the methods of a type class can be applied to all the instances of the type class. What is the kernel of an operating system? It is a program that controls the resources of a computer and enables application programs to be executed on the computer. What is the floating point value "NaN" used for? This value is returned when an operation on floating point numbers is undefined. What method of proof is usually used to prove properties about a Mathematical induction. recursively defined function? How are programs executed in parallel on a computer with only Each program running on the computer is given in turn control one CPU? of the CPU for a short period of time. What kind of encryption is used to encrypt passwords stored on One-way encryption. a computer? In what kind of packet does an IP datagram travel when crossing A frame for the network. a physical network? In what kind of packet does a TCP segment travel when crossing An IP datagram. the Internet? What is the type of 2 * 3 in Haskell? Num a => a. Give an example of a number x with 0.6 < x < 0.7 that is 0.625. represented exactly as a member of type Float? Why are the positive rational numbers with the usual order < not There are infinite decreasing sequences of positive rational Noetherian? numbers such as 1/2, 1/3, 1/4,.... Give an example of a boolean function that cannot be defined “not” negation using just the boolean functions "and" and "or"? How many outputs can a function have for a given input? At most one What does it mean for a function to be side-effect free? A function is side-effect free if its execution does not modify the state of the environment in which it is executed. What does a data type denote? A data type is a syntactic entity that denotes a collection of values of similar form. eg: Bool that denotes the values True and False What kind of encryption is used to encrypt passwords stored on One-way encryption. a computer? Suppose that person A is sending a secret key to person B. A encrypts the secret key using B's public key. Person B would like person A to encrypt the secret key using public key encryption. How does person A do this? At what TCP/IP layer is the Internet a virtual connectionless Internet layer. network? What is a little language as a problem solving technique? A little language is a language for solving a family of related problems. Which kind of Haskell algebraic type has the same structure as a A product type. tuple type? Which kind of Haskell algebraic type is the Maybe type? A sum type. What is the type of 2/3 in Haskell? Fractional a => a What is the type of 2 * 3 in Haskell? Num a => a. What value is returned in Haskell when overflow occurs during -Infinity or Infinity. the evaluation of an expression of type Float or Double? Where did the word "algebra" come from? The word "algebra" comes from the word "al-jabr" in the name of Mohammad Al-Khwarizmi's book on solving linear and quadratic equations. What is the decimal number 888 in binary? 1101111000. What is the name of the model of computation developed by Combinatory logic. Haskell Curry? Give an example of a boolean function that can be used to define "nand" or "nor". every boolean function? What does a data type denote? It denotes a collection of values of similar form. What is a system program? It is an application program that supports the use of a computer and is part of the operating system. Why is it better in Haskell to use a newtype instead of a product The newtype is more efficient at run time than the product type. type with a single constructor of the form C t? How many values will an algebraic type have if it is not A finite or infinite number of values. recursive? What does it mean to say that a Haskell algebraic data type has Every member of the algebraic type can be constructed using the "no confusion"? constructors of the type in exactly one way. What was Gottfried Leibniz' dream about computation? Any scientific question could be solved using the characteristica universalis to express the question and the calculus ratiocinator to compute an answer to the question. What did Alonzo Church discover about the limits of Church discovered that there are decision problems that cannot computing? be solved by algorithms. What is the difference between a value and an expression? A value is a piece of data that is stored and manipulated by a computer program, while an expression is a syntactic entity that denotes a value. What is lambda notation used for? Lambda notation is used to specify a function without giving it a name. What number in base 10 is represented by the value of type Float 10 whose sign bit is 0, mantissa is 1.01000000000000000000000, and exponent is equal to 3? What is the name of the model of computation developed by Combinatory logic Haskell Curry? How could the Patriot Missile disaster have been avoided? The Patriot Missile disaster could have been avoided by choosing the unit of time to be a value that is exactly represented as a binary floating-point number. What is the binary number 111111011000 In hexadecimal? FD8. What is the difference between compilation and interpretation? Compilation translates a program to machine code that is then executed. Interpretation directly executes a program without translating it to machine code. What is a decision problem? It is a problem that, for each input, requires a yes-or-no answer. At what TCP/IP layer does the HTTP protocol operate? Application layer. What is the purpose of the domain name system (DNS)? The domain name system is for naming individual hosts and collection of hosts in a hierarchical fashion. Which kind of Haskell algebraic type is the Maybe type? A sum type. Why is the code x == y not effective for testing whether two The values of floating points numbers are approximations, so numbers x and y are the same number when they are represented two equal numbers may be approximated by slightly different as floating point numbers? floating points numbers. What does it mean to say that a Haskell algebraic data type has Every member of the algebraic type can be constructed using the "no junk"? constructors of the type. What is the usual type of a sorting algorithm in Haskell? Ord a => [a] -> [a]. Why are there no loops in Haskell? Loops can be efficiently simulated in Haskell by recursive functions. At what TCP/IP layer is the Internet a virtual Transport layer. connection-oriented network? Why did the U.S. Department of Defense fund the research that It wanted to improve data communication between its military led to the creation of the Internet? bases. What is an identifier? An atomic expression that serves as a name for a variable or constant. Why is recursion not as space efficient as iteration in many In many program languages, recursive functions do not execute programming languages? in constant space as loops do. In Haskell, how many values of type Double represent the 2 values of type Double number 0? Why is the code x== y not effective for testing whether two The values of floating point numbers are approximations so two numbers x and y are the same number when they are represented equal numbers may be approximated by slightly different as floating point numbers floating point numbers. What did Alonzo Church discover about the limits of Church discovered that there are decision problems that cannot computing? be solved by algorithms. What is the difference between a value and an expression? A value is a piece of data that is stored and manipulated by a computer program, while an expression is a syntactic entity that denotes a value. What is lambda notation used for? Lambda notation is used to specify a function without giving it a name. In Haskell, what is the main difference between the Float and Float represents a finite number of rational numbers, while Rational types? Rational represents all rational numbers. Where did the word "algebra" come from? The work "algebra" comes from the word "al-jabr" in the name of Mohammad Al-Khwarizmi's book on solving linear and quadratic equations. What does it mean to say that a function definition is tail A function definition is tail recursive if the value of each recursive? recursive call is directly returned to the calling function without any additional computation being performed. How many outputs can a function have for a given input? At most one. What is the difference between a boolean function and a The inputs and output of a boolean function are boolean values, predicate? while the output of a predicate is a boolean value, but the inputs  can be any type of value. Suppose that person A is sending a document to person B. A encrypts the document using A's private key. Person B would like person A to digitally sign the document using public key encryption. How does person A do this? What is the main advantage of conventional encryption over Conventional encryption is more efficient than public key public key encryption? encryption. What does QuickCheck check? QuickCheck checks whether or not a property holds for a finite number of randomly generated inputs. In the two’s complement representation of the integers using 8 125 bits, what is the value of 3 * 127 HASKELL/CODING QUESTIONS Fill in your previous Haskell Questions here QUESTION ANSWER A prime number is a natural number greater than 1 whose only [1,n] factors are 1 and itself. Consider the Haskell code factors n = [m | m [a] -> [a] amazon 0 x = x amazon n [] = [] amazon n x = amazon (n - 1) ( tail x) What does amazon n x return when n is nonnegative and x is a list? Consider the following Haskell code: False. arno :: Integer -> Bool arno 0 = True arno n = rhone (abs n - 1) rhone :: Integer -> Bool rhone 0 = False rhone n = arno (abs n - 1) What is the value of arno 37? Consider the following code where Tree is an algebraic type of max (maxLabel t) (maxLabel (Branches ts x)). multiple branching trees whose nodes are labeled by integers. ` data Tree = Branches [Tree] Integer maxLabel :: Tree -> Integer maxLabel (Branches [] x) = x maxLabel (Branches (t:ts) x) = E Consider the following Haskell code? 15 grendel :: Integer -> Integer -> Integer grendel m n | m == n = m | m > n = grendel (m - n) n | m < n = grendel m (n - m) What is grendel 150 315? Consider the following Haskell code: ConsA True (ConsB "a" Empty). data Sample a b = Empty | ConsA a (Sample a b) | ConsB b (Sample a b) deriving (Show,Eq) Give an example of an expression of type Sample Bool String that contains all three constructors of Sample. Consider the following Haskell code: It contains the length of each line of text in the file named x. congo x = do y Euclid -> Euclid data Euclid = Eudoxus Integer | Apollonius Rational Euclid What is the type of Apollonius? Consider the following Haskell code where E is an unspecified danube (m - 1) (a + b) a. expression: missouri :: Integer -> Maybe Integer missouri n = let danube :: Integer -> Integer -> Integer -> Maybe Integer danube m a b | m < 0 = Nothing | m == 0 = Just b |m>0=E in danube n 1 0 What should E be so that missouri n computes the n-th Fibonacci number? Consider the following Haskell code: IO Double. orinoco = do x [Integer] -> Integer beowulf x ys = unferth (beowulfAux x ys [0 ,0 ,0]) beowulfAux :: Integer -> [Integer] -> [Integer] -> [Integer] beowulfAux x [] [a,b,c] = [a,b,c] beowulfAux x (y:ys) [a,b,c] | y < x = beowulfAux x ys [a + 1,b,c] | y == x = beowulfAux x ys [a,b + 1,c] | y > x = beowulfAux x ys [a,b,c + 1] What is the value of beowulf 5 [8,3,4,10,11,7,2,2]? Consider the following Haskell code where A and B are A must be " " and B must be (++). unspecified expressions: big m n f |m>n =A | m Integer unferth [a,b,c] = 2 * a * (b + c) beowulf :: Integer -> [Integer] -> Integer beowulf x ys = unferth (beowulfAux x ys [0 ,0 ,0]) beowulfAux :: Integer -> [Integer] -> [Integer] -> [Integer] beowulfAux x [] [a,b,c] = [a,b,c] beowulfAux x (y:ys) [a,b,c] | y < x = beowulfAux x ys [a + 1,b,c] | y == x = beowulfAux x ys [a,b + 1,c] | y > x = beowulfAux x ys [a,b,c + 1] What is the value of beowulf 5 [8,3,4,10,11,7,2,2]? Consider the following Haskell code: It does not have a value. g :: Rational -> Rational -> Rational g x y = x/y What is the value of g x 0? Consider the following Haskell code where A is an unspecified (x - 1). expression: breca x | x == 100 = 0 | otherwise = breca A The application breca 1000 terminates if A is ________. Which of the following Haskell functions are tail recursive? Only g is tail recursive. fx | x == 0 = 1 | x > 0 = f (x - 1) * x gxy | x == 0 = y | x > 0 = g (x - 1) (y * x) Write a case statement expression that is equivalent to the case a of conditional expression True -> b False -> c if a then b else c. Consider the following Haskell code: [2,1,0,3,2,1,0,4,3,2,1,0]. wiglaf :: Integer -> [Integer] wiglaf 0 = wiglaf x = [x] ++ wiglaf (x - 1) hygd :: Integer -> Integer -> (Integer -> [Integer]) -> [Integer] hygd m n f | m > n = [] | m IO () reverse order. styx x = do y String volga a = let b = lines a c = map reverse b d = unlines c in d If x is the name of a text file, what does the file "out.txt" contain after styx x is evaluated? Consider the following Haskell code: [4,7]. hrothgar :: [Integer] -> (Integer -> Bool) -> [Integer] hrothgar xs p = hygelac xs [] p hygelac :: [Integer] -> [Integer] -> (Integer -> Bool) -> [Integer] hygelac [] ys p = ys hygelac (x:xs) ys p |px = hygelac xs (ys ++ [x]) p | otherwise = hygelac xs ys p What is the value of the expression hrothgar [3,2,5,2,4,7,6] (\x -> x `mod` 3 == 1)? Consider the following Haskell code: It does not have a value. g :: Rational -> Rational -> Rational g x y = x/y What is the value of g x 0? Consider the following Haskell code: -Infinity, NaN, or Infinity. f :: Float -> Float -> Float f x y = x/y If z is an expression of type Float, what is the value of f z 0? Consider the following Haskell code: [4,7]. hrothgar :: [Integer] -> (Integer -> Bool) -> [Integer] hrothgar xs p = hygelac xs [] p hygelac :: [Integer] -> [Integer] -> (Integer -> Bool) -> [Integer] hygelac [] ys p = ys hygelac (x:xs) ys p |px = hygelac xs (ys ++ [x]) p | otherwise = hygelac xs ys p What is the value of the expression hrothgar [3,2,5,2,4,7,6] (\x -> x `mod` 3 == 1)? Consider the following code where Tree is an algebraic type of max (maxLabel t) (maxLabel (Branches ts x)). multiple branching trees whose nodes are labeled by integers. data Tree = Branches [Tree] Integer maxLabel :: Tree -> Integer maxLabel (Branches [] x) = x maxLabel (Branches (t:ts) x) = E What expression E will make the function maxLabel returns the maximum label in a member of type Tree? A palindrome is a string that reads the same both from left to E1 is head ds and E2 is False. right and right to left. For example, "eye" and "racecar" are palindromes. Consider the following Haskell code where E1 and E2 are an unspecified expressions. isPalindrome :: String -> Bool isPalindrome [] = True isPalindrome [c] = True isPalindrome (c:cs) = let ds = reverse cs in if c == E1 then isPalindrome (tail ds) else E2 What should E1 and E2 be so that isPalindrome determines whether a given string is a palindrome? A palindrome is a string that reads the same both from left to E1 is reverse cs and E2 is (tail ds). right and right to left. For example, "eye" and "racecar" are palindromes. Consider the following Haskell code where E1 and E2 are an unspecified expressions. isPalindrome :: String -> Bool isPalindrome [] = True isPalindrome [c] = True isPalindrome (c:cs) = let ds = E1 in if c == head ds then isPalindrome E2 else False What should E1 and E2 be so that isPalindrome determines whether a given string is a palindrome? Consider the following code where Tree is an algebraic type of sumTree t + sumTree (Branches ts x). multiple branching trees whose nodes are labeled by integers. data Tree = Branches [Tree] Integer sumTree :: Tree -> Integer sumTree (Branches [] x) = x sumTree (Branches (t:ts) x) = E What expression E will make the function sumTree return the sum of the integer labels in a member of type Tree? What value is returned in Haskell when underflow occurs during -0.0 or 0.0. the evaluation of an expression of type Float or Double? In Haskell, -0.0 or 0.0 would be returned if underflow occurred during the evaluation of an expression of type Float or Double. Write a guarded function definition that is equivalent to the fabc function definition |a =b | otherwise = c f a b c = if a then b else c. Consider the following Haskell code: 32. unferth :: [Integer] -> Integer unferth [a,b,c] = 2 * a * (b + c) beowulf :: Integer -> [Integer] -> Integer beowulf x ys = unferth (beowulfAux x ys [0 ,0 ,0]) beowulfAux :: Integer -> [Integer] -> [Integer] -> [Integer] beowulfAux x [] [a,b,c] = [a,b,c]  beowulfAux x (y:ys) [a,b,c] |yx =beowulfAuxxys[a,b,c+1] What is the value of beowulf 5 [8,3,4,10,11,7,2,2]? CODE TO HELP SOLVE QUESTIONS If you find that there are some questions that can be generalized into an algorithm to solve, feel free to add it here. In the two’s complement representation of the integers using 8 bits, what is the value of 3 * 127? def underOverflowResult (n, availableBits): availableBits = 1 0 = skunk (a - 1) c ( b + c ) The fundamental question of computational thinking is False. concerned with the time and space efficiency of computer programs. Is this statement true or false? A shell script is a program that executes commands for a __ Command-line interface - A shell script is a program that executes commands for a command-line interface to an operating system called a shell. For all values a, b, c in Haskell, if (a, b, c) is a tuple, then [a, b, False. c] is a list. Is this statement true or false? Modular arithmetic is used in computers to add and multiply True. machine integers. Is this statement true or false? Who invented the first mechanical calculator that could do Gottfried Leibniz. addition, subtraction, multiplication, and division? A pure functional program has No imperative statements, No loops, No side effects. Consider the following Haskell code: [2,2,4,6]. mink :: [ Integer ] -> ( Integer -> Bool ) -> [ Integer ] mink xs p = weasel xs [] p weasel :: [ Integer ] -> [ Integer ] -> ( Integer -> Bool ) -> [ Integer ] weasel [] ys p = ys weasel ( x : xs ) ys p | p x = weasel xs ( ys ++ [ x ]) p | otherwise = weasel xs ys p What is the value of the expression mink [3,2,5,2,4,7,6] (\x -> x ‘mod‘ 2 == 0) ? Consider the following Haskell code: 0.4000001. marten :: Float -> [ Float ] -> Float -> Float marten x [] z = z marten x ( y: ys ) z = let w = abs ( x - y ) in if abs w < z then marten x ys w else marten x ys z What is the value of the Haskell expression marten 3.2 [2.1, -3.3, 4.2, 3.8, 10.5, 2.8] 100 ? The technology underlying the Internet was developed by The U.S. Department of Defense - The research was funded by researchers funded by the U.S. Department of Defense’s ARPA agency. Which of the following is a type of curryed functions?. Integer -> Bool -> Bool What is the hexadecimal number 3ABC in binary? 11101010111100. Let a,b,c be Haskell variables of type Bool and let fox be the boolean expression (not a && not (b || c)) || (a || not (not b && c)) Which of the following truth tables specifies the semantics of fox? The IP protocol routes IP datagrams using The destination IP address - Addressing is done in the IP protocol using IP addresses that are assigned to network interfaces. A web browser includes a(n) ___ HTTP client - A browser includes an HTTP client as well as possibly other clients. In the two’s complement representation of the integers using 8 -2 bits, what number in base 10 does 11111110 represent? Which of the following statements about floating point numbers Which of the following statements about floating point numbers is incorrect? is incorrect? What number in base 10 is represented by the value of type Float 9 whose sign bit is 0, mantissa is 1.00100000000000000000000, and exponent is equal to 3? What is the decimal number 638 in binary? 1001111110. What is the usual type of a sorting algorithm in Haskell? Ord a => [a] -> [a] - A sorting algorithm in Haskell takes a list as input and returns a list as output that is a sorted permutation of the input list. What is the hexadecimal number BCD in decimal? 3021. Let b be a variable of type Bool. Which of the following boolean b nand b expressions always has the same value as not b? The expressions of an algebraic type serve as ____ for the values Literals - An expression of an algebraic type indicates its value of the type. by its construction, as a literal does Consider the following function: 36. lynx m n f |m>n=1 | m abs x + 1) ? Consider the following function: [0,2,2,1,1]. wolf x y | x < 0 = (- x ) ‘mod ‘ y | x >= 0 = x ‘mod ‘ y What is the value of map (‘wolf‘ 3) [0,-5,8,10,-1] ? Consider the following functions: 1024 otter x = 2 ^ x wolverine x = x + 2 badger f g = \ a -> f (2 * ( g a ) ) What is the value of (badger otter wolverine) 3 ? Consider the following Haskell code: [1,3,6,10,15]. bear x | x == 0 = 0 | otherwise = bear (x - 1) + x raccoon n = [ bear m | m Bool -> Bool -> Bool fisher :: Bool -> Bool -> Bool -> Bool ferret a b c fisher a b c = | True _ True = False if a == False | True b False = not b then if b == True | False True c = c then if c == False then False else True | False False _ = True else True else if c == True then False else if b == False then True else False Which of the following versions of the Haskell function ferret implements the same boolean function that fisher implements? Suppose that we would like to prove a property about a function 2 - Poly has two base cases, one for the indeterminant X and one of type Poly -> Poly (where Poly is for coefficients the type defined in Assignment 3) using structural induction. How many base cases would there be? Who invented the lambda calculus? Alonzo Church. Which mode of program execution is best for learning a Interpretation. programming language and debugging code? Consider the following Haskell code. What is the value kilkenny [1,2,3] - kilkenny is the “take” function on lists. 3 [1,2,3,4,5,6,7]? kilkenny :: Integer -> [ a ] -> [ a ] kilkenny 0 x = [] kilkenny n [] = [] kilkenny n x = ( head x) : kilkenny ( n - 1) ( tail x ) Which number in base ten cannot be represented exactly by a 1/6 member of type Float? In Haskell, what is is the type of 2.1? Fractional a => a A palindrome is a string that reads the same both from left to E1 is (reverse cs) and E2 is (tail ds) right and right to left. For example, "eye" and "racecar" are palindromes. What expressions E1 and E2 will make the following function return True if the input x of type String is a palindrome and return False if the input x of type String is not a palindrome? isPalindrome :: String -> Bool isPalindrome [] = True isPalindrome [ c ] = True isPalindrome ( c : cs ) = let ds = E1 in if c == head ds then isPalindrome E2 else False Consider the following Haskell code: NaN. x :: Float x = 0/0 What is the value of x? Consider the following Haskell code. If x is the name of a text It contains the length of each line of text in the file named x. file, what does the file "out.txt" contain after limerick x is evaluated? rathberry breaks its input string into lines, replaces each line with the line’s length, replaces each limerick x = do y Int -> Bool and (Int,Int) -> Bool denote False the same set of functions. Is this statement true or false? An n-ary function can always be represented as a unary function. True Is this statement true or false? The Patriot Missile disaster could have been avoided if the basic True unit of time was 1/16 of a second instead of 1/10 of a second. Is this statement true or false? Consider the following code where Tree is an algebraic type of sumTree t + sumTree (Branches ts x) multiple branching trees whose nodes are labeled by integers. What expression E will make the function The sum of a nonempty tree is the sum of the first branch of the sumTree return the sum of the integer labels in a member of type tree plus the sum of the tree without Tree? its first branch. data Tree = Branches [ Tree ] Integer sumTree :: Tree -> Integer sumTree ( Branches [] x ) = x sumTree ( Branches ( t : ts ) x ) = E Alonzo Church and Alan Turing independently showed that any False decision problem can be solved, in theory, by a computer program. Is this statement true or false? Both the natural numbers N and the integers Z are Noetherian False with respect to the usual order ≤ on the real numbers. Is this statement true or false? In Haskell, a function can only be applied if the function has a False name. Is this statement true or false? Who developed algorithms for performing arithmetic using the Mohammad Al-Khwarizmi. Hindu-Arabic numeral system Haskell Curry, Alonzo Church, and Alan Turing developed “combinatory logic”, “lambda calculus”, and “Turing machines”. models of computation based on ,_______ , _______and ,________ respectively. What should be put in the blanks? Consider the following code. What is the type of skibbereen? IO (). skibbereen = do x [ a ] macroom [] = [] macroom ( x : xs ) = let kinsale [] y z = [y , z ] kinsale ( x : xs ) y z | x < y = kinsale xs x z | x > z = kinsale xs y x | otherwise = kinsale xs y z in kinsale xs x x In the two’s complement representation of the integers using 8 -3 bits, what number in base 10 represents the result of adding 126 and 127? What number in base 10 is represented by the value of type Float 0.3125. whose sign bit is 0, mantissa is 1.01000000000000000000000, and exponent is equal to -2? What is the decimal number 621 in hexadecimal? 26D What is the binary number 1010101011 in hexadecimal? 2AB What is the type of the expression 2.3/0.8 in Haskell? Fractional a => a. Every boolean function can be defined using just the boolean {and}. functions in each of the following sets except Which mode of program execution is best for producing efficient Compilation to native machine code code? What value is returned in Haskell when underflow occurs during -0.0 or 0.0 the evaluation of an expression of type Float or Double? In programming languages, a literal is a(n) Expression. A positive integer is perfect if it equals the sum of its factors less [m | m [ a ] -> a sumUp [] = 0 sumUp ( x : xs ) = x + sumUp xs factors :: Integer -> [ Integer ] factors n = E perfect :: Integer -> Bool perfect n = sumUp ( factors n ) - n == n What must E be so that the function perfect computes whether or not a positive integer is perfect? The function The value of ifThenElse is a function ifThenElse a b c = if a then b else c is a Which of the following functions is defined when the input is the bulls :: Integer -> Integer integer 50? bulls x | x == 100 = 0 | otherwise = bulls ( x + 1) Let f be the boolean function defined by the following truth knicks :: Bool -> Bool -> Bool -> Bool knicks False b _ = not b knicks True _ b = not b table: Which of the following Haskell functions correctly implements f? Consider the following Haskell code: [1,2,1,2,1,2,1,2,1,2] clippers :: [ a ] -> Integer -> [ a ] clippers x 0 = [] clippers x y = x ++ clippers x ( y - 1) warriors :: Integer -> Integer -> ( Integer -> [ a ]) -> [ a ] warriors m n f | m > n = [] | m Integer lakers :: [a ] -> Integer pelicans [] = 0 lakers xs = pelicans [ x ] = 1 if length xs == 0 pelicans [x ,y ] = 2 then 0 pelicans ( x :y : z : xs ) = 3 else if length xs == 1 then 1 else if length xs == 2 then 2 else 3 The function defined as lakers is equal the function defined as Consider the following Haskell code: a*b celtics :: Integer -> Integer -> Integer celtics x y | y < 0 = celtics x ( y + 1) - x | y == 0 = 0 | y > 0 = celtics x ( y - 1) + x If a and b are expressions of type Integer, then celtics a b has the same value as Consider the following Haskell code: if y < 0 then -y else y celtics :: Integer -> Integer -> Integer celtics x y | y < 0 = celtics x ( y + 1) - x | y == 0 = 0 | y > 0 = celtics x ( y - 1) + x What natural number value should be assigned to the tuple (x,y) to show that the definition of celtics makes sense? Consider the following Haskell code: 21 pistons :: [ Integer ] -> Integer pistons [a ,b , c ] = a + (2 * b ) + (3 * c ) raptors :: Integer -> [ Integer ] -> Integer raptors x ys = pistons ( raptorsAux x ys [0 ,0 ,0]) raptorsAux :: Integer -> [ Integer ] -> [ Integer ] -> [ Integer ] raptorsAux x [] [a ,b , c ] = [a ,b , c ] raptorsAux x ( y : ys ) [a ,b , c ] | y < x = raptorsAux x ys [ a + 1 ,b , c ] | y == x = raptorsAux x ys [a ,b + 1 , c ] | y > x = raptorsAux x ys [a ,b , c + 1] What is the value of raptors 5 [2,6,1,5,4,5,8,8,3,3,9]? Without using &&, write Haskell code that defines a function and True True = True named "and" that is equivalent to &&. and _ _ = False and :: Bool -> Bool and True True = True and True False = False and False True = False and False False = False Without using ||, write Haskell code that defines a function or False False = False named "or" that is equivalent to ||. or _ _ = True or :: Bool -> Bool -> Bool or True _ = True or False b = b A prime number is a natural number greater than 1 whose only [1..n] factors are 1 and itself. Consider the Haskell code factors n = [m | m Integer -> (Integer -> [Integer]) -> [Integer] hygd m n f  | m > n = [] | m n =A | m Bool isPalindrome [] = True isPalindrome [c] = True isPalindrome (c:cs) = let ds = reverse cs in if c == E1 then isPalindrome (tail ds) else E2 What should E1 and E2 be so that isPalindrome determines whether a given string is a palindrome? Consider the following code where Tree is an algebraic type of True. multiple branching trees whose nodes are labeled by integers. data Tree = Branches [Tree] Integer sumTree :: Tree -> Integer sumTree (Branches [] x) = x sumTree (Branches (t:ts) x) = E What expression E will make the function sumTree return the sum of the integer labels in a member of type Tree? sumTree t + sumTree (Branches ts x). Consider the following Haskell code: danube :: Integer -> Bool danube 0 = True danube n = inn (abs n - 1) inn :: Integer -> Bool inn 0 = False inn n = danube (abs n - 1) What is the value of inn (-31)? According to the TCP protocol, when is a TCP segment resent The sender resends a TCP segment when the segment's timer by the sender? expires before the sender has received an acknowledgment for the segment from the receiver. Consider the following Haskell code: It returns the list of the first n members of x. nile :: Integer -> [a] -> [a] nile 0 x = [] nile n [] = [] nile n x = (head x) : nile (n - 1) ( tail x) What does nile n x return when n is a nonnegative integer and x is a list? What is the usual type of a sorting algorithm in Haskell Ord a => [a] -> [a]  COMPSCI 1JC3 C01 Midterm Test 1 McMaster University Answer Key: Large arrow (⇐=) for correct, small (←) for partially correct Day Class, Version 1 Dr. W. M. Farmer DURATION: 2 hours October 10, 2019 Please CLEARLY print: NAME: Student ID: In an addition to this examination paper, you will be given two answer sheets for this test. This examination paper includes 16 pages and 30 questions. You are responsible for ensuring that your copy of the examination paper is complete. Bring any discrepancy to the attention of your invigilator. The examination will be conducted in two stages: First Stage: You have 90 minutes to answer the questions in the examination paper on the first answer sheet working by yourself. Getting any help in any form from your fellow students and anyone else will be treated as academic dishonesty. You must submit your first answer sheet to your invigilator by the end of the 90-minute period. Your performance on the answer sheet counts for 85% of the Midterm Test 1 mark. You may want to fill out the second answer sheet as you fill out the first leaving blank those questions that you want to work on during the second stage. Second Stage: You have 30 minutes to answer the questions in the examination paper on the second answer sheet working with the other students in the test room. You may walk around the test room, but you may not leave the test room. You must submit your second answer sheet and your examination paper to your invigilator by the end of the 30-minute period. Your performance on the answer sheet counts for 15% of the Midterm Test 1 mark. Special Instructions: (1) It is your responsibility to ensure that the two answer sheets are properly completed. Your examination result depends upon proper attention to these instructions: A heavy mark must be made, completely filling the circular bubble, with an HB pencil. Print your name, student number, course name, course number and the date in the space provided on the top of Side 1 and fill in the corresponding bubbles underneath. Fill in the bubble corresponding to your version number. Mark only ONE choice from the alternatives (1, 2, 3, 4, 5 or A, B, C, D, E) provided for each question. If there is a True/False question, mark 1 (or A) for True, and 2 (or B) for False. The question number is to the left of the bubbles. Make sure that the number of the question on the scan sheet is the same as the number on the examination paper. Page 1 of 16  Pay particular attention to the “Marking Directions” given on the scan sheet. Begin answering the questions using the first set of bubbles, marked “1.” Answer all questions. (2) The use of notes and textbooks is not permitted in both stages of the test. (3) Calculators, computers, cell phones, and all other electronic devices are not to be utilized in both stages of the test. (4) Read each question carefully. (5) Try to allocate your time sensibly and divide it appropriately between the questions. (6) Select the best answer for each question. Question 1 [1 mark] Floating point arithmetic does not obey all of the standard laws of arithmetic. Is this statement true or false? A. True. ⇐= B. False. ANSWER: For example, floating point addition and multiplication are not associative. Question 2 [1 mark] In Haskell, the members of a tuple must have the same type. Is this statement true or false? A. True. B. False. ⇐= ANSWER: The members of a list must have the same type, but the members of tuple may have different types. Question 3 [1 mark] The Haskell types Int -> Int -> Bool and (Int,Int) -> Bool denote the same set of functions. Is this statement true or false? A. True. B. False. ⇐= ANSWER: The first type is the set of curryed binary functions on the integers, while the second type is the set of functions that map a pair of integers to an integer. These two sets of functions can be used to do the same things, but they are completely distinct sets of functions. Page 2 of 16 Question 4 [1 mark] An n-ary function can always be represented as a unary function. Is this statement true or false? A. True. ⇐= B. False. ANSWER: Every n-ary function f : A1 ,... , An → B can be represented a function f 0 : (A1 × · · · × An ) → B on tuples or a curryed function f 0 : A1 → (A2 · · · (An → B) · · ·). Question 5 [1 mark] The Patriot Missile disaster could have been avoided if the basic unit of time was 1/16 of a second instead of 1/10 of a second. Is this statement true or false? A. True. ⇐= B. False. ANSWER: 1/16 can be represented exactly in base 2 as (0.0001)2 , unlike 1/10. Question 6 [1 mark] Alonzo Church and Alan Turing independently showed that any decision problem can be solved, in theory, by a computer program. Is this statement true or false? A. True. B. False. ⇐= ANSWER: No! Alonzo Church and Alan Turing independently showed, for the first time, that there are decision problems that cannot be solved by computer programs. Question 7 [1 mark] Both the natural numbers N and the integers Z are Noetherian with respect to the usual order ≤ on the real numbers. Is this statement true or false? A. True. B. False. ⇐= ANSWER: The structure (N, ≤) is Noetherian since it contains no infinite descending sequences, but the structure (Z, ≤) is not Noetherian since it contains infinite descending sequences, e.g., 0, −1, −2,.... Page 3 of 16 Question 8 [1 mark] In Haskell, a function can only be applied if the function has a name. Is this statement true or false? A. True. B. False. ⇐= ANSWER: Lambda notation in Haskell allows anonymous functions to be applied, e.g., (\x -> sqrt 2 * x) 7 is the application of the doubling function to 7. Question 9 [1 mark] Who developed algorithms for performing arithmetic using the Hindu-Arabic numeral system. A. Mohammad Al-Khwarizmi. ⇐= B. George Boole. C. Gottfried Leibniz. D. Emmy Noether. ANSWER: This is one of Al-Khwarizmi’s many great accomplishments. The term “algorithm” is derived from his the Latin name Algoritmi. Question 10 [1 mark] Haskell Curry, Alonzo Church, and Alan Turing developed models of computation based on , , and , respectively. What should be put in the blanks? A. “general recursive functions”, “lambda calculus”, and “unlimited register machines”. B. “combinatory logic”, “lambda calculus”, and “Turing machines”. ⇐= C. “lambda calculus”, “combinatory logic”, and “Turing machines”. D. “combinatory logic”, “general recursive functions”, and “lambda calculus”. ANSWER: These three great pioneers of computing developed different but equivalent models of computation — a truly amazing development in the history of computing. Page 4 of 16 Question 11 [1 mark] Which of the following people completed a Ph.D. degree under the supervision of Alonzo Church? A. George Boole. B. Haskell Curry. C. Stephen Kleene. ⇐= D. Emmy Noether. ANSWER: Kleene finished his Ph.D. with Church in 1934. Question 12 [1 mark] Why is Gottfried Leibniz one of the greatest computational thinkers of all time? A. He designed and had built a machine that could perform — for the first time! — addition, subtraction, multiplication, and division. B. He conceived of a universal language in which any scientific statement could be expressed. C. He conceived of a computing device that could determine the truth of any scientific statement. D. All of the above. ⇐= ANSWER: Among his many, many superlative achievements, Leibniz saw — before anyone else — the tremendous potential of computing as a problem solving tool. Question 13 [1 mark] In the two’s complement representation of the integers using 8 bits, what number in base 10 represents the result of adding 126 and 127? A. -125 B. -3. ⇐= C. 1. D. 125. ANSWER: (126)10 + (127)10 = (01111110)2 + (01111111)2 = (11111101)2 which represents −3 in two’s complement. Page 5 of 16 Question 14 [1 mark] What number in base 10 is represented by the value of type Float whose sign bit is 0, mantissa is 1.01000000000000000000000, and exponent is equal to -2? A. 0.25. B. 0.3125. ⇐= C. 5.0. D. 9.0. ANSWER: The answer is (1.01)2 ∗ (2−2 )10 = (1.01)2 ∗ (0.01)2 = (0.0101)2 = (0.25)10 + (0.0625)10 = (0.3125)10. Question 15 [1 mark] What is the decimal number 621 in hexadecimal? A. B4. B. 1B4. C. 228. D. 26D. ⇐= ANSWER: (26D)16 = (2 ∗ 162 ) + (6 ∗ 161 ) + (13 ∗ 160 ) = (2 ∗ 256) + (6 ∗ 16) + 13 = 621. Question 16 [1 mark] What is the binary number 1010101011 in hexadecimal? A. AD. B. 1C9. C. 2AB. ⇐= D. AA3. ANSWER: (2AB)16 = (2∗162 )+(10∗161 )+(11∗160 ) = ((10)2 ∗162 )+((1010)2 ∗161 )+((1011)2 ∗160 ) = (1010101011)2. Page 6 of 16 Question 17 [1 mark] What is the type of the expression 2.3/0.8 in Haskell? A. Float. B. Double. C. Rational. D. Fractional a => a. ⇐= ANSWER: The type of 2.3/0.8 is polymorphic; 2.3/0.8 can be used in any context that requires a type in the Fractional type class. Question 18 [1 mark] Every boolean function can be defined using just the boolean functions in each of the following sets except A. {and}. ⇐= B. {nand}. C. {nor}. D. {not, or}. ANSWER: Using just and, it is not possible to define the not function, so it is not possible to define every boolean function using and alone. Question 19 [1 mark] Which mode of program execution is best for producing efficient code? A. Compilation to byte code. B. Compilation to native machine code. ⇐= C. Interpretation. D. Execution done with pencil and paper. ANSWER: Compilation translates a program to the machine code that is native to the computer on which it will run. The machine code is optimized for efficiency. Page 7 of 16 Question 20 [1 mark] What value is returned in Haskell when underflow occurs during the evaluation of an expression of type Float or Double? A. -0.0 or 0.0 ⇐= B. -Infinity. C. NaN. D. None of the above. ANSWER: -0.0 [0.0] is returned when value of the expression is too small [big] to be represented as a value in the floating point type of the expression. Question 21 [1 mark] In programming languages, a literal is a(n) A. Expression. ⇐= B. Number. C. Type. D. Value. ANSWER: A literal is an expression that “literally” tells its value; e.g., the literal 2.3 says its value is the rational number 2.3. Page 8 of 16 Question 22 [1 mark] A positive integer is perfect if it equals the sum of its factors less than itself. So 6 and 28 are perfect since 1 + 2 + 3 = 6 and 1 + 2 + 4 + 7 + 14 = 28, respectively. Consider the following code where E is an unspecified expression: sumUp :: Num a = > [ a ] -> a sumUp [] = 0 sumUp ( x : xs ) = x + sumUp xs factors :: Integer -> [ Integer ] factors n = E perfect :: Integer -> Bool perfect n = sumUp ( factors n ) - n == n What must E be so that the function perfect computes whether or not a positive integer is perfect? A. [m | m Bool -> Bool -> Bool bucks b1 b2 b3 = if b3 then if not b1 && not b2 then True else False else if not b1 && b2 then True else False B. jazz :: Bool -> Bool -> Bool -> Bool jazz b1 b2 b3 = if b1 then if b3 then False else True else if b2 then True else False C. nuggets :: Bool -> Bool -> Bool -> Bool nuggets b1 b2 b3 | b2 = if b1 && ( not b3 ) then True else False | b3 = not b1 | otherwise = False D. knicks :: Bool -> Bool -> Bool -> Bool knicks False b _ = not b knicks True _ b = not b ⇐= ANSWER: We can easily check using truth tables that only knicks correctly implements the boolean function f. Page 12 of 16 Question 26 [1 mark] Consider the following Haskell code: clippers :: [ a ] -> Integer -> [ a ] clippers x 0 = [] clippers x y = x ++ clippers x ( y - 1) warriors :: Integer -> Integer -> ( Integer -> [ a ]) -> [ a ] warriors m n f | m > n = [] | m Integer lakers xs = if length xs == 0 then 0 else if length xs == 1 then 1 else if length xs == 2 then 2 else 3 The function defined as lakers is equal the function defined as A. magic :: [ a ] -> Integer magic [] = 0 magic [x] = 1 magic [x , y ] = 2 magic [x ,y , z ] = 3 B. nets :: [ a ] -> Integer nets [] = 0 nets ( x :[]) = 1 nets ( x : y :[]) = 2 nets ( x : y : z :[]) = 3 C. grizzlies :: [ a ] -> Integer grizzlies [] = 0 grizzlies ( x : xs ) = 1 grizzlies ( x : y : xs ) = 2 grizzlies ( x : y : z : xs ) = 3 D. pelicans :: [ a ] -> Integer pelicans [] = 0 pelicans [x] = 1 pelicans [x , y ] = 2 pelicans ( x : y : z : xs ) = 3 ⇐= ANSWER: pelicans is the only equivalent function. Page 14 of 16 Question 28 [1 mark] Consider the following Haskell code: celtics :: Integer -> Integer -> Integer celtics x y | y < 0 = celtics x ( y + 1) - x | y == 0 = 0 | y > 0 = celtics x ( y - 1) + x If a and b are expressions of type Integer, then celtics a b has the same value as A. a + b. B. a - b. C. a * b. ⇐= D. (a - b) * b. ANSWER: celtics defines multiplication as repeated addition while compensating for negative numbers. Question 29 [1 mark] Consider the following Haskell code: celtics :: Integer -> Integer -> Integer celtics x y | y < 0 = celtics x ( y + 1) - x | y == 0 = 0 | y > 0 = celtics x ( y - 1) + x What natural number value should be assigned to the tuple (x,y) to show that the definition of celtics makes sense? A. x. B. y. C. x - y. D. if y < 0 then -y else y. ⇐= ANSWER: The required natural number value is the absolute value of y. Page 15 of 16 Question 30 [1 mark] Consider the following Haskell code: pistons :: [ Integer ] -> Integer pistons [a ,b , c ] = a + (2 * b ) + (3 * c ) raptors :: Integer -> [ Integer ] -> Integer raptors x ys = pistons ( raptorsAux x ys [0 ,0 ,0]) raptorsAux :: Integer -> [ Integer ] -> [ Integer ] -> [ Integer ] raptorsAux x [] [a ,b , c ] = [a ,b , c ] raptorsAux x ( y : ys ) [a ,b , c ] | y < x = raptorsAux x ys [ a + 1 ,b , c ] | y == x = raptorsAux x ys [a , b + 1 , c ] | y > x = raptorsAux x ys [a ,b , c + 1] What is the value of raptors 5 [2,6,1,5,4,5,8,8,3,3,9]? A. 11. B. 13. C. 21. ⇐= D. 29. ANSWER: Plug and chug. Please make sure your version number is clearly marked on your scan sheet! THE END. Page 16 of 16  COMPSCI 1JC3 C01 Midterm Test 1 McMaster University Answer Key: Large arrow (⇐=) for correct, small (←) for partially correct Day Class 01, Version 1 Dr. W. M. Farmer DURATION: 2 hours October 19, 2018 Please CLEARLY print: NAME: Student ID: In an addition to this examination paper, you will be given two answer sheets for this test. This examination paper includes 15 pages and 30 questions. You are responsible for ensuring that your copy of the examination paper is complete. Bring any discrepancy to the attention of your invigilator. The examination will be conducted in two stages: First Stage: You have 90 minutes to answer the questions in the examination paper on the first answer sheet working by yourself. Getting any help in any form from your fellow students and anyone else will be treated as academic dishonesty. You must submit your first answer sheet to your invigilator by the end of the 90-minute period. Your performance on the answer sheet counts for 85% of the Midterm Test 1 mark. You may want to fill out the second answer sheet as you fill out the first leaving blank those questions that you want to work on during the second stage. Second Stage: You have 30 minutes to answer the questions in the examination paper on the second answer sheet working with the other students in the test room. You may walk around the test room, but you may not leave the test room. You must submit your second answer sheet and your examination paper to your invigilator by the end of the 30-minute period. Your performance on the answer sheet counts for 15% of the Midterm Test 1 mark. Special Instructions: (1) It is your responsibility to ensure that the two answer sheets are properly completed. Your examination result depends upon proper attention to these instructions: A heavy mark must be made, completely filling the circular bubble, with an HB pencil. Print your name, student number, course name, course number and the date in the space provided on the top of Side 1 and fill in the corresponding bubbles underneath. Fill in the bubble corresponding to your version number. Mark only ONE choice from the alternatives (1, 2, 3, 4, 5 or A, B, C, D, E) provided for each question. If there is a True/False question, mark 1 (or A) for True, and 2 (or B) for False. The question number is to the left of the bubbles. Make sure that the number of the question on the scan sheet is the same as the number on the examination paper. Page 1 of 15  Pay particular attention to the “Marking Directions” given on the scan sheet. Begin answering the questions using the first set of bubbles, marked “1.” Answer all questions. (2) The use of notes and textbooks is not permitted in both stages of the test. (3) Calculators, computers, cell phones, and all other electronic devices are not to be utilized in both stages of the test. (4) Read each question carefully. (5) Try to allocate your time sensibly and divide it appropriately between the questions. (6) Select the best answer for each question. Question 1 [1 mark] It is possible to build a calculus rationator as devised by Gottfried Leibniz. Is this statement true or false? A. True. B. False. ⇐= ANSWER: A calculus rationator is a computer that is intended to be able to answer any scientific question. By showing that there are decision problems that cannot be solved by a computer, Alonzo Church showed that it is impossible to build a calculus rationator. Question 2 [1 mark] In all the major programming languages, using recursion is better than using loops. Is this statement true or false? A. True. B. False. ⇐= ANSWER: In many programming languages, such as Java and Python, recursively defined functions are not able to execute in a fixed amount of space like loops do. Page 2 of 15 Question 3 [1 mark] A type error cannot normally occur when a Haskell program is executed. Is this statement true or false? A. True. ⇐= B. False. ANSWER: If Haskell is implemented correctly, type errors will not occur during the execution of a program. Question 4 [1 mark] The associative law of addition does not hold for floating point numbers. Is this statement true or false? A. True. ⇐= B. False. ANSWER: Recall that (1.0e30 + (-1.0e30)) + 1.0 and 1.0e30 + (-1.0e30 + 1.0) have different values (1.0 and 0.0) in floating point arithmetic in Haskell. Question 5 [1 mark] Consider the function skunk defined below. The function application skunk a b c is defined whenever a,b,c are integers with the value of a ≥ 0. Is this statement true or false? skunk :: Integer -> Integer -> Integer -> Integer skunk a b c | a == 0 = b | a > 0 = skunk ( a - 1) c ( b + c ) A. True. ⇐= B. False. ANSWER: We can see that skunk a b c is defined whenever a ≥ 0 by assigning a to the input triple (a,b,c) and noticing that, when the natural number n is assigned to (a,b,c), n − 1 will be assigned to (a - 1, c, b + c), the input triple for the recursive call of skunk. Page 3 of 15 Question 6 [1 mark] The fundamental question of computational thinking is concerned with the time and space efficiency of computer programs. Is this statement true or false? A. True. B. False. ⇐= ANSWER: No, the fundamental question of computational thinking is concerned with what can and cannot be done by computers. Question 7 [1 mark] For all values a, b, c in Haskell, if (a, b, c) is a tuple, then [a, b, c] is a list. Is this statement true or false? A. True. B. False. ⇐= ANSWER: This statement is only true when a, b, c are values of the same type. Question 8 [1 mark] Modular arithmetic is used in computers to add and multiply machine integers. Is this statement true or false? A. True. ⇐= B. False. ANSWER: Yes, modular arithmetic is used to add and multiply machine integers that are represented using the two’s complement method. Page 4 of 15 Question 9 [1 mark] Who invented the first mechanical calculator that could do addition, subtraction, multiplication, and division? A. Mohammad Al-Khwarizmi. B. George Boole. C. Haskell Curry. D. Gottfried Leibniz. ⇐= ANSWER: Leibniz is the inventor of the Staffelwalze, the first machine that could do addition, subtraction, multiplication, and division. It could also compute square roots. Question 10 [1 mark] A pure functional program has A. No imperative statements. B. No loops. C. No side effects. D. All of the above. ⇐= ANSWER: A pure functional program has no side effects and thus no need for imperative statements such as loops. Page 5 of 15 Question 11 [1 mark] Consider the following Haskell code: mink :: [ Integer ] -> ( Integer -> Bool ) -> [ Integer ] mink xs p = weasel xs [] p weasel :: [ Integer ] -> [ Integer ] -> ( Integer -> Bool ) -> [ Integer ] weasel [] ys p = ys weasel ( x : xs ) ys p | p x = weasel xs ( ys ++ [ x ]) p | otherwise = weasel xs ys p What is the value of the expression mink [3,2,5,2,4,7,6] (\x -> x ‘mod‘ 2 == 0) ? A. [2,2]. B. [2,2,4,6]. ⇐= C. [3,5,7]. D. [3,5,4,7,6]. ANSWER: Just plug and chug. Page 6 of 15 Question 12 [1 mark] Consider the following Haskell code: marten :: Float -> [ Float ] -> Float -> Float marten x [] z = z marten x ( y : ys ) z = let w = abs ( x - y ) in if abs w < z then marten x ys w else marten x ys z What is the value of the Haskell expression marten 3.2 [2.1, -3.3, 4.2, 3.8, 10.5, 2.8] 100 ? A. 0.4000001. ⇐= B. 7.3. C. 13.7. D. NaN. ANSWER: Plug and chug. Question 13 [1 mark] Which of the following is a type of curryed functions? A. Integer -> Integer. B. (Integer,Integer) -> Integer. C. Integer -> Bool -> Bool. ⇐= D. [Integer] -> Integer. ANSWER: C is the type of curryed functions that take a member of Integer as input and returns a boolean function as output. Page 7 of 15 Question 14 [1 mark] Let a,b,c be Haskell variables of type Bool and let fox be the boolean expression (not a && not (b || c)) || (a || not (not b && c)) Which of the following truth tables specifies the semantics of fox? a b c fox F F F T F F T F F T F T A. F T T T T F F T T F T T T T F F T T T T a b c fox F F F T F F T F F T F T B. F T T F T F F T T F T T T T F T T T T F a b c fox F F F T F F T T F T F T C. F T T T T F F T T F T F T T F F T T T T a b c fox F F F T F F T F F T F T D. F T T T ⇐= T F F T T F T T T T F T T T T T ANSWER: D is the correct truth table for fox. Page 8 of 15 Question 15 [1 mark] In the two’s complement representation of the integers using 8 bits, what number in base 10 does 11111110 represent? A. -127. B. -2. ⇐= C. 126. D. 127. ANSWER: -127 is represented by 10000001; 126 is represented by 01111110; and 127 is represented by 01111111. Question 16 [1 mark] Which of the following statements about floating point numbers is incorrect? A. There are two floating point values that represent the number 0. B. The density of the floating point values around a real number r decreases as r increases in absolute value. C. Floating point numbers cannot represent irrational numbers. D. In Haskell, the type Double of double-precision floating point numbers represents more rational numbers than the type Rational. ⇐= ANSWER: Only D is false: the type Double contains only finitely many rational numbers, while Rational contains all the rational numbers. Question 17 [1 mark] What number in base 10 is represented by the value of type Float whose sign bit is 0, mantissa is 1.00100000000000000000000, and exponent is equal to 3? A. 3. B. 3.003. C. 9. ⇐= D. 36. ANSWER: The answer is (1.001)2 ∗ (23 )10 = (1.001)2 ∗ (1000)2 = (1001)2 = (9)10. Page 9 of 15 Question 18 [1 mark] What is the decimal number 638 in binary? A. 100111110. B. 101111110. C. 1001111010. D. 1001111110. ⇐= ANSWER: 638 = 512 + 64 + 32 + 16 + 8 + 4 + 2 = 28 + 26 + 25 + 24 + 23 + 22 + 21. Question 19 [1 mark] What is the hexadecimal number BCD in decimal? A. 584. B. 3021. ⇐= C. 6432. D. 10,871. ANSWER: (BCD)16 = (11 ∗ 162 ) + (12 ∗ 161 ) + (13 ∗ 160 ) = (11 ∗ 256) + (12 ∗ 16) + 13 = 3021. Question 20 [1 mark] Let b be a variable of type Bool. Which of the following boolean expressions always has the same value as not b? A. b and b. B. b or b. C. b nand b. ⇐= D. b implies b. ANSWER: b nand b = not (b and b) = not b. Page 10 of 15 Question 21 [1 mark] Consider the following function: lynx m n f | m > n = 1 | m abs x + 1) ? A. 0. B. 4. C. 36. ⇐= D. 58. ANSWER: Plug and chug. Question 22 [1 mark] Consider the following function: wolf x y | x < 0 = ( - x ) ‘mod ‘ y | x >= 0 = x ‘mod ‘ y What is the value of map (‘wolf‘ 3) [0,-5,8,10,-1] ? A. 6. B. [0,-2,2,1,-1]. C. [0,2,2,1,1]. ⇐= D. [3,-2,11,13,2]. ANSWER: Plug and chug. Page 11 of 15 Question 23 [1 mark] Consider the following functions: otter x = 2 ^ x wolverine x = x + 2 badger f g = \ a -> f (2 * ( g a ) ) What is the value of (badger otter wolverine) 3 ? A. 64. B. 144. C. 332. D. 1024. ⇐= ANSWER: Plug and chug. Question 24 [1 mark] Consider the following Haskell code: bear x | x == 0 = 0 | otherwise = bear ( x - 1) + x raccoon n = [ bear m | m Bool -> Bool -> Bool fisher a b c = if a == False then if b == True then if c == False then False else True else True else if c == True then False else if b == False then True else False Which of the following versions of the Haskell function ferret implements the same boolean function that fisher implements? A. ferret :: Bool -> Bool -> Bool -> Bool ferret a b c | True _ True = False | True b False = not b | False True c = c | False False _ = True ⇐= B. ferret :: Bool -> Bool -> Bool -> Bool ferret a b c | True _ _ = False | True b _ = not b | False b c = c | False False _ = True C. ferret :: Bool -> Bool -> Bool -> Bool ferret a b c | True b True = False | True b False = not b | False _ c = c | False False _ = True D. ferret :: Bool -> Bool -> Bool -> Bool ferret a b c | True True True = False | True b False = not b | False _ c = c | False False _ = True ANSWER: fisher and the A version of ferret have the same truth table. Page 13 of 15 Question 26 [1 mark] Who invented the lambda calculus? A. Alonzo Church. ⇐= B. Haskell Curry. C. Stephen Kleene. D. Alan Turing. ANSWER: Church invented the lambda calculus to serve as a model of computation. Question 27 [1 mark] Which mode of program execution is best for learning a programming language and debugging code? A. Compilation to byte code. B. Compilation to native machine code. C. Interpretation. ⇐= ANSWER: Interpretation enables code to be executed line by line — which facilitates exploring how the code works. Question 28 [1 mark] Which number in base ten cannot be represented exactly by a member of type Float? A. 1/2. B. 1/4. C. 1/6. ⇐= D. 1/8. ANSWER: 1/2 is represented by (0.1)2 ; 1/4 is represented by (0.01)2 ; and 1/8 is represented by (0.001)2. 1/6 is represented by the infinite binary fraction (0.00101010101...)2 Page 14 of 15 Question 29 [1 mark] In Haskell, what is is the type of 2.1? A. Float. B. Double C. Rational. D. Fractional a => a. ⇐= ANSWER: The type of 2.1 is polymorphic; it can be used as a value of any numeric type that represents rational numbers, i.e., Float, Double, and Rational. Question 30 [1 mark] Consider the following Haskell code: x :: Float x = 0/0 What is the value of x? A. 0. B. 1. C. Infinity. D. NaN. ⇐= ANSWER: Since the mathematical value of 0/0 is undefined, the value of x is NaN. However, note that, if x is set equal to 1/0, its value is Infinity although its mathematical value is undefined. Please make sure your version number is clearly marked on your scan sheet! THE END. Page 15 of 15  COMPSCI 1JC3 Midterm Test 2 McMaster University Answer Key: Large arrow (⇐=) for correct, small (←) for partially correct Day Class 01, 02, Version 1 Dr. W. M. Farmer DURATION: 2 hours November 17, 2017 Please CLEARLY print: NAME: Student ID: In an addition to this examination paper, you will be given two answer sheets for this test. This examination paper includes 13 pages and 30 questions. You are responsible for ensuring that your copy of the examination paper is complete. Bring any discrepancy to the attention of your invigilator. The examination will be conducted in two stages: First Stage: You have 90 minutes to answer the questions in the examination paper on the first answer sheet working by yourself. Getting any help in any form from your fellow students and anyone else will be treated as academic dishonesty. You must submit your first answer sheet to your invigilator by the end of the 90-minute period. Your performance on the answer sheet counts for 85% of the Midterm Test 1 mark. You may want to fill out the second answer sheet as you fill out the first leaving blank those questions that you want to work on during the second stage. Second Stage: You have 30 minutes to answer the questions in the examination paper on the second answer sheet working with the other students in the test room. You may walk around the test room, but you may not leave the test room. You must submit your second answer sheet and your examination paper to your invigilator by the end of the 30-minute period. Your performance on the answer sheet counts for 15% of the Midterm Test 1 mark. Special Instructions: (1) It is your responsibility to ensure that the two answer sheets are properly completed. Your examination result depends upon proper attention to these instructions: A heavy mark must be made, completely filling the circular bubble, with an HB pencil. Print your name, student number, course name, course number and the date in the space provided on the top of Side 1 and fill in the corresponding bubbles underneath. Fill in the bubble corresponding to your version number. Mark only ONE choice from the alternatives (1, 2, 3, 4, 5 or A, B, C, D, E) provided for each question. If there is a True/False question, mark 1 (or A) for True, and 2 (or B) for False. The question number is to the left of the bubbles. Make sure that the number of the question on the scan sheet is the same as the number on the examination paper. Page 1 of 13  Pay particular attention to the “Marking Directions” given on the scan sheet. Begin answering the questions using the first set of bubbles, marked “1.” Answer all questions. (2) The use of notes and textbooks is not permitted in both stages of the test. (3) Calculators, computers, cell phones, and all other electronic devices are not to be utilized in both stages of the test. (4) Read each question carefully. (5) Try to allocate your time sensibly and divide it appropriately between the questions. (6) Select the best answer for each question. Question 1 [1 mark] Public key encryption has largely replaced conventional encryption in network communication. Is this statement true or false? A. True. B. False. ⇐= ANSWER: Public key and conventional encryption are equally used in network communication today. Question 2 [1 mark] QuickCheck can be used to prove that a Haskell function satisfies a given property? Is this statement true or false? A. True. B. False. ⇐= ANSWER: QuickCheck can be used to check whether a function satisfies a given property for a finite number of randomly generated instances, but it cannot, in general, be used to check all instances. Thus it cannot be used to prove that the function satisfies the property. Question 3 [1 mark] In Haskell, an enumeration type is a special case of a sum type. Is this statement true or false? A. True. ⇐= B. False. ANSWER: An enumeration type is the simplest kind of sum type. Page 2 of 13 Question 4 [1 mark] Public key encryption is used to exchange secret keys for conventional encryption. Is this statement true or false? A. True. ⇐= B. False. ANSWER: Secret key exchange is one of the principal applications of public key encryption. Question 5 [1 mark] Unlike a server, a client usually listens at a fixed UDP or TCP protocol port. Is this statement true or false? A. True. B. False. ⇐= ANSWER: Servers usually listen at fixed protocol ports, while clients are assigned temporary protocol ports on a random basis. Question 6 [1 mark] An operating systems manages running programs as processes. Is this statement true or false? A. True. ⇐= B. False. ANSWER: A process consists of a program’s code and its current activity. Question 7 [1 mark] The TCP/IP protocol suite can run on a computer that is not connected to any physical network. Is this statement true or false? A. True. ⇐= B. False. ANSWER: TCP/IP can run on a computer without any physical network interfaces by using the virtual loopback network interface. Page 3 of 13 Question 8 [1 mark] Every Haskell function must be defined on all possible inputs. Is this statement true or false? A. True. B. False. ⇐= ANSWER: A Haskell function can be left undefined on a subset of its possible inputs. Question 9 [1 mark] Public key encryption can be used to protect A. Confidentiality. B. Integrity. C. Confidentiality and integrity. ⇐= D. Availability, confidentiality, and integrity. ANSWER: Public key encryption can be used to protect both confidentiality and integrity, but not availability. Question 10 [1 mark] A hash table is A. Used for efficiently storing and retrieving hash functions. B. Used for efficiently storing and retrieving values. ⇐= C. Used to store encrypted passwords. D. Produced by the application of a hash function. ANSWER: A hash table uses a hash function to store values that can be later quickly retrieved. Page 4 of 13 Question 11 [1 mark] The Internet has the structure of a bipartite graph. The edges of the graph are A. Hosts. B. Network interfaces. ⇐= C. Physical networks. D. Routers. ANSWER: The nodes are hosts and physical networks; the edges are network interfaces. Question 12 [1 mark] A(n) normally would be transported in the data area of a(n). Which answer fills in the blanks in order correctly? A. IP datagram, TCP segment. B. Network frame, IP datagram. C. Network frame, TCP segment. D. TCP segment, IP datagram. ⇐= ANSWER: Only D makes sense. Question 13 [1 mark] Which communication protocol provides a reliable communication service between processes? A. FTP. B. HTTP. C. IP D. TCP. ⇐= ANSWER: TCP is protocol for reliably transporting data between processes. Page 5 of 13 Question 14 [1 mark] Tim Berners-Lee invented A. HTML. B. HTTP. C. URLs. D. All of the above. ⇐= ANSWER: Yes, he invented all of these. Question 15 [1 mark] Which number can be represented exactly as a member of the type Float? A. 0.375. ⇐= B. 0.575. C. 0.610. D. 0.800 ANSWER: 0.375 = 0.25 + 0.125 = 1/4 + 1/8 = 1/22 + 1/23. Question 16 [1 mark] A shell script is a program that executes commands for a A. Command-line interface. ⇐= B. Graphical user interface. C. Web browser. D. Web server. ANSWER: A shell script is a program that executes commands for a command-line interface to an operating system called a shell. Page 6 of 13 Question 17 [1 mark] The technology underlying the Internet was developed by researchers funded by A. AT&T (before its breakup in 1982). B. IBM. C.