• CLEARLY PRINT YOUR NAME HERE:

• A quick-reference sheet will be provided with the exam.

• You have 3 hours to complete the exam (9:00-12:00)

• There are 7 questions on the exam, worth 15 marks each.
  Your best 6 questions will be used, for a total of 90 marks.

• Answer directly on the exam paper, using the backs of pages if extra space is required.

• The exam is closed book, closed notes, no calculators, phones, or other electronic aids of any form may be used during the exam.

• Be sure to check your exam to ensure all 7 questions and the reference sheet have been included.

Question	Mark
1. Regular expressions [15 marks]
2. Finite state machines [15 marks]
3. Algorithm complexity [15 marks]
4. Data representation [15 marks]
5. Digital logic [15 marks]
6. Prolog [15 marks]
7. Lisp [15 marks]
Exam Total (Best 6) [90 marks]

Question 1: Regular expressions [15]

1. Over the alphabet [A-Z], give a regular expression for the set of strings of odd length that begin with a vowel [AEIOU] and whose total length is greater than 2.

   Sample solution ^[AEIOU]([A-Z]{2})+$

2. Suppose we wanted to describe the set of hex strings representing object code for valid marie instructions. Provide a regular expression that does so, and justify your reasoning.

   Sample solution They will each be 4 hex characters long, starting with the character that indicates the instruction type and then following one of three patterns: input, output, halt, and clear end with 000 skipcond ends with one of 000, 400, 800 the other instructions end with any three hex digits hence: ^(([567A]000) | (8[048]00) | ([0-49B-E][0-9A-F]{3}))$

Question 2: Finite state machines [15]

1. Given the state table below, draw the corresponding finite state machine and show which state the FSM should be in after processing the string: "xyzyxx".

   Current State	Symbol	New State
   Start	x	Q1
   Start	y	Q2
   Start	z	Q3
   Q1	x	Q1
   Q1	y	Q3
   Q1	z	Q2
   Q2	x	Q3
   Q2	y	Q2
   Q2	z	Q1
   Q3	x	Q1
   Q3	y	Q2
   Q3	z	Accept
   Accept	x	Accept
   Accept	y	Q1
   Accept	z	Q3

   Sample solution For string xyzyxxx the state sequence would be Start -> Q1 -> Q3 -> Accept -> Q1 -> Q1 -> Q1 (string not accepted)

2. If we were to describe the fetch-decode-execute cycle in terms of a finite state machine,
   (i) what would be the key states?
   (ii) when would the transitions between them take place?
   (iii) in which state(s) would the IR be updated?
   (iv) in which state(s) might the PC be updated?

   Sample solution One simple possibility is to have five states: start --> fetch --> decode --> execute --> accept ^ / \__________________/ We go from start to fetch once the program is loaded and begins running, we go from fetch to decode once the next instruction has been fetched, we go from decode to execute once decoding is completed, we go from execute to accept after a halt instruction has been executed, otherwise once an instruction execution completes we go back to fetch The instruction register would be updated during the fetch instruction. The program counter would be updated during decoding, but could also be updated by certain instructions during execution (e.g. by a jump instruction).

Question 3: Algorithm complexity [15]

1. Determine the complexity order for the marie program below as one of O(logN), O(N), O(N logN), or O(N²). Justify your answer.

   input store N L, load N subt Y store N output skipcond 0 jump L halt N, hex 0 Y, hex 10

   Sample solution O(N) - the code reads and stores N, then repeatedly subtracts 10 from N until the result is negative. This takes roughly N/10 iterations, thus O(N), linear

2. Determine the complexity order for the lisp function below as one of O(logN), O(N), O(N logN), or O(N²). Justify your answer.

   (defun f (N) (cond ((not (numberp N)) 0) ((< N 1) 0) (t (+ N (f (/ N 2))))))

   Sample solution O(logN) - the recursion quits when N < 1, the recursive calls cut N in half each time, rounding down, thus at most 1 + log2(N) calls

Question 4: Data representation [15]

Suppose file "hexStuff.cl" contains the definition of a lisp function, gethex, described below.

gethex takes an integer, N, as a parameter and returns an 8-character string that is the hex representation of N (two's complement).

For instance (gethex 18) would return "00000012", and (gethex -1) would return "FFFFFFFF".

Show the output that would be produced if we ran the following lisp script:

#! /usr/bin/gcl -f (load "hexStuff.cl") (defun product (X Y) (if (and (integerp X) (integerp Y)) (let ((result (* x y))) (format t "~A * ~A is ~A~%" (gethex X) (gethex Y) (gethex result)) result))) (format t "Final: ~A~%" (gethex (+ 17 (product -3 -2))))

Sample solution Note that it's essentially displaying VAL1 * VAL2 is PRODUCT Final RESULT where VAL1 is the hex for -3, VAL2 is the hex for -2, PRODUCT is the hex for 6 (i.e. (-3)*(-2)), and RESULT is the hex for 23 (i.e. 6+17) Thus the output is FFFFFFFD * FFFFFFFE is 00000006 Final 00000017

Question 5: Digital logic [15]

Based on the truth table below, answer questions 1-3.

wxyz   F     G   0000   0   1 0001   0   0 0010   1   1 0011   1   0 0100   1   0 0101   0   0 0110   1   1 0111   0   1 1000   0   0 1001   0   0 1010   1   0 1011   1   0 1100   1   0 1101   0   0 1110   1   1 1111   0   1

Provide Karnaugh maps corresponding to functions F and G. Based on the Karnaugh maps above, provide minimal sum-of-products expressions for F and G. Be sure to clearly circle the term groupings used from the Karnaugh maps. Sample solution Remember the maps wrap around top-bottom and left-right, hence for F we're getting three groups of four, while for G we're getting a group of 2 and a group of 4 Draw the circuit corresponding to the minimal sum-of-products expressions for F and G.

Part 3 sample solution

Question 6: Prolog [15]

1. Write a set of facts/rules to support prolog queries of the form
         extremes(L, Sm, Lg).
   Where extremes expects L to be a list of numbers, and attempts to unify Sm and Lg with the smallest and largest values in L.

   Sample solution extremes(L,Sm,Lg) :- smallest(L,Sm), largest(L,Lg). smallest([N], N) :- number(N). smallest([H|T], H) :- number(H), smallest(T,S), H < S. smallest([H|T], S) :- number(H), smallest(T,S), H >= S. largest([N], N) :- number(N). largest([H|T], H) :- number(H), largest(T,L), H > L. largest([H|T], L) :- number(H), largest(T,L), H =< L.

2. For the set of prolog facts/rules below, show the result of the following query, and briefly explain your reasoning
         memRequest([[128,1000],[4096,2000],[2048,8000],[512,9000]], 2048, C, MA).

   % memRequest(FreeMem, RequestSize, Chosen, MemAfter) % -------------------------------------------------- % given a list of available memory segments, FreeMem, and % a request for a block of memory of a specific size, RequestSize, % determine the chosen block, Chosen, and % the updated memory list, MemAfter % % memory segments are described as pairs: [ size, address] % where size is the number of available bytes % and address is the memory address of the start of the segment memRequest([[S,A]|T], R, [S,A], T) :- posint(S), posint(A), posint(R), R =< S. memRequest([H|T], R, C, [H|MA]) :- memRequest(T, R, C, MA). memRequest(M, _, noneAvail, M). posint(X) :- integer(X), X > 0.

   Sample solution Note that for a request like memRequest(L, N, C, M), memRequest is finding the first free block that is at least as big as N, unifying that block's [Size,Address] list with C, and unifying M with everything that's left in L after removing C So in this query N is 2048, and the first big enough chunk is the one [4096,2000], so the query unifies C with [4096,2000] and MA with the rest, i.e. [[128,1000], [2048,8000], [512,9000]]

Question 7: Lisp [15]

1. Suppose we already have two functions available:
   (smallest L) returns the smallest element of list L
   (largest L) returns the largest element of list L.

   Write a lisp function, extremes, that expects a list, L, as its only parameter.

   If L is not a list, or is an empty list, then extremes returns nil, otherwise extremes returns a list of two values: the smallest value in L and the largest value in L.

   For example, (extremes '(3 12 4 1)) returns (1 12)

   Sample solution (defun extremes (L) (cond ((not (listp L)) nil) ((null L) nil) (t (list (smallest L) (largest L)))))

2. Write a lisp script (remember your #! line) that does the following (in the order specified)
   • loads a file named "final.pl",
   • prompts the user to enter a list,
   • reads the list and stores it in a variable,
   • calls your function from part 1 (assume it was defined in the "final.pl" file) and stores the result in a variable,
   • prints the contents of both variables.

   Sample solution #! /usr/bin/gcl -f (load "final.pl") ; <-- I really should have named it final.cl!!! (format t "Please enter a list~%") (defvar L (read)) (defvar result (extremes L)) (format t "Extremes of ~A are ~A~%" L result)