2019 midterm sample solution 2019 final exam sample solution

There will be one midterm and one final exam for the course. The midterm is worth 24% of your final grade, and the final exam is worth 40%.

The midterm will be held in class, scheduled for Tuesday March 5th, and will cover all material up to and including the labs and lectures on Marie/assembly language. The midterm will be closed book, closed notes, calculators and other electronics will not be permitted. A short reference sheet will be provided with the exam.

The final exam will be held in the VIU final exam period, on Tuesday April 23rd from 9am-noon in the gym. It will cover all course material, but will heavily focus on material not covered by the midterm. A short reference sheet will be provided with the exam. The final will be closed book, closed notes, calculators and other electronics will not be permitted.

You must pass the final exam to pass the course.

Practice midterms: version 1, version 2, some additional circuit practice, and the reference sheet

Practice finals: version 1, version 2, some additional discussion question practice, and the reference sheet

Programming practice for lisp and prolog

If you're looking for suitable small programming problems to practice on, try the ones below. Sample solutions for each of them can be found on the coding examples pages for lisp or prolog.

lisp: write functions to do each of the following

• count all the elements in a list and all its nested lists
• find the smallest number in a list
• append the contents of one list to another
• take the difference of two lists
• print each element of a list, one element per line
• reverse a list
• get the user to enter a value, then identify the type as accurately as possible

  prolog: write sets of facts/rules to handle queries to do each of the following

• find the smallest number in a list
• find the nth element of a list
• remove duplicates from a list
• take the difference of two lists
• check if a list is sorted
• compute N! (factorial)
• get the user to enter values for A,B,C,X, and compute AX^2 + BX + C

Practice with finite state machines and regular expressions

Regex -> FSM For each of the regular expressions below, provide a finite state machine that recognizes the same language

• (101 | 10101)+
• (0 | 1(01*0)*1)*

  FSM and regex For each of the languages described below, provide both a finite state machine and a regular expression for the language, where the alphabet used is [0-9A-F]

• The set of all even-length strings that do not begin with 0,1,2, or 3
• The set of all strings whose length is a multiple of 4 and where each block of four characters contains at least one F
• The set of all strings that contain a section of three characters that do not contain a 3, 6, or 9

Practice with algorithm complexity For each of the code elements described below, explain whether their worst case complexity is constant-time, log-time, linear-time, quadratic-time, or exponential-time.

• the main routine in this example, using the cash amount as the "size" of the problem
• the prTriangle routine in this example, using the width as the "size" of the problem
• the sum routine in this example, using N as the "size" of the problem
• the shuffle routine in this example, using N as the "size" of the problem
• questions 1-4 in this old 161 exercise