[SOLVED] IT CSE 130 Midterm, Spring 22

CSE 130 Midterm, Spring 22
Nadia Polikarpova May 2, 2022
Exam released: Monday, May 2, 9am PDT
Exam due: Tuesday, May 3, 9am PDT

Copyright By Assignmentchef assignmentchef

You must submit your answers via an online quiz on Gradescope
You may consult any course material (lecture notes, assignments, past exams, etc)
You may test your code in Elsa/ghci if youd like
You may ask for clarifications on Piazza via a private message to in-
You may resubmit as many times as you want
You may not communicate with other students or ask for anyones help
You may not search help forums (StackOverflow, Chegg) and the In- ternet for a solution
Good luck!

Q1: Lambda Calculus: Reductions [5 pts]
Check the box next to each template that can be turned into a correct single-
step beta-reduction by replacing each ? with a variable. For example:
(x->xy)z [o]
(x->xy)z []
The first template is valid because we can replace ? ? with z y. The second template is invalid because, although beta-reduction is possible, its result is z y, and we cannot obtain that by replacing ? with a variable.
You get 1 pt for each box you correctly checked or left unchecked.
(A) x->xx =b> ?
(B) (x->x)x =b> ?
(C) (x->xx)yz =b> (? ?) (? ?)
(D) (x->x(x->x))(fx) =b> ? ? (? -> ?)
[] [] [] [] []
(E) (yx->y)(fx) =b> x -> ? ?

Q2: Lambda Calculus: Functions [10 pts]
Below you will find five lambda terms, F1 through F5 (along with helper functions, H3 through H5). Each one of them implements one of eight possible algorithms, (A) through (H). Your task is to guess for each term, which algorithm it implements. You can use each algorithm zero or more times (i.e. some algorithms might remain unused and some might be used more than once):
(A) is natural number n positive?
(B) is natural number n odd?
(C) decrement natural number
(D) division of two natural numbers
(E) modulo of two natural numbers
(F) gcd of two positive numbers
(G) are two booleans equal?
(H) xor of two booleans
You get 2 points for each lambda term whose meaning you guessed correctly. You will find the definitions of all the functions used inside the terms in Appendix I at the end of the exam.
You are supposed to do this task on paper and not in Elsa. Although we cannot prevent you from using Elsa, be aware that the =~> reduction in Elsa may give incorrect answers, so you should trust your own understanding of lambda calculus over Elsa.

Lambda terms:
letF1 (2)
let H3 let F3
letH4 letF4
=xy->x(NOTy)y =
->nNOTFALSE
= p -> PAIR (INC (FST p)) (FST p)
=
-> SND (n H3 (PAIR ZERO ZERO))
=
mi->ITE(LEQ(MULm(INCi))n)(INCi)i =
m->n(H4nm)ZERO
=xy->ITE(LEQxy) (ITE (LEQ y x)
(PAIR x y)
(PAIR (SUB y x) x))
(PAIR (SUB x y) y)
=
m->FST(n(p->H5(FSTp)(SNDp))(PAIRnm))

Q3: Autocomplete [16 pts]
Suppose you want to implement an autocomplete feature in a text editor: the editor has a dictionary (which is just a set of words), and whenever the user types a prefix of a word, you want to display all words from the dictionary that start with that prefix.
To implement this feature efficiently, you decided to store the dictionary as a prefix tree (also called a trie). Here is an example of a trie that stores the set of words he, him, his, she, her.
Figure 1: A trie that stores he, him, his, she, her.
As you can see from this example, a trie is a tree, where edges are labeled with characters (note: all child edges of a single node are labeled with distinct characters). Nodes in a trie are of two kinds: terminal (the four nodes in Fig. 1 that are filled) and non-terminal (the rest of the nodes). The set of all words stored in a trie t, which we will denote W(t), is defined as the set of paths from the root to all terminal nodes.
Note that terminal nodes are not necessarily at the leaves: because our dic- tionary stores both he and her, and the former is a prefix of the latter, the node at path [h, e] is terminal (it represents the word he) but it is not a leaf.

In Haskell, we can represent a trie using the following Trie datatype:
| A trie node stores whether it is terminal + zero or mode edges
data Trie = Node Bool [Edge]
| An edge is a pair of a character and a child trie
type Edge = (Char, Trie)
With this datatype, the trie from Fig 1 would be represented like so:
pronouns = Node False [
(h, Node False [
(e, Node True [
(r, Node True [])
(i, Node False [
(s, Node True []),
(m, Node True [])
(s, Node False [
he her
his him
(h, Node False [
(e, Node True [])

Fill in the holes {- 1 -} through {- 16 -} in the code below using the following expressions {- A -} through {- W -}. You can use each expression zero or more times (i.e. some expressions might remain unused and some might be used more than once):
{- A -} []
{- B -} []
{- C -} [k:w
{- D -} [k:w
{- E -} [k:w
{- G -} cs
{- H -} cs == []
{- I -} c:cs
{- J -} c ==
{- K -} Node
{- L -} Node
{- M -} Node
{- N -} Node
{- O -} Node
{- P -} Node
{- Q -} Node
{- S -} words es
{- T -} words (Node b es)
{- U -} words t
{- V -} words t ++ words es
{- W -} words t ++ words (Node b es)
| w <- withPrefix cs t]| w <- words t]| w <- words t] ++ words (Node b es)b ((k,t):es)Task 3.1: Empty and EpsilonWrite down the definitions of the following two tries: empty, the trie that stores the empty set of words (W(empty) = {}) epsilon, the trie that stores a single word the empty string(W(epsilon) = {“”}).– | The empty trieempty :: Trie empty = {- (1) -}– | The trie that stores only the empty stringepsilon :: Trie epsilon = {- (2) -}Task 3.2: All WordsImplement the function words that returns a list of all words stored in a trie (the order of words in the list is not important). Your implementation mustsatisfy the following test cases: > words empty
> words epsilon
> words pronouns
[her,he,his,him,she]
| All words stored in a trie
words :: Trie -> [String]
words (Node False []) = {- (3) -} words (Node True []) = {- (4) -} words( {-(5)-} )={-(6)-}

Task 3.3: Words with Prefix
Finally, implement the function withPrefix that returns a list of all words with a given prefix stored in a trie (this is the main function you need to implement autocomplete!). The order of words in the list is not important. You can use words from Task 3.2 in this function. Your implementation must satisfy the following test cases:
> withPrefix he pronouns
[her, he]
> withPrefix pronouns
[her,he,his,him,she]
> withPrefix m pronouns
| Words with a given prefix stored in a trie
withPrefix :: String -> Trie -> [String] withPrefix [] t = {- (7) -} withPrefix ({- (8) -}) ({- (9) -}) = {- (10) -} withPrefix ({- (11) -}) ({- (12) -})
| {- (13) -} = {- (14) -}
| otherwise = withPrefix ({- (15) -}) ({- (16) -})

Lambda Calculus Cheat Sheet
Here is a list of definitions you may find useful for Q2
Booleans
letTRUE =xy->x
let FALSE = x y -> y letITE =bxy->bxy letNOT =bxy->byx
Pairs
letPAIR =xyb->bxy letFST =p ->pTRUE let SND = p -> p FALSE
Numbers
letZERO letONE letTWO letINC letADD letMUL let ISZ let SKIP1 let DEC letSUB letLEQ
=fx->f(fx)
=
fx->f(nfx)
=
m->nINCm
=
m->n(ADDm)ZERO =
->n(z->FALSE)TRUE
= f p -> PAIR TRUE (ITE (FST p) (f (SND p)) (SND p)) =
-> SND (n (SKIP1 INC) (PAIR FALSE ZERO)) =
m->mDECn
=
m->ISZ(SUBnm)

CS: assignmentchef QQ: 1823890830 Email: [email protected]