CSCI 162 practice final [90 marks total]

The final is closed book, closed notes, no calculators or other electronics permitted. A reference sheet is included with the exam, covering key Marie opcodes, boolean logic identities, powers of 2, lisp syntax, and prolog syntax.

Question 1: [15 marks]

Study the truth table below, then answer questions 1 and 2.
wxyz   f     g     h  
0000  0  0  0
0001  0  1  0
0010  0  1  0
0011  1  0  1
0100  0  1  0
0101  1  0  1
0110  1  0  1
0111  1  1  1
1000  0  0  1
1001  0  1  1
1010  0  1  1
1011  1  0  0
1100  0  1  0
1101  1  0  0
1110  1  0  0
1111  1  1  0

  1. Give karnaugh maps for each of the three output functions (f, g, h) and minimal sum of products expressions for each. Clearly circle the groupings you used on the k-maps.

  2. Draw a circuit matching your expressions.

Question 2: [15 marks]

Study the marie program below then answer questions 1 and 2. 
      input
      add      X
      store    X
      add      X
      add      X
Top,  skipcond 800
      jump     Done
      output
      subt     Decr
      jump     Top
Done, halt
Decr, dec      3
X,    dec      1

  1. Show the output produced by the program if the user enters the value 3 for N.

  2. Give the complexity of the program as one of the following, and justify your answer: O(log(N)), O(N), O(N log(N)), O(N2)

Question 3: [15 marks]

  1. For the lisp function below, write a set of prolog facts/rules that handles equivalent queries: 
    (defun f (N L)
   (cond
       ((not (listp L)) nil)
       ((not (integerp N)) nil)
       ((< N 0) nil)
       ((null L) nil)
       ((not (numberp (car L))) nil)
       ((= N 0) (car L))
       (t (f (- N 1) (cdr L)))))

  2. For the set of prolog facts/rules below, write a lisp function that handles equivalent function calls: 
    f([], 0).
f([H|T], Result) :- number(H), f(T, TR), R is H + TR, R = Result.
f([_|T], Result) :- f(T,Result).

Question 4: [15 marks]

Based on the regular expression and the state table shown below, answer questions 1, 2, and 3.

Regular expression:   ( 0 | (1 (0 1* 0)* 1)* )

State table:
Current stateInputNew state
Start 0 Accept
Start 1 B
Accept 0 Accept
Accept 1 B
B 0 C
B 1 Accept
C 0 B
C 1 C

  1. Draw the finite state machine corresponding to the state table.

  2. For the 6 bit binary string corresponding to integer 23, determine:
    (a) if it is accepted by the FSM machine, and if not determine which state the FSM ends in
    (b) determine if it is part of the language recognized by the regular expression.

  3. For the 6 bit binary string corresponding to integer 9, determine:
    (a) if it is accepted by the FSM machine, and if not determine which state the FSM ends in
    (b) determine if it is part of the language recognized by the regular expression.

Question 5: [15 marks]

Write a lisp function that takes two parameters, L and N, and does the following:

Question 6: [15 marks]

Write a set of prolog facts/rules to support queries of the form:
      getSmallerNums(L, N, R).
such that if L is a list and N is a number then R is a list of all the numbers in L that are smaller than N.

e.g. the result of getSmallerNums([13, 7, 7, 9, 11, 8], 9, R). would be R = [ 7, 7, 8 ]