Released by F18 Instructors. Do not redistribute * This exam is © CS 135 instructors, 2018. Do not redistribute. + Do not use this exam as your sole source of study questions, Exams change from term to term, If you expect your exam to be identical (or even substantially similar) to this one you will be sad. Your exam may cover different material than this exam, or may cover material with a different emphasis, + Having said that, practice exams are useful for timing practice. Can you finish all the exam questions in the allotted time? Can you catch your mistakes? Can you write accurate code on paper? University of Waterloo Final Examination CS 135 Tepm: Fall Year: 2018 Identifying information will be printed here. Date: December 15, 2018 Time: 9:00 am Duration: 150 minuces Sections: 001-011 Instructors: Becker, Clarke, Hackman, Jung, Lanctot, Nijjar, he ~ ) UW Student ID Number: Number of Exam Pages 21 pages (including this cover sheet) Additional Material Allowed Provided reference sheet This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Question Points Question Points Qi z 6 8 Q 2 qr 9 Q3 6 Qs 4 Qt 8 @ 7 oS T Quo 4 ‘Total Points: 57 So at ) Va - o> ) CS 135 Final Examination Fall 2018 Page 2 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Instructions: * There are a total of 10 questions and 57 points on this exam. + All code is to use the Intermediate Student with Lambda language. + Design recipe components are not required for functions we ask you to write, unless explicitly stated in the question. If you write helper functions that are not specifically asked for, they must include a purpose. contract, and function definition, unless stated otherwise. + Ifa question or pi text in a box. rt has specific design recipe requirements or othe strictions, they will be indicated by + Unless otherwise specified, helper fun tion, Z + Throughout the exam, you should follow good programming < fas ouilined in the course such as appropriate use of coastants and meaningful identifier names. * Your functions do not have to check for invalid argument + Functions you write may use: = Any function you have written in another fe cof the sandy, question. T ‘Any function Wwe asked you to wiitg for & previous\part of the samme question (even if you did not complete that part). — Any function on the reference sheet, ‘Any built-in mathematical functigf Any other built-in function or special form . tion, ( ns may be defined locally gr separate from your primary fune- tt appears in lecture slides, unless specifically noted in the qu + Unless otherwise specified, for quesfions where you are required to provide a value, you may use either cons, List, or quoted list ngtation. Frere questions, switching between these notations does not ithe exam, notify a proctor. An announcement will be made if a significant count as a "step + If you believe there is atherror iny error is found. ~) + Itis your responsibility to properly interpret a question, ~" Do not ask questions regarding the interpretation of a question; it will not be answered and you will only disrupt your neighbours. = If there is @ non-technical term you do not understand you may ask for a definition, = If, despite your best efforts, you are still confused about a question, state your assumptions and proceed to the best of your abilities, + The amount of space allocated to a question does not necessarily reflect the length of the response required. * If you require more space to answer a question, you may use the blank page(s) at the end of this exam, but you must clearly indicate in the provided answer space that you have done so, Marks for that question will be recorded on the initial page for that question and not the additional space CS 135 Final Examination Fall 2018, Page 3 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 4 1. (2 points) History Pick one of the mous computer scientists/mathematicians we discussed in lecture or in the course notes, describe one of their major contributions to computer science, and explain why that contribution is, important today. (Don’t write more than a few lines.) 2. (2 points) Producing a Function SO Write a function make-quad-n that consumes three Nuns galled ab, anxt), and produces a funetion ‘The produced function should consume a Num ( and produce the value ax? + bx +-¢ For example. (define ay-fn (make-quad-fn 12 3) (my-fn 4) P)+¢ 2)(4) +3) “ (my-tn 6) (1) +2)6)+) Required design reci ole +; make-quad-fn: a) a (define (make-quad-tn Z i) Clomboda CA) (4 OK 0 (sy 8) OK 6 4) <))) nction definition, contraet, and any requirements, > (Num > Nur) CS 135 Final Examination Fall 2018, Page 4 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 2 3. (6 points) Binary Search Trees (a) (2 points) For cach tree below, fill in the nodes with keys 1, 2, 3,4, 5, 6, 7, 8, 9 so the resulting trees satisfy the binary search tree property. You should use each key exactly once per tree. CS 135 Final Examination Fall 2018, Page 5 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 4 (b)_ 4 points) Consider the following definition for a binary search (ree (BST): i; A Binary Search Tree (BST) is one of: * enpty * a Node (define-struct node (key Left right) ; A Node is a (make-node Nat BST BST) requires: key >= every key in left BST key < every key in right BST Notice that this definition allows duplicate keys to exist. Write function key-count which consumes a 8ST and a Nat called key. It produces the number occurrences of that key in the tree. For full marks, your solution must make use of the ordering ens of a binary search tree. Required design recipe components: Function defini Restrictions: Must use explicit recursion ~ mC ) see count bst key) NC om CY) Tom be) 2 rhe’ ts) ) tha caunt, (node-left bst’) tey))J rodeo bst)) Uey- Count, “y tight be) tey)] abs i, Cnode-lefe. bot) \ 1) CS 135 Final Examination Fall 2018, Page 6 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 4 4. (8 points) Stepping Problems For the Racket expressions below, provide the following three lines: * The first expression that would result from exactly one substitution step, using the substitution rules as defined in lectures; + The expression that would result from the second substitution step; and * The final value that is produced. If the evaluation would result in an exror, deseribe the error. Ifthe final value is reached in the first or second step, you do not need to write anything, ‘When one of these lines cequites you to write out a list, you can use cons notation, the built: List or quote notation, When renaming Local definitions, append “ 2” if possible, or else “ You do not need to repeat lines (e.g. constants) that are already in my st form and which occur at the top of your code. (a) (2 points) ~ ve) (filter (Lambda (x) (zero? (remainder x 3)) (build-List (+ 12) sar) prey > (ter Clambda. (x) (2200 (ember x))) Chuid-tist 3. qr) po) > Citler (ons te (oe eh or x 3))) ist 0 14) inal) = (lst 0) C 7 (b) 2 points) (ctimeda x93 Fama yn Taney a 2 2) 10) (Clnmbda Cy Dist | y 2) 4) jomty = (li 134) {final} > CS 135 Final Examination Fall 2018, Page 7 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this 4 (©) 2 points) (define (mystery x y z) (+ (Local [(define z (* 2 x)) (define (y x) (* 3 x))] ty z)) 2) (mystery 1 2 3) rp» (4 Coual [ene @ Ge 2D) (s (ys 2) 3) (he x) 39) f (y2)) 3) 2 pony (die 2.0 (42.1) ¢ ) Ciehve (y.0 94 3 *) (+ Wyo 2.0) 3) al NO final] > % C (d)_ (2 points) i, - ) hak, Con" (define (power x y)/ (expt|x y)) ~ (define (enigna {ga bc (cond [(> (f a BY (g a $)]Amap F (List a b c))] [else Ge (enigma power 106 2)99) 11 (eonk [> (gover fo 2) (40 4) Cap. per List loo 2 40))J Tehe te) 2%!) = (‘ond [L> (exp 108 2) OF 1060) Lap power Uist oo 2. 0) (ae tue) (final) > Exton: Ope reels wn potonetors , given Uist \oo 2 90) CS 135 Final Examination Fall 2018, Page 8 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute 5. (7 points) General ‘Trees and Mutual Recursion Consider the following mutually recursive data definitions for a set of directories (also known as a folders) and files below: iy A FileDir is one of: i * A File } * A Directory i * where the Str is the name of the file ) dada Sti) called target, and tafget, Aint: Use the data definitions Required design recipe components: For ini funtion and any helper functions, provide a function definition, contract, and any reqiigements Restrictions: You must use mutual regtirsion (\~ 7 Write your solution on the next page. } A Directory is a (cons Str (listof FileDir)) HA File is a str } ¥ where the Str is the name of the directory ¢ Write a function count-name that consumes a Directory called dir produces the total number of files and directories that hav the na to plan your helper functions. CS 135 Final Examination Fall 2018, Page 9 of 21 This document is for the exclusive use of d2dong.£4 count name: Dyedy Sf -> Nak sy eount-name ist. Llstat EreDir) > FileDic (eine (cout-rane . target) Ue (amg i) {[Lemply? dic) 0 (on (eee Use dr) faye) [Corey \e) 0] Tlebe Cé (count-tane [fst Wt) i Conan entrant (os 16) 1) {edse (court-nane/tst Cet dir))})) CS 135 Final Examination Fall 2018 Page 10 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 4 6. (8 points) Functional Abstraction 1 from class the function te to implement dot- product): plate for lock-step processing of two equal-length lists (which we used (define (Lockstep-template Ust1 Lst2) (cond [(empty? tst1) ...] [else (... (First Istt) ... (first Ist2) (Llockstep-tenplate (rest [stl) (rest lst2)) ...)1)) (a) (4 points) Write lockstep, a higher-order function that abstracts Lockstep-template. It consumes acombining function, a base value, and two equal-length lists. Por example, (lockstep f b (List x1 x2 ... xn) (List yl y2 “orm produces (f xl yl (f x2 y2... (f xm yn b))). Required design recipe components: Function Fn omit dnd any requirements Restrictions: Must use explicit recursion i went: OX KY) Y OXON) gl Q 08 ney idetine (lockstep f base yo Conk a The ibe (x) CS 135 Final Examination Fall 2018, Page Il of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 4 (b) (2 points) Write a function abs-nax that consumes 1on1 and Lon2, both of which are (Listof Num) It produces a fist that contains one clement for every pair of items at the same position in Lont and Lon2. This clement should be the larger absolute value of the pair, For example, (abs-max "(1 0) => "0 (abs-max "(2 1) "(-1 -3)) => "(2 3) (abs-max "(+1 -2 -3) "(32 1) = "(3.23) Complete the following definition of abs-nax by providing a lambda expression to replace FUNC and a value for BASE, (define (abs-max Lonl lon2) (lockstep FUNC BASE lanl lon2)) FUN: (lombda yer) (cons (imax Cabs *) Cobs e tor )) NO ony (e) 2 points) Write a function facto Guy sumes a list of numerators (Lon) and a list of denominators (Lod). bes of} woke (LiJtof Nat). It produces true if all numerators are evenly divisible by tir der inators\in the samé list position, and false otherwise. (i.e. Compare each numerator ONLY § ihe or at the same list position), You may assume all values in Lod are non-zero, For exai (factors? () (0) (factors? '(4 020) 'y23 5)) => true (factors? '(4 6 10) be 45)) = false Complete the following definition of factors? by providing a lambda expression to replace FUNC and a value for BASE. (define (factors? lon lod) (lockstes FUNC BASE lon 1od)} FUNC: (olde, Gi y) (= Lremainder * y 0)) BASE: “Hue, CS 135 Final Examination Fall 2018, Page 12 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 3 7. (9 points) Abstract List Functions Required design recipe components: For parts that ask for an expression, give only that expression, For parts that ask for a function, give only the function definition. Restrictions: For all parts of this question, you may not write helper functions and you may not use explicit recursion, You must use abstract list functions. (a) (I point) ;; A Dataset is a (Listof Num) with at least two data points Implement a function to calculate the arithmetic mean (¥) of a Dataset. Reminder: the arithmetic mean of a set of numbers is defined as: F — «309 x), where x, the value of the ith data point, Nis the number of data points, and Px is the sum of the data poifitg: xy +29 +... +2. 13 (dataset-nean ds) calculates the average of dx(_ 1) dataset-mean: Dataset. -> Num £. (ete icheck-expect (dataset-mean "(2 -1 2 2)) 1.25) 4 (define (dataset-mean ds) A CI Chale + 0 ds) Cengh 4))) C) ealculate the stindard deviation (SD) of a Dataset. SD = PDE On where. is the value offhe ith Yata point-dnd d You should use 108 and sum (2" (x; )*). Your solution may to defing consjants for N, mean @ use dataset-nean, even if youl didnot implement it. : sone se ds)\caleGlates the standard deviation of ds (b) (2 points) Implement a function to s the number of data points. i) dataset-stddy: DataSet -> Num (check-expect (datasef-stdev '(2 -1 2 2)) 1.5) (define (dataset-stdév ds) (low [ede Cloth 4) (debe mean (datnset-meon hy) Cdefie sun Chalke Conde cor) C+ (say (mean) cror)) 0 ds))] (yt OE GN )) sun)))) CS 135 Final Examination Fall 2018, Page 13 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 3 (©) @ points) When collecting data, you often have (0 remove outliers, which are the few data points that do not seem (o fit the rest of your data, A common practise is removing a data point xy if its value is more than 3 + SD larger or smaller than X. In other words: + If; > 3-43» SD: remove data point x; + fy <¥— 3+ SD: remove data points + Otherwise: keep data point xj Implement a function that consumes a Dataset and produces a new Dataset with all outliers removed. (You may assume that the above algorithm will always produce a Dataset with at least 2 elements.) For full marks, avoid explicitly calling helpers more than once by using Local Your solution may use dataset-mean and dataset -stdev, & if you did not implement them, (renove-outliers ds) removes all outliers fro} as ) the 3-SD rule (see above) and produces a clean Ne Co i} remove-outliers: Dataset -> Dataset (check-expect (remove-outliers ‘(1 -1 45 2(1 yy "(2 -121-266@-211)) (define (remove-outliers ds} (local [Caine Cat tier? 4) eS Ament ds) OK 2 (datst-stl))) ~ ane nan ds)(K 3 Cdatset-sidev !))) CS 135 Final Examination Fall 2018, Page 14 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 3 (4) G points) Write the following Racket function destruction-sort, Hint: The body can be written using only foldr, anda single Lambda (destruction-sort lon) produces the list of numbers sorted in strictly increasing order (neaning no duplicates are allowed) which is the result of working backwards fron the last number in lon and removing any elements that are out of order. destruction-sort: (Listo® Nun) -> (Listof Num) ii Examples: (check-expect (destruction-sort '(29 5)) '(5)) (check-expect (destruction-sort '(-10 40 58 5)) "(-10 5)) (check-expect (destruction-sort ‘(1359 416 16)) ‘(134 10 16)) (define (destruction-sort al Cfoukr (lambda. C4. ror) Con 1 wr) ( “ ct ri Pe [eee « yy lon) r\O iv © CS 135 Final Examination Fall 2018, Page 15 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 4 8. (4 points). Short Answer Write the final values that result from evaluating each of the following expressions, When the results are lists, use either List or quoted list notation (not cons notation). i (67) ii, (rest (first (rest (List (List 1 2) (List 3 4))))) Crest Chie Uist lie 3 49) > Lek Ui) ili, ((Lambda (x) (* x x)) 3) iv, ((lambda (y) (Lambda (x) (+ Comedia CX) (x 23) filter empty? “aro 34 Lo) vie (map (Lambda () (+ (Q¥six) x)) (List 12 .3)) Cis 16 12) vii. (build-List (foldr + -4 '(1 2 3}) even?) 2 (list 0) Vili, (foldr append (pass) "({This) (2 "shalt"))) Lagpend Uist This) Copend Cst > “shall” List “pass))) list : 1S 2“ dul ut 085, (lie 2" datt” ass) CS 135 Final Examination Fall 2018, Page 16 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 4 9. (7 points) Gener Required design recipe components: For parts that ask for an expression, For parts that ask for a function, give only the function definition ive only that expression, For this question, we define the concept of “shifting” a list. When a list is shifted to the left one time, its ment is removed and appended to its end. eg. (123456) = (234596 1) Whea a list is shifted to the right one time, its last element is renkeed ad appended to its front C eg. "(12345 6) = ON 6s 4321 To shift a list n times, we can apply n individual shifts» (a) @ points) Write a function shift-Dagt <=> aNat called n, and a non-empty list called st. It should produce Lst shifted C (define (shift-left n Ust) Cond, [com Ole {ee “5 bln) (oped (rest Ist) Uist Gist (x:))) yy) (b) 2 points) Write « function Conn that consumes a Wat called n, and & non-empty Hist called ‘Ist, It should produce Ist shifted right n times. Hint: You may find reverse useful (define (shift-rignt n Ist) (cond, [loa 1) 13 [ae (ainight Coubl n) Crevese (append (Brot. Creverse 1¢)) Lrest (reverse ie)))) CS 135 Final Examination Fall 2018, Page 17 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 3 (©) @ points) Write s function shi ft-List that consumes a non-empty (Listof Int) called Loi, It produces a new list in the following way: + If (first Loi) is negative, shift the list left (abs (First Loi)) times, then call shitt-List again, + If (First 1oi) is positive, shifl the list right (First Loi) times, then call shift-List again + If (First 104) is zero, produce Loi Inspect the following examples of shift-List carefully. (shift-List "(0 26 8 -1) (shift-List "(015 -2) 4 (shift-list 68 9)) > "(089 52M (shift-List 1) = (65 4 -2 1) (shift-List Ungar Deny TE. ¢ You may use shift-Left and shift-right, evenit} on dg de fe them. ating antes 1 Coons ‘ Cenregtve? fist li) (iRRKeE (ote (obs fst li) si) ) [lysine Chit ta) (3 alg wie ight Uist bi) bi)) | [ee bi) > My (d) (1 point) Does shi *t- List terminate for all consumed values? (Circle one) Iryes, explain why. If no, give an example of a list (in quoted list or List notation) that would cause it to run forever, CS 135 Final Examination Fall 2018, Page 18 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute Points on this page: 4 10. (4 points) Graphs Given the following definitions: i; ANode is a Sym i; A Graph is a (Listof (List Node (Listof Node))) (define a-graph '((A (B.C) (B (D)) (C (A E)) (D (F)) (E (G)) (F()) (G (AF HY) (HO) Note that the nodes and lists of neighbours in 4-graph have been sorted alphabetically. a-graph can be represented pictorally as: handles cycles but is not Bfficient on ftiany3nd graphs. “Visiting” a node means that itis assigned to orig in For the following questi os, bse “ts route a6 defined on your reference sheet, which is the version that acall to find-route/ace. essfon does not terminate, write “Does not terminate”. an exph ited in order when (find-route 'B ’H a-graph) is evaluated. (For "F a-graph) visits A B DF.) AS DF (b) (1 point) What is produced by (find-route 'B 'H a-graph)? (it 8 DF GH) (©) (1 point) Write the nodes visited in order when (find-route ‘A ’H a-graph) is evaluated. ACEGH (d) (1 point) What is produced by (find-route ‘A 'H a-graph)? Uist A CEG H) (a) (1 point) Write thy nodes yi example, (find-robte o CS 135 Final Examination Fall 2018 Page 19 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute ‘This page is intentionally left blank for your use, Do NOT remove it from your booklet. Ifyou require space to answer a question, you may use this page, bul you must clearly indicate in the provided answer space that you have done so. If this page is used for continuing an answer, the marks for work done here will be included in that question's page mark. CS 135 Final Examination Fall 2018, Page 20 of 21 This document is for the exclusive use of d2dong.Released by F18 Instructors. Do not redistribute ‘This page is intentionally left blank for your use, Do NOT remove it from your booklet. Ifyou require space to answer a question, you may use this page, bul you must clearly indicate in the provided answer space that you have done so. If this page is used for continuing an answer, the marks for work done here will be included in that question's page mark. CS 135 Final Examination Fall 2018, Page 21 of 21 This document is for the exclusive use of d2dong.CS 135 Final Examination Reference Page Abstract List Functions i; build-list; Nat (Nat -> X) -> (Listof x) (build-List n f) produces (List (f 6) ... (f (subl n))) i; filter: (X -> Bool) (Listof X) -> (Listof x) (filter pred? Ist) produces a list containing the elements of Ust for which pred? holds Ordering of elements is preserved. 33 quicksort: (Listof x) (x X -> Bool) -> (Listof X) (quicksort alox cmp) produces the items of alox sorted in order according to cmp 5; map: (X -> ¥) (Listof X) -> (Listof Y) (map f Ut) produces a list by applying f to each element of Ust. ‘Thatis, (map f (list x1 ... xn)) produces (List (f x1)... (P xn) i; foldr: (X ¥ -> Y) ¥ (Listof x) -> ¥ (foldr combine base 1st) produces (combine x1 ... (conbige xr) base)) given that Ust is (List x1... xn) 3; foldl: (XY -> ¥) Y (listof X) -> ¥ C (foldl combine base Lst) produces (combine xn ..~ ((combit, x1Sbas¢)) given that Ist is (List x1... xn) L) (string-Length s) produces tht\qumber of characters in (string=? si s2) prodiges true jfstring $1 is equal to string s2 and false otherwise P (char=? cl ¢2) ( roduces trug/if char c1 is equal to char c2 and false otherwise Selected Other Functiqns (quotient nm) sc the quotient when n is divided by m (remainder n m) C produces the remainder when n is divided by m Selected String and Character Fun' (expt nm) produces the value of 1” (abs n) produces the absolute value of n (positive? x) produces true if.x > 0, false otherwise (negative? x) produces true if x <0, false otherwise (even? x) produces true if xis even, false otherwise (odd? x) produces true if x is odd, false otherwise (zero? x) produces true if x is 0, false otherwise (append Ist1 ... Istn) produces a list of all elements in (st ... Lstn, in that order (length Ist) produces the number of elements in Ust (member? x Ist) produces true if x is in Ust, false otherwise (reverse lst) produces 1st in reverse order This document is for the exclusive use of d2dong.Graphs These are functions for finding a route in a Graph that may contain cycles. They do not implement efficient route-finding in diamond graphs. The functions neighbours, #ind- route/List and tind-route/acc match the code on Slide 12, Slide 31 and Slide 33 of Module 12 exactly. The function find-route is a wrapper function that uses find-route/acc to find a route from an origin node to a destination node in a graph. A Node is a Sym A Graph is a (listof (list Node (listof Node))) (neighbours v 6) produces the list of neighbours of v in & neighoours: Node Graph -> (Listof Node) requires: v is a node in G (define (neighbours v6) (cond [(symbol=? v (first (first G))) (second (tirst 6))] [else (neighdours v (rest 6))1)) je (find-route/ace orig dest G visited) produces a path of (ode from orig to dest in G, or false if no such path exists find-route/acc: Node Node Graph (listof Node) -> ( NO es pe false) (define (tind-route/acc orig dest G visited) (cond [{symbol=? orig dest) (List orig)] [else (Local [(define nbrs (neighbours %. (define route (Find-route/List_nbi (cond [(false? route) false] [else (cons orig ro e de C (cohs orig visited)))] J) (tind-routenist ros dest 6 a srodlces » path of odes tron a member of los to dest in G iflone exists, or false if there is no such path. find-route/List: (listo Node) Pedic (Listof Node) -> (anyof (Listof Node) false) (define (find-route/List lo\gest d yéSited) (cond [(emoty? los) false] [(member? (first los )\wisitkd) (find-route/list (rest 19S) dest G visited)] [else (local [(define route (find-route/acc (tirst los) dest G visited))) (cond [(false? route} (find-route/list (rest los) dest G visited)] [else route]})1)) (find-route orig dest G) produces a oath from orig to dest in G it one exists, or false otherwise i} find-route: Node Node Grapn -> (anyof (Listof Node) false) (define (Find-roure orig dest G) (find-route/acc orig dest G empty)) 2 This document is for the exclusive use of d2dong.