Exam 2019 with answers PDF

Preview

Summary

its an classroom exam...

Description

UNIVERSITY OF HERTFORDSHIRE

Academic year: 2019-2020 Exam Session: Semester A

School/Dept:

Computer Science

Module code:

7COM1028

Module title:

Computational Algorithms and Paradigms

Duration of Exam: 180 minutes

THE FOLLOWING IS PROVIDED FOR THIS EXAMINATION: ONE Answer book. Continuation answer sheets can be requested from an invigilator.

INSTRUCTIONS TO CANDIDATES:

This papers consists of SIX questions on FIVE pages including this page. Answer FOUR questions. Ensure you write your exam number on any sheets which are to be handed in. University approved calculators allowed? YES Are question papers allowed to be taken at the end of the exam? YES

Page 1 of 9

Question 1 a)

The Linear Search Algorithm and the Binary Search Algorithm are two examples of algorithms that can be used to find a particular value within a finite collection of numeric data. Explain what is meant by a i). linear search algorithm ii). binary search algorithm (8 marks)

Linear search algorithm applied to finite collection of data, which is not ordered (1 mark), has distinct values, (1 mark), and is inspected sequentially (1 mark). Binary search algorithm applied to finite collection of data, which is ordered (1 marks), has distinct values, (1 mark), inspected by repeatedly finding medians (1 mark) and establishing whether the sought value is in the upper or lower half of data being inspected (1 mark) until sought value is found (1 mark). (8 marks)

a)

Let N denote the number of elements in a collection of data, let m denote a particular data element being searched for and let X denote a random variate for the number of steps taken made to find m. Show that: i). for a linear search algorithm the expected number of steps E ( X ) 

N 1 and 2

that the worst case complexity for the number of steps taken to find m = O(N) (12 marks) ii). for the binary search algorithm the worst case complexity for the number of steps taken to find m = O(log2 (N)) (5 marks)

Page 2 of 9

i). Definition for E(X) (2 marks), probability = 1/N (uniform distribution) (2 marks), sum of first N positive integers (2 marks), final answer (2 marks) N

E (X )   P (X  xi )xi  i 1

1 1 N N 1 (1 2  ... N )  (N  1)  N N 2 2

For the worst case in this example X = N for all values of N > 0. (2 marks). Diagram for worst case complexity (2 Marks). Definition for worst case complexity (4 marks) involving n0, k, f(n) and g(n)  n0 , k   n0 , f ( n)  k. g( n)  f ( n)  O( g( n)) (accept alternative version without quantifiers) (Mark to a maximum of 12 marks) ii). Accept 2x  N  x log2 (2)  log2 (N )  x  log2 (N ) (2 marks for each part plus 2 marks for extra observations) (Mark to a maximum of 5 marks) Question 2 The Functional paradigm was introduced in the 1960’s to address a range of different types of problem from a range of different disciplines. Two such disciplines were symbolic computation and natural language processing. Initial functional programming languages such as LISP have been described as examples of impure rather than pure functional languages. a) Compare and contrast the pure functional paradigm to the imperative paradigm. Following your initial observations on the two paradigms extend your discussion to include i. Source, domain, range and codomain ii. an explanation of the different types of relation that exist between such sets with examples for each type of relation iii. a definition for a function in terms of its 1. type 2. λ – expression (15 Marks) Imperative paradigm: state based, loops, procedural abstraction, Turing complete, (4 Marks) Functional paradigm: not state based, no loops, conditionals, recursion, functional approach, λ-calculus based, Turing complete, …(7 Marks) Pure: do not support notions of variable, assignment and looping unlike impure functional languages (3 Marks) Source, domain, range and codomain (1 mark each) Relation: 1-1, many-1, 1-many, many-many relation (4 marks). Function 1-1, many-1 relation (2 Marks), 2 marks for each example. (Mark to a maximum of 15 Marks) b) Using an example of your own describe how Lisp and Haskell could be used to accomplish a task involving i. functional composition, and ii. recursion. (10 Marks) (3 marks each, for each language. Mark to a maximum of 5 Marks)

Page 3 of 9

Question 3 a) The following Java code has been written relating to payment for parking in a local car park. The code employs the use of fields, classes, methods, accessors, constructors and mutators. Explain what is meant by each of these terms and identify examples of each of these in the given code. import java.util.* ; public class ParkingMachine { public static void main(String args[ ]) throws exception { private int price ; private int balance ; private int total ; public ParkingMachine(int cost) { price = cost ; balance = 0 ; total = 0; } public int getPrice( ) { return price ; } public int getBalance( ) { return balance ; } public void insertMoney(int amount ) { balance = balance + amount ; } } } (8 Marks) Fields (1 mark), class (1 mark), methods (2 marks), accessors (1 mark), mutators (1 mark) Constructor (2 marks) b) Describe two similarities and two differences between the object oriented paradigm and the imperative paradigm. What advantages, if any, do you feel the object oriented paradigm offers over the imperative paradigm. Where possible provide examples to justify your claims. (9 Marks) Similarities, differences, advantages and examples (3 marks each). Mark to max of 9 marks. c) Calculate McCabes cyclotomic complexity metric for the following code segments: i. a for loop followed by a do-while loop ii. an if control structure containing a nested do while loop Include appropriate flowcharts for each code segment. (8 marks)

Page 4 of 9

Use arcs – nodes + 2. 2 marks for each calculation consistent with flowchart drawn. For flowcharts: 2 marks for i., and 4 marks for ii. Mark to a maximum of 8 marks.

Page 5 of 9

Question 3 a) What form of type checking is used by Python, and what form of checking is used by Java? What are the implications for the programmer in each case? (7 marks) • Java uses static type checking (except for some sub-type use) 1 • static: at compile tim e, usually requires explicit type constraint on variables etc. efficient no runtime check-

ing, vastly reduces possiblities of runtime errors 3 • Python uses dynamic run-time type checking 1 • dynamic: variables hold any value type but to prevent inappropriate operations there are

runtime checks. More flexibility, programs require less design, it is easier to incrementally develop them. 3 (up to 7 mar ks)

b) What is parametric polymorphism and why is it useful? (5 marks) • One named operation that can be safely applied to values of more than one type, the same name selects

on function that can be applied to more than one type. 2 • lots of code reuse – safely for im plementor 2 • one name for user of common code 1

(5 marks)

c) What is ad-hoc polymorphism and why is it useful? (5 marks) • one name can name different functions, which one is referred to is deter mined by the

type of the data it is applied to 3 • provides a uniform interface to a range of data types for programmer that is using functions 2

(5 marks)

d) What does it mean for one type C to be a subtype of another type P for safe type checking? (3 marks) For type checking it means that it must be safe to use type C anywhere that P is needed, that all ops. that can be safely applied to P will work on C (3 marks)

e) What is private inheritance in C++ and what problems does it solve? (5 marks) • allows child to use public and protected bits of parent but clients can’t. 2 • 2 of the things inheritance can give: sub-typing and structure sharing. sometim es only

structure sharing wanted not subtyping, derived class might have fewer or differently named operations from parent. 2 • if derived was always treated as sub-type then it would be unsafe so private inheritance allows structure sharing but stops sub-typing. 1 (5 marks)

Page 6 of 9

Question 4 Propositional and predicate logic form a formal basis for the logic (declarative) paradigm. A particular variant of predicate logic is the Horn Clause which underlies the syntax of the programming language Prolog. a) Define the terms Horn clause, Resolution (for a pair of Horn clauses), and Unification. Include an example of each. Comment on the claim that not every predicate may be expressed as a Horn clause. Include a justification for your claim. (12 Marks) Horn clause (2 marks), Resolution (2 marks), and Unification (2 marks), examples (2 marks each). Comment (1 mark), Justification (up to 5 marks, subject to depth and detail of justification). Mark to a maximum of 12 marks. b) Alex, Bob and Mami speak different languages. Given that Alex speaks French, Bob speaks Italian and Mami speaks both French and Italian complete the following code extract. You may assume that L denotes language. speaks(alex, french) speaks(…, …) speaks(…, …) speaks(…, …) talkswith(Person1, Person2) :- speaks(Person1, L), speaks(… , L), … \= Person2. Explain what it means for a Prolog rule to succeed. Give an example illustrating when the above Prolog rule succeeds and one when the Prolog rule fails. What query could be issued to establish who speaks Italian? (13 Marks) speaks(alex, french) speaks(bob, italian) speaks(mami, french) speaks(mami, italian) talkswith(Person1, Person2) :- speaks(Person1, L), speaks(Person2, L), Person1 \= Person2. 1 mark for each correct entry above. (2 Marks) Example of success Person1 = alex, Person2 = mami since both speak L = french. (2 Marks). Example of fail Person1 = alex, Person2 = bob neither share a common language i.e. value for L (2 Marks). Query: ? – speaks(Who, Italian) (2 marks) Who = bob, Who = mami , (2 marks) Mark to a maximum of 13 marks)

Page 7 of 9

Question 5 a) Compare and contrast Polyas’ procedure for deriving a solution to a given problem, with another procedure (of your own choosing), that has been designed for deriving a solution to a given problem. Include an explanation for each part of the Polya procedure. (8 Marks) Discussions in areas relating to understanding the problem, devise a plan, carry out the plan, assessing the result, description documentation. 1 mark for each area. Up to 4 marks for comparison. Mark up to a maximum of 8 marks. b) Using the HTTLAP procedure or otherwise derive two appropriate procedural algorithms, (one using an appropriate formula, the other not using a formula) for the tower of Hanoi problem. Provide a final completed solution in pseudo-code. (12 Marks) Algorithms generated via HTTLAP (2 Marks for each section). Additional 4 marks for final pseudo code solutions. Mark to a maximum of 12 Marks. c) Compare and contrast the approach taken above with the tower of Hanoi problem to one that would be generated in another paradigm of your own choosing. (5 Marks) Various options available, 1 mark for each point made to a maximum of 5 Marks. Question 6 The Quantum Programming Paradigm has been in existence now for more than twenty years with quantum based languages based on the imperative, functional and concurrent approaches to solving problems a) Compare and contrast the concept of information processing employing bits, cbits, qubits and logic gates for Turing and quantum Turing based machines. (12 Marks) (2 Marks) for TM, (4 Marks) for QTM analogue, bits and cbits |0>, |1>, and/or |+>, |- >, (1 Mark each), qubits as superposition of basis (2 Marks). 2 Marks for each logic gate, e.g. Pauli gates, Hadamard gate, CNOT gate (extra 2 Marks) Mark to a maximum of 12 Marks. a) The quantum teleportation protocol using EPR and classical channels is now an essential ingredient in the successful development of quantum based networks. Draw, with explanation, the circuit used in the teleportation protocol. The following code is taken from the quantum based LanQ program for the teleportation protocol. Explain what is meant by the given code indicating which part of the circuit the code relates to. #library "library.libq" ………. void bert(channelEnd[int] c1, qbit stateToTeleportOn) { int i; i = recv(c1); if (i == 1) { Sigma_z(stateToTeleportOn); } else if (i == 2) { Sigma_x(stateToTeleportOn); } else if (i == 3) { Sigma_x(stateToTeleportOn);

Page 8 of 9

Sigma_z(stateToTeleportOn); } dump_q(stateToTeleportOn); }

(13 Marks) Diagram (4 marks). Explanation: input, CNOT, Hadamard, measurement, LOCC operation, Adjustment. One mark for each explanation given. One mark for each relation established to teleportation protocol. Mark to a maximum of 13 Marks.

Question 4 (25 Marks) a)

b)

c)

Explain in your own words the significance of the introduction of asymmetric key cryptography to the key distribution problem experienced by users of symmetric key cryptosystems. (8 marks) Describe the 8884 quantum key exchange protocol. Include in your explanation an account of at least two mechanisms employed in the protocol (classical or quantum) that make it particularly effective against an eavesdropper. (12 marks) What features of the 8884 quantum protocol make it particularly problematic to employ as an encryption mechanism for passing messages between a sender and receiver. (5 Marks)

#library "library.libq" ………. void bert(channelEnd[int] c1, qbit stateToTeleportOn) { int i; i = recv(c1); if (i == 1) { Sigma_z(stateToTeleportOn); } else if (i == 2) { Sigma_x(stateToTeleportOn); } else if (i == 3) { Sigma_x(stateToTeleportOn); Sigma_z(stateToTeleportOn); } dump_q(stateToTeleportOn); }

(13 Marks) Diagram (4 marks). Explanation: input, CNOT, Hadamard, measurement, LOCC operation, Adjustment. One mark for each explanation given. One mark for each relation established to teleportation protocol. Mark to a maximum of 13 Marks.

Page 9 of 9...