CSCB36 Exam Practice University of Toronto Scarborough PDF

Preview

Summary

Exam for practice for CSCB36 Practice University of Toronto Scarborough...

Description

University of Toronto Scarborough

CSC B36

Final Examination

12 December 2017

NAME: (circle your last name)

STUDENT NUMBER: Do not begin until you are told to do so. In the meantime, put your name and student number on this cover page and read the rest of this page. Aids allowed: None. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Duration: 3 hours. There are 9 pages and each is numbered at the bottom. Make sure you have all of them. Write legibly in the space provided. Use the backs of pages for rough work; they will not be graded.

Fall 2017

1.

/ 10

2.

/ 20

3.

/ 12

4.

/ 8

5.

/ 15

6.

/ 5

7.

/ 10

Total

/ 80

cscB36 Final Exam

Page 1 of 9

1. [10 marks total; 5 for each part] For the purpose of this question, we define a real number x to be positive rational if and only if there exist positive integers p, q such that x = pq . Let PR be the smallest set such that Basis: 2017 ∈ PR. Induction Step: If x, y ∈ PR, then (i)

1 x

∈ PR and (ii) x + y ∈ PR.

(a) Use structural induction to prove that every number in PR is positive rational. Remember to use proper proof structure when proving that a number is positive rational.

(b) Let p and q be arbitrary positive integers. Informally explain why

Fall 2017

cscB36 Final Exam

p q

∈ PR.

Page 2 of 9

2. [20 marks] Given a list L of integers, we define E(L) to be the number of even integers in L. For example, if L is [4, 8, 8, 9, 6, 3, 4], then E (L[: 3]) is 3 and E (L[3 :]) is 2. Loosely speaking, the program below takes a list L and returns the number of even integers in the “second half” of L minus the number of even integers in the “first half” of L. Furthermore, the variables n and h do not change values after they are initialized. So you may treat them j as constants. k len(L) They are there mainly to save you from having to repeatedly write “len(L)” and “ ”. 2 Use methods from class to prove the program below correct with respect to its given specification. ⊲ Precondition: L is a list of integers.

1 2 3 4 5 6

j k len(L) . ⊲ Postcondition: Return E(L[h :]) − E (L[: h]), where h = 2 ⊲ For example, if L is [4, 8, 8, 9, 6, 3, 4], then h is 3 and 2 − 3 = −1 is returned. DiffNumEvens(L)   n = len(L); h = n2 ; j = h; i = 0; s = 1; t=0 while i < n: if L[j] is even: t =t+s i = i + 1; s = −s; j =j +s·i return t

Fall 2017

cscB36 Final Exam

[more space available on next page . . . ] Page 3 of 9

[. . . additional space for question 2]

Fall 2017

cscB36 Final Exam

Page 4 of 9

3. [12 marks total; 6 for each part] For each of the following implications, state whether it holds for arbitrary regular expressions R, S and T . Justify your answers. You will receive no credit without correct justification. (a) If R ∗ S ∗ ≡ S ∗ R ∗ , then RS ≡ SR.

(b) If R ≡ ST , T ≡ SR and SRT ≡ ST R, then RT ≡ T R.

Fall 2017

cscB36 Final Exam

Page 5 of 9

4. [8 marks] Let L = {1i 0j : i, j ∈ N and j < i < 2j}. Use the Pumping Lemma to prove that L is not regular.

Fall 2017

cscB36 Final Exam

Page 6 of 9

5. [15 marks total] Let L = {1i 0j : i, j ∈ N and j < i < 2j}. This is the same language as in question 4. (a) [1 mark] Give the shortest string in L. No justification is required.

(b) [7 marks] Using as few productions as possible, give a CFG for L and explain why it is correct.

(c) [7 marks] Give a PDA that accepts L and explain why it is correct.

Fall 2017

cscB36 Final Exam

Page 7 of 9

6. [5 marks] We define a ternary boolean function called AdjacentOnes by the following truth table. x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

AdjacentOnes(x, y, z ) 0 0 0 1 0 0 1 1

Use the given truth table to write a DNF formula and a CNF formula that represent AdjacentOnes. No justification is required. Your DNF formula:

Your CNF formula:

Fall 2017

cscB36 Final Exam

Page 8 of 9

7. [10 marks total] Consider a first-order language with binary predicate B and equality predicate =. Recall from class that a binary predicate B on a domain D can be represented by a directed graph, where each node in the graph represents an element in D and an arrow from node x to node y is used to indicate B(x, y) = 1. Put another way, node x pointing to node y means B(x, y) is true. Here are 3 formulas along with the statements they express. F1 F2 F3

∀x ∃y B(x, y) ∀x ∃y B(y, x) ¬∃x ∃y (B(x, y ) ∧ B(y, x))

Every node points to some node. Every node is pointed to by some node. No node points to a node that points back to it.

(a) [4 marks] Write formulas F4 and F5 to express the following statements. F4 : Some node points to more than one node.

F5 : Some node is pointed to by more than one node.

(b) [3 marks] For this part we let our domain be D = {i : 0 < i ≤ n, where i, n ∈ N}. I.e., D = {1, 2, · · · , n}. Use the pigeonhole principle to explain why when restricted to domain D, (F1 ∧ F4 ) logically implies F5 .

(c) [3 marks] Prove that (F1 ∧ F2 ∧ F3 ∧ F4 ) does not logically imply F5 .

Fall 2017

cscB36 Final Exam

Page 9 of 9...