Quizzes Flashcards
One of the major differences between the imperative and functional programming languages is that the functional programming languages do NOT (in general)…
have side-effects.
Convert the following expression into prefix-p notation (a Scheme statement):
10 + (5 - 3) + 2/4
(+ 10 (- 5 3) (/ 2 4))
Convert the following expression into prefix-p notation (a Scheme statement):
-5 * (2 + 1/2) + 40
(+ (* (- 5) (+ 2 (/ 1 2))) 40)
The statement “a function is a first-class object” means that a function…
can be placed in a place where a value is expected.
What notation requires parentheses in order to correctly define the order of computation?
infix notation
In Scheme, the form (symbol-length? ‘James) will return:
an error message
Which of the following is a valid Scheme expression?
(* 9 (/ (- 4 2) 7))
What is the expected result for this expression (in Scheme)?
(string-ref “Hello World” 4)
/o
Given an expression: x1 + x2 + x3 + x4
Which language allows us to evaluate the expression in this order: (1) x1 plus x2; (2) x3 plus x4; (3) sum of (x1 + x2) plus sum of (x3 + x4), without concern for producing a different result than other evaluation orders:
Scheme
Which of the following expression will return false (#f)?
(number? #\7)
The Scheme for (char? #\5) will return…
true (#t)
What data structure is used in Scheme for representing extremely large integers?
probably a list. Really, we shouldn’t know or care.
A student is wondering if Scheme is a strong or weakly typed language. How might they check this?
They could execute a form like (+ #\a 10) in the REPL. If i works (like in C), then it is probably weakly typed.
Given this procedure, what is the return result?
(define (guess value)
(cond ((number? value) “I’m a number”)
((char? value “I’m a character”)
((integer? value) “I’m an integer”)))
(guess 10)
“I’m a number”
What statements contain non-functional features of Scheme?
(begin (write x) x)
(display x)
What is the result of this expression (in Scheme)?
(let ((x 10)
(y 10)
(- (* x y) y))
90
What functional feature does the code below best exhibit?
(define start-engine (lambda ()
(error-detection (wheel-velocity (wheel-sensor)) (body-velocity))))
procedures are first class objects
A let-form in Scheme is equivalent (in giving names to values) to…
an unnamed/lambda procedure.
Given the Scheme code, answer the following two questions.
((lambda (x)
((lambda (x y)
(+ x y))
5 (* 7 x)))
3)
1). What is the value passed to parameter y?
2). What is the final output?
y = 21
final output = 26
Given the Scheme code, answer the following two questions.
((lambda (x)
((lambda (x y)
(+ x y))
4 (* 6 x)))
3)
1). What is the value passed to parameter y?
2). What is the final output?
y = 18
final output = 22
Which of the following forms will return an error when run?
(‘+ 2 3)
(define a a)
Given this Scheme procedure:
(define foo (lambda (x)
(if (= x 0)
1
(* x (foo (- x 1)))
)
))
What does this procedure do?
compute x!
Which of the followings is a Scheme pair?
‘(x.y)
‘(x.x)
’(() ())
What is the return value of the code below? (min is a procedure that returns the minimum of two values.)
(define lst ‘(3 5 2 9))
(min (car lst) (cadr lst))
3
What is the correct method for constructing a pair in Scheme?
(cons 1 2)
Compare the following two Scheme forms:
(append ‘(1 2) ‘(4 5)) and (cons ‘(1 2) ‘(4 5)).
(cons ‘(1 2) ‘(4 5)) returns ‘((1 2) 4 5).
Which of the following is equivalent to the expression below?
(car (cdr ‘(1 2 3 4 5))
(cadr ‘(1 2 3 4 5))
Given this expression, what is the expected result?
(car (cdr ‘(1 2 3 4 5))
2
Why is it fair to use either recursion or iteration to solve a problem like factorial?
Factorial describes how the result should look (e.g., 6! = 6 * 5 * 4 * 3 * 2 * 1), it doesn’t require a specific algorithm to get the result.
What aspect of computation in a recursive algorithm leads to slow performance?
Deferring work until computing the recursive result.
What is the typical design approach used in Scheme algorithms (like cipher or mergesort)?
Break functionality into little pieces and then assemble them into something more complicated
Consider the first two procedures for doing the cipher encryption:
(define (string-encryption str) ;main procedure
(encryption-recursive str 0 (string-length str)))
(define (encryption-recursive str pos len)
(if (>= pos len)
“” ;empty string
(string-append
(character-encryption (string-ref str pos))
(encryption-recursive str (+ pos 1) len))))
Why does the true branch of the if-statement in encryption-recursive return “” instead of ‘()?
The result will eventually be used in string-append which needs a string.
Given the Scheme code below, answer the following questions related to the Fantastic Four abstract approach.
(define dtob (lambda (N) ; line 1
(if (= N 0) (list 0) ; line 2
(append (dtob (quotient N 2)) ; line 3
(list (remainder N 2)))))) ; line 4
What line of code defines the stopping condition and the return value?
Line 2
Given the Scheme code below, answer the following questions related to the Fantastic Four abstract approach.
(define dtob (lambda (N) ; line 1
(if (= N 0) (list 0) ; line 2
(append (dtob (quotient N 2)) ; line 3
(list (remainder N 2)))))) ; line 4
What line of code contains the size-M problem, where M < N?
Line 3
Given the Scheme code below, answer the following questions related to the Fantastic Four abstract approach.
(define dtob (lambda (N) ; line 1
(if (= N 0) (list 0) ; line 2
(append (dtob (quotient N 2)) ; line 3
(list (remainder N 2)))))) ; line 4
What line of code defines the step that constructs the solution to the size-N problem?
Size 3 and 4
Given the Scheme code as follows. What is the output?
(define not-gate (lambda (x) (if (= x 0) 1 0)))
(define onescomplement (lambda (a-list) (map not-gate a-list)))
(onescomplement ‘(0 1 0 2 0 3))
(1 0 1 0 1 0)
A higher order function is a function that takes the…
operator of a function as an argument.
Given this procedure, what is the expected result?
(map (lambda (x) (+ x x 2 )) ‘(1 2 3 4 5 (6 7)))
Error Message
Given this procedure, what is the expected result?
(map (lambda (x) (+ x x 2 )) ‘(1 2 3 4 5 6))
(4 6 8 10 12 14)
Given this procedure, and assuming filter is defined as in the slides, what is the expected result?
(filter (lambda (x) (= (remainder x 2) 0)) ‘(1 2 3 4 5 6))
‘(2 4 6)
Filter is a higher-order function that…
applies a predicate to all elements of a list.
The first implementation of mergesort only processed lists of numbers. How did higher-order programming help to make it generic and able to process more types of data?
Parameters were added to the algorithm to specify specific procedures for examining data.
Which of the following predicates in logic programming matches most closely with this statement?
“Bill listens to music or news.”
listensto(bill, music); listnesto(bill, news).
The key idea of logic programming paradigm is to solve a problem by describing…
what the problem is.
A Prolog program finds a solution by…
searching the built-in database consisting of facts and rules.
A Prolog variable represents a…
place holder.
Waht notation does Prolog use for expressing arithmetic operations?
infix notation
How many arguments can be defined in a fact?
n, where n >= 0.
We apply an anonymous variable in the definition of a rule if we…
do not want to obtain a return value to the variable.
A fact starts with a relationship followed by a list of arguments. The arguments of a fact…
can be variables or simple values or structures.
A goal succeeds, if there are facts (rules) that match or unify the goal. What are required in order for a goal clause and a fact to unify?
Their predicates are the same,
they have the same number of arguments,
and
their corresponding arguments match.
A Prolog program usually contains…
facts,
rules,
and
queries
Given these facts:
is_dessert(cookie).
is_dessert(ice_cream).
is_dessert(pie).
is_dessert(cheesecake).
is_fruit(strawberry).
is_fruit(apple).
is_fruit(peach).
contains(cookie, chocolate_chips).
contains(ice_cream, cookie).
contains(ice_cream, strawberry).
contains(ice_cream, peach).
contains(pie, apple).
contains(pie, peach).
contains(pie, strawberry).
contains(cheesecake, strawberry).
Which of the following rule can identify the list of desserts that contains apple?
apple_dessert(X) :- is_dessert(X), contains(X, apple).
In a Prolog recursive rule, what components are required?
Stopping condition.
Size-M problem, where M<N
Size-N problem
What is wrong with this piece of Prolog code?
ancestor(A, D) :- ancestor (A, P), ancestor(P, D).
It does not have a stopping condition.
If we try to use tail-recursive rules to implement non-tail-recursive rules, it will normally result in rules that are…
more complex and more difficult to understand.
A circular definition of a rule…
may cause an infinite loop for certain goals.
Assume that the rule factorial (N, Fac) will compute Fac = N!. What should be the output if the following question is asked?
?- factorial(2, 5).
no
What programming language features are supported in Prolog?
Call-by-value
Call-by-reference
The following Prolog program solves the hanoi tower problem:
hanoi(N) :- move(N, source, center, destination).
move(1, S, _, D) :- write(‘Move top from ‘), write(S), write(‘ to ‘), write(D), nl.
move(N, S, C, D) :- N>1, M is N-1, move(M, S, D, C), move(1, S, _, D), move (M, C, S, D).
What are the size-(N-1) problems in the program?
move(M, S, D, C)
move(M, C, S, D)
Explain how the following rules check if there is a miscolor in a map factbase.
adjacent(X, Y) :- edge(X, Y); edge(Y, X).
miscolor(S1, S2, Color1) :- adjacent(S1, S2), color(S1, Color1), color(S2, Color1).
Prolog runtime will iteratively apply the rules to all the facts to find the matches and mismatches.
Which of the followings is equivalent to this Prolog list: [cat | dog, pig]]?
[cat, dog, pig]
What goal will return a “no” answer?
NONE OF THESE:
member(cat, [cat | [dog | [pig | []]]]).
member(cat, [cat | [dog | [pig | []]]]).
member(cat, [cat | [dog | [pig | []]]]).
What are the possible answers of the following goal (question)?
?- member([2, X], [[1, a], [2, m], [2, z], [3, p], [4, v]]).
X = m;
X = z;
Given a Prolog pair [H | T], which of the following statements are correct?
If T is a list, then [H | T] is a list.
If T is not a list, then [H | T] is not a list.
The following rules will trigger a singleton variable warning. How do you fix the problem?
count([], 0) :- !.
count([X | Tail], S) :- count(Tail, S2), S is 1+S2.
Change X to _.
Which sorting algorithm has the best execution time in the worse case scenario?
Merge sort
According to the quick sort algorithm, how can the pivot value be selected?
Any element in then current list can be selected.
In quicksort, what does the following clause mean?
split(Pivot, [X | T], [X | Le], Gt) :- X =< Pivot, split(Pivot, T, Le, Gt).
If x=< Pivot, add X to the beginning of Le.
Given the following set of the recursive rules, what clause represents the size-(N-1) problem?
bar([],[]).
bar([X | L], F) :- bar(L, G), append(G, [X], F).
bar(L, G).
Given the “Duplicate-Removal” rules below:
drm([], []) :- !.
drm([Head | Tail], NL) :- member(Head, Tail), drm(Tail, NL), !.
drm([H1 | T1], [H1 | T2]) :- drm(T1, T2).
Which line of the code actually excludes an element from the result list?
drm([Head | Tail], NL) :- member(Head, Tail), drm(Tail, NL), !.
What does the following set of the recursive rules do?
bar([], []).
bar([X | L], F) :- bar(L, G), append(G, [X], F).
Reverse a list
A backtracking point is a point, from which the Prolog runtime will re-start its search,…
if the current search fails.
Cut (!) is a clause that always returns…
true.
A cut interferes with a recursive process by removing the recursive exit points.
False.
Using a cut (!) in a rule can…
reduce possible answers of a question that is asked using the rule.
Prolog allows to dynamically adding facts into the factbase through the following operations.
Asserta(fact).
Assertz(fact).
We can use a repeat clause to form a loop. What clause do we typically use to return to the repeat point?
fail
Which of the following mechanisms can make Prolog search more efficient?
Place the stopping condition (facts) before recursive rules.
Use tail recursion if possible.
Use cut if only one answer is needed.
