1    Marking Rubric

Write your answers in overleaf and include the shareable overleaf link below (replace the link below to this document with a link to your document), in case there is error in your formatting.

● You are required to submit your pdf.  Export this from overleaf with correct formatting and symbol generation or your work will not be marked. For proofs it is recommended you provide a sample case first

● Half marks for working or explanation for a proof.  The requirement is to include a brief and clear explanation of your work in your own words.

● Half marks for correct answer except where only explanation is required.

● Where a question has many parts, each part has equal value. Your result will be rounded up to nearest half mark

The original of this sheet is found https://www.overleaf.com/read/nrtwrqmgcptp

Please replace the link above with the link to your answer sheet in overleaf

2    Questions

1.  (4 points)  Proof of Correctness Week 4.8 and revised week 6 Workshop

Given the following Algorithms derive their correctness (or not) by proof of the required invariant

(a)  Fibonnacci(n){

n ≥ 0 and Fibonnacci(n) = ((1 +′5)/2)n + (1 一 ′5)/2)n )/′5

if  n=0:  return  0

if  n  =  1:  return  1

return  Fibonnacci(n-1)  +  Fibonnacci(n-2)

}

(b)  searchDictionary(word,node){

0c e word : c e Alphabet n \ * \ .

word = c1 c2 ..cn    =→  0 ci , ci+1  {if c1 ...ci  e Dictionary and ci+1  e/ Dictionary then word e/ Dictio- nary}. Else word e Dictionary

word=word+"*"

for  j  in  range  (0,  len(word))

c=word[j:j+1]

if  c  in  node .children:

index=0

while  c!=node .child[index]:

index+=1

else  return  false

node=node_child[index]

return  true

}

(c) public static int floor(int nums[], int key){

A key e Z A i e range (0,nums.length) A nums[i] ≤ key and key < nums[i+1], floor(nums,key)= i

int  listIndex=0;

int  r=nums .length-1;

while(listIndex<=r){

int  approxIndex=listIndex+(r-listIndex)/2;

if(nums[approxIndex]>=key)

r=approxIndex-1;

else

listIndex=approxIndex+1;

}

return  listIndex;

}

2.  (3 points)  Primes - Related to Proofs week 1 and 2.

(a)  Prove there are infinitely many primes

(b)  Using the Sieve of Eratosthenes, what is the worst case complexity for finding the prime factors of

a number of magnitude N.

(c)  Prove that whenever a prime p does not divide the square of an integer, it also does not divide the original integer. i.e. p \|x2   =→  p \|x

3.  (3 points)  Partition - Coding exercise from Week 6

Describe an efficient in-place algorithm called Partition-Even-Odd(A) that partitions an array A in even and odd numbers. The algorithm must terminate with A containing all its even elements preceding all its odd elements.

For example, for input A = [7, 17, 74, 21, 7, 9, 26, 10],

the result might be A = [74, 10, 26, 17, 7, 21, 9, 7].

Partition-Even-Odd must be an in-place algorithm.

What do you think this mean about your algorithm?

(a) Write the pseudo-code for Partition-Even-Odd.

(b)  Characterize the complexity of Partition-Even-Odd. Briefly justify your answer.

(c)  Formalize the correctness of the partition problem as stated above, and prove that Partition-Even- Odd is correct using a loop-invariant (as repeated Week 6 workshop).

4.  (1 point)  Do these matrices represent equivalence relations.  See Week 5 and repeated Workshop Week 6.

Explain your answer

(a)   ┌ ┐

'1    0    0'

┌ ┐

(b)   '(')0    1    1   0'(')

'0    1   0    1'

(c)   ┌ 0一┐

'一1    0    1'

5.  (3 points)  Proof by Induction Week 4

Prove using weak or strong induction as needed. State which one you use

(a)  Prove that every positive integer n has a binary expansion.   Namely, that there exists integers ci  e {0, 1} such that n=     ci 2i

(b)  Let {ai } be a sequence of sequence of real numbers such that 0 i,j ai+j  ≤ ai + aj

Prove that      ai /i ≥ an

(c)  Prove by strong induction that if a country has n cities where any two cities are connected by a one-way road, there is a route that passes through every city.

6.  (3 points)  Closed forms - discussed since Week 4

Solve the following equation for the closed form of this expression:

ak  = 4 . ak — 1  + 5 . ak —2

That is find the nth term in terms of n, independent of previous terms except a0  and a1

7.  (3 points)  Equivalence Relations Week 5

Prove this statement from the definition of an equivalence relation:

Let A be a nonempty set and let R be an equivalence relation on the set A . Then, 0 ae A, a e [a].

0 a,b e A, a R b ←→ [a]=[b]

For each a,b e A, [a]=[b] v [a]∩ [b] = u

Also prove the collection C of all equivalence classes determined by R is a partition of the set A.

8.  (4 points)  Cryptography - extension from Week 6 Seminar Consider a consequence of Euclid’s Lemma:

0 a,b,c e Z, gcd (a,b) =1 A a | bc → a | b and Fermat’s Little Theorem:

If p is any prime number and a is any integer such that p /|a =→  ap=1= 1 (mod p ).

Show how these statements are used to show an RSA cypher will work.  It is possible in RSA cryptog- raphy to encode a cypher with (pq, e) as public key, by using

C=Me  (mod pq)

and then decode the cypher with d=-e (mod (p-1)(q-1)), using M = Cd  (mod pq)

9.  (6 points)  Algorithm - Based on work on graphs since week 1, mostly since week 3.

Consider the following Algorithms and explain why they are not sufficient to solve the problem Simply a description or code for the standard algorithm will receive zero marks .

(a)  Find Shortest Path to Node

To search for shortest path when the edges are different length you can use Breadth First or Depth First Search. The BFS and DFS are explained here