Instructions

Please either 1) typeset your answers in LATEX and submit a PDF file through Piazza, or else 2) write answers by hand and turn in a physical copy in class, 3) write answers by hand and send a scanned PDF file. We prefer to read succinct and precise answers. If you can be precise while being succinct with your answers, please try.


How multiple choice is graded. Multiple choice questions may have multiple correct answers.  If there are N multiple correct answers, then each correct answer is worth 1/N of the total points for the question. You lose 1/N points for every wrong answer you circle. The total cannot go negative.  In code, score = points * max(num correct – num wrong) / total correct


Clarity, succinctness, writing your name and Netid: [5 pts].

1 Indistinguishability [6 pts]


1. (3 pts) If {Xn}n is computationally indistinguishable from {Yn}n, {Yn}n is computationally indistin- guishable from {Zn}n, then (select the one that is always correct)

(a) {Xn}n is computationally indistinguishable from {Zn}n

(b) {Xn}n can be distinguished from {Zn}n

(c) Sometimes {Xn}n can be distinguished from {Zn}n, sometimes {Xn}n is computationally indis- tinguishable from {Zn}n

2. (3 pts) If Xn n can be distinguished from Yn n, Yn n can be distinguished from Zn n, then (select the one that is always correct)

(a) {Xn}n is computationally indistinguishable from {Zn}n

(b) {Xn}n can be distinguished from {Zn}n



(c) Sometimes {Xn}n can be distinguished from {Zn}n, sometimes {Xn}n is computationally indis- tinguishable from {Zn}n


2 Useful Asymptotical Notations [6 points]

(No need to prove throughout this question.)


2.1 [2 pts]

Among the following functions in n, please select all that are negligible functions in n:



a. 12 b. 1



c. 1

d. n−3 e. n− log log log n f. 2n g. nlog log n



2n 2n

nlog log n




2.2 [2 pts]

Suppose that f1(n), f2(n) are negligible functions in n. Let g(n) denote some fixed polynomial in n. Which of the following must be negligible functions in n:

a. f1(n) + f2(n) b. f1(n)f2(n) c. f1(n)g(n) d. g(n) e. √f1(n) f. f1(n)g(n)

2.3 [2 pts]
(Let g1(n), g2(n) denote two fixed polynomials in n. Which of the following must be polynomial in n:

a. g1(n) + g2(n) b. g1(n)g2(n) c. g1(n)g2(n) d. g1(n) + 203942 e. g1(n) + 2n f. g1(n)100

g. 2g1(n)


3 Pseudorandomness [10 pts]

3.1 Pseudorandom Generators [5 pts]

Let tt : {0, 1}λ → {0, 1}λ be a PRG. Circle all PRGs below. (No need to prove)

a. ttj(s) = if |s| > 1024 then tt(s) else 0A(|s|)

b. ttj(s1 || s2) = tt(s1) ⊕ tt(s2), where |s1| = |s2| = λ c. ttj(s1Due: 14th of October 2018 at 11:59pm



COMP 9020 – project 3
Note: In your project, how you arrived at your solution is as important (if not more so) than the solution itself and will be assessed accordingly. There may be more than one way to find a solution, and your approach should contain enough detail to justify its correctness. Lecture content can be assumed to be common knowledge.

1. Let (T, ∧, ∨,j , 0, 1) be a Boolean Algebra.

Define ∗ : T × T → T and ◦ : T × T → T as follows:

x ∗ y := (x ∨ y)j x ◦ y := (x ∧ y)j

(a) Show, using the laws of Boolean Algebra, how to define x ∗ y using only x, y, ◦ and parentheses.

(b) Show, using the laws of Boolean Algebra, how to define x ◦ y using only x, y, ∗ and parentheses.

(10 marks)

Define R ⊆ T × T as follows:

(x, y) ∈ R if, and only if, (x ∧ y) ∨ (xj ∧ yj) = 1

(c) Show, using the laws of Boolean Algebra, that R is an equivalence relation. Hint: You may want to use the observation that if A = B = 1 then A ∧ B ∧ C = A ∧ B implies C = 1 (why?)

(10 marks)

2. Let P F denote the set of well-formed propositional formulas made up of propositional variables,  ,   , and the connectives   ,   , and   .  Recall from Quiz 7 the definitions of dual and flip as functions from P F to P F :

• dual(p) = p • flip(p) = ¬p

• dual(T) = ⊥; dual(⊥) = T • flip(T) = T; flip(⊥) = ⊥

• dual(¬ϕ) = ¬dual(ϕ) • flip(¬ϕ) = ¬flip(ϕ)

• dual(ϕ ∧ ψ) = dual(ϕ) ∨ dual(ψ) • flip(ϕ ∧ ψ) = flip(ϕ) ∧ flip(ψ)

• dual(ϕ ∨ ψ) = dual(ϕ) ∧ dual(ψ) • flip(ϕ ∨ ψ) = flip(ϕ) ∨ flip(ψ)

(a) For the formula ϕ = p ∨ (q ∧ ¬r):

(i) What is dual(ϕ)?

(ii) What  is flip(ϕ)?

(b) Prove that for all ϕ ∈ P F : flip(ϕ) is logically equivalent to ¬dual(ϕ).

(10 marks)






3. Let P (n) be the proposition that: for all k, with 1 ≤ k ≤ n,

.nΣ = .n − 1Σ + .n − 1Σ.

k k − 1 k

(a) Prove that P (n) holds  for all n 1. (Note: it is possible to do this without using induction)

(10 marks)

We can compute n from the formula given in lectures, however this  can often require computing unnecessarily large numbers. For example,

100 = 253338471349988640 which can be expressed as a 64-bit integer,

but 100! is larger than a 512-bit integer. We can, however, make use of the equation above to compute n more efficiently.  Here are two algorithms

for doing this:

chooseRec(n, k) : chooseIter(n, k) :

if k = 0 or k = n : return 1 Let C be a n n array else : for m = 1 to n :

x := chooseRec(n 1, k 1) C[m][0]=C[m][m]=1

y := chooseRec(n 1, k) for j = 1 to m 1 :

return x + y C[m][j]=C[m 1][j 1]

+ C[m 1][j]

return C[n][k]


Let trec(n, k) be the running time for chooseRec(n, k), and let titer(n) be the running time for chooseIter(n, k). Let Trec(n) = max0≤k≤n trec(n, k) and Titer(n) = max0≤k≤n titer(n, k) (so Trec(n) ≥ trec(n, k) for all k, and likewise for Titer(n)).

(b) Give an asymptotic upper bound for Trec(