Foundations of Computer Science (a) We are interested in performing… Foundations of Computer Science (a) We are interested in performing o

Foundations of Computer Science (a) We are interested in performing… Foundations of Computer Science (a) We are interested in performing operations on nested lists of integers in ML. A nested list is a list that can contain further nested lists, or integers. For  example: [[3, 4], 5, [6, [7], 8], []] We will use the datatype: datatype nested_list = Atom of int | Nest of nested_list list; Write the code that creates a value of the type nested list above. [1 mark] (b) Write the function flatten that flattens a nested list to return a list of integers. [3 marks] (c) Write the function nested map f n that applies a function f to every Atom in n. [4 marks] (d) What is the type of f in Part (c)? [1 mark] (e) Write a function pack as xs n that takes a list of integers and a nested list; the function should return a new nested list with the same structure as n, with integers that correspond to the integers in list xs. Note: It is acceptable for the function to fail when the number of elements differ. Example: > pack_as [1, 2, 3] (Nest [Atom 9, Nest [Atom 8, Atom 7]]); val it = Nest [Atom 1, Nest [Atom 2, Atom 3]]: nested_list [6 marks] (f ) What does the data type nested zlist correspond to? [2 marks] datatype nested_zlist = ZAtom of int | ZNest of (unit -> nested_zlist list); (g) Write the function that converts a nested zlist to a nested list. [3 marks] 3 (TURN OVER) CST0.2019.1.4 SECTION B 3 Object-Oriented Programming (a) You are given the following implementation for an element of a list: class Element { int item; Element next; Element(int item, Element next) { super(); this.item = item; this.next = next; } @Override public String toString() { return item + ” ” + (next == null ? “” : next); } } (i) What does the statement super() mean? [1 mark] (ii) What is the meaning of this in the line this.item = item? [1 mark] (iii) What is the purpose of the annotation @Override? [2 marks] (iv) Rewrite the class to be immutable. You may assume that there are no sub-classes of Element. [2 marks] (b) Use the immutable Element class to provide an implementation of an immutable class FuncList which behaves like an int list in ML. Your class should include a constructor for an empty list and methods head, tail and cons based on the following functions in ML. Ensure that your class behaves appropriately when the list is empty. [6 marks] fun head x::_ = x; fun cons (x,xs) = x::xs; fun tail _::xs = xs; (c) Another developer changes your implementation to a generic class FuncList that can hold values of any type T. (i) This means that FuncList is no longer immutable. Explain why and what could be done to remedy this. [2 marks] (ii) Java prohibits covariance of generic types. Is this restriction necessary in this case? Explain why with an example. [6 marks] 4 CST0.2019.1.5 4 Object-Oriented Programming (a) What is an object? [2 marks] (b) Give four examples of how object-oriented programming helps with the development of large software projects and explain why each one is helpful. [8 marks] (c) Explain the meaning of the Open-Closed principle. [2 marks] (d) Draw a UML diagram for a design satisfying the Open-Closed principle and explain why it satisfies it. [8 marks] 5 (TURN OVER) CST0.2019.1.6 SECTION C 5 Numerical Analysis (a) Let f be a single variable real function that has at least one root ?, and that admits a Taylor expansion everywhere. (i) Starting from the truncated form of the Taylor expansion of f(x) about xn, derive the recursive expression for the Newton-Raphson (NR) estimate xn of the root at the (n + 1)th step. [1 mark] (ii) Consider the general Taylor expansion of f(?) about xn. Using big O notation for an appropriate Taylor remainder and denoting the NR error at the nth step by en, prove that the NR method has quadratic convergence rate. That is, show that en+1 is proportional to e 2 n plus a bounded remainder. State the required conditions for this to hold, paying attention to the interval spanned during convergence. [6 marks] (iii) Briefly explain two of the known problems of the NR method from an implementation standpoint or otherwise. [2 marks] (b) Let f(x) = x 2 ? 1. Suppose we wish to find the positive root of f using the Newton-Raphson (NR) method starting from an initial guess x0 ? 1. (i) Show that if x0 ? 1 then xn ? 1 for all n ? 1. [3 marks] (ii) Thus find an upper bound for NR’s xn+1 estimate in terms of xn and in turn find an upper bound for xn in terms of x0. [5 marks] (iii) Using the above, estimate the number of NR iterations to obtain the root with accuracy 10?9 for a wild initial guess x0 = 109 . [Hint: You may wish to approximate 103 by 210.] [3 marks] 6 CST0.2019.1.7 6 Numerical Analysis (a) You are given a system of real equations in matrix form Ax = b where A is non-singular. Give three factorization techniques to solve this system, depending on the shape and structure of A: tall, square, symmetric. For each technique, give the relevant matrix equations to obtain the solution x, and point out the properties of the matrices involved. Highlight one potential problem from an implementation (computer representation) standpoint. [Note: You do not need to detail the factorization steps that give the matrix entries.] [5 marks] (b) We want to estimate travel times between stops in a bus network, using ticketing data. The network is represented as a directed graph, with a vertex for each bus stop, and edges between adjacent stops along a route. For each edge j ? {1, . . . , p} let the travel time be dj . The following ticketing data is available: for each trip i ? {1, . . . , n}, we know its start time si , its end time fi , and also the list of edges it traverses. The total trip duration is the sum of travel times along its edges. We shall estimate the dj using linear least squares estimation, i.e. solve arg min? ky ? X?k 2 for a suitable matrix X and vectors ? and y. (i) Give an example of ticket data for a trip traversing 5 edges, and write the corresponding equation of its residual. [1 mark] (ii) Give the dimensions and contents of X, ?, and y for this problem. State a condition on X that ensures we can solve for ?. [3 marks] (iii) Give an example with p = 2 and n = 3 for which it is not possible to estimate the dj . Compute XT X for your example. [2 marks] (c) Let A be an n × n matrix with real entries. (i) We say that A is diagonalisable if there exists an invertible n × n matrix P such that the matrix D = P ?1AP is diagonal. Show that if A is diagonalisable and has only one eigenvalue then A is a constant multiple of the identity matrix. [3 marks] (ii) Let A be such that when acting on vectors x = [x1, x2, . . . , xn] T it gives Ax = [x1, x1 ?x2, x2 ?x3, . . . , xn?1 ?xn] T . Write out the contents of A and find its eigenvalues and eigenvectors. Scale the eigenvectors so they have unit length (i.e. so their magnitude is equal to 1). [6 marks] 7 (TURN OVER) CST0.2019.1.8 SECTION D 7 Algorithms (a) The Post Office of Maldonia issued a new series of stamps, whose denominations in cents are a finite set D ? N{0}, with 1 ? D. Given an arbitrary value n ? N{0} in cents, the problem is to find a minimum-cardinality multiset of stamps from D whose denominations add up to exactly n. In the context of solving the problem with a bottom-up dynamic programming algorithm. . . (i) Give and clearly explain a formula that expresses the optimal solution in terms of optimal solutions to subproblems. [Note: If your formula gives only a scalar metric (e.g. the number of stamps) rather than the actual solution (e.g. which stamps), please also explain how to obtain the actual optimal solution.] [4 marks] (ii) Draw and explain the data structure your algorithm would use to accumulate the intermediate solutions. [2 marks] (iii) Derive the big-Theta space and time complexity of your algorithm. [1 mark] (b) Repeat (a)(i)-(a)(iii) for the following problem: A car must race from point A to point B along a straight path, starting with a full tank and stopping as few times as possible. A full tank lets the car travel a given distance l. There are n refuelling stations so ? A, s1, s2, . . . , sn ? B along the way, at given distances d0 = 0, d1, d2, . . . , dn from A. The distance between adjacent stations is always less than l. The problem is to find a minimum-cardinality set of stations where the car ought to refill in order to reach B from A. [7 marks] (c) Which of the two previous problems might be solved more efficiently with a greedy algorithm? Indicate the problem and describe the greedy algorithm. Then give a clear and rigorous proof, with a drawing if it helps clarity, that your greedy algorithm always reaches the optimal solution. Derive the big-Theta time complexity. [6 marks] 8 CST0.2019.1.9 8 Algorithms (a) Consider a Binary Search Tree. Imagine inserting the keys 0, 1, 2, . . . , n (in that order) into the data structure, assumed initially empty. (i) Draw a picture of the data structure after the insertion of keys up to n = 9 included. [2 marks] (ii) Clearly explain, with a picture if helpful, how the data structure will evolve for arbitrary n, and derive the worst-case time complexity for the whole operation of inserting the n + 1 keys. [2 marks] (b) Repeat (a)(i) and (a)(ii) for a 2-3-4 tree, with some scratch work showing the crucial intermediate stages. [2+2 marks] (c) . . . and for a B-tree with t = 3, again showing the crucial intermediate stages. [2+2 marks] (d) . . . and for a hash table of size 7 that resolves collisions by chaining. [2+2 marks] (e) . . . and for a binary min-heap. [2+2 marks] 9 (TURN OVER) CST0.2019.1.10 9 Algorithms A Random Access Queue supports the operations pushright(x) to add a new item x to the tail, popleft() to remove the item at the head, and element at(i) to retrieve the item at position i without removing it: i = 0 gives the item at the head, i = 1 the following element, and so on. (a) We can implement this data structure using a simple linked list, where element at(i) iterates from the head of the list until it reaches position i. (i) State the complexity of each of the three operations. [1 mark] (ii) A colleague suggests that, by defining a clever potential function, it might be possible to show that all operations have amortized cost O(1). Show carefully that your colleague is mistaken. [6 marks] (b) We can also implement this data structure using an array. The picture below shows a queue holding 4 items, stored within an array of size 8. When new items are pushed, it may be necessary to create a new array and copy the queue into it. The cost of creating an array of size n is ?(n). head item item item tail item 0 1 2 3 4 5 6 7 (i) Give pseudocode for the three operations. Each operation should have amortized cost O(1). [6 marks] (ii) Prove that the amortized costs of your operations are indeed O(1). [7 ma.DatabasesSuppose that we have a relational database with the following tables.Table Primary KeyMovies(mid, title, year) midPeople(pid, name) pidGenres(gid, genre) gidActsIn(pid, mid) pid, midHasRole(pid, mid, role) pid, mid, roleHasGenre(gid, mid) gid, midIn tables ActsIn and HasRole, pid is a foreign key into People and mid is a foreignkey into Movies. In table HasGenre, mid is a foreign key into Movies and gid is aforeign key into Genres.Note that this database is similar to, but not the same as, the examples used inlectures and the database used for practicals.(a) For the table ActsIn, carefully explain what is meant by saying that pid is aforeign key into People. [2 marks](b) Discuss potential problems this database might suffer due to data redundancy.[2 marks](c) Write an SQL query that produces triples of the form genre1, genre2, totalthat count the number of movies associated with a pair of distinct genres. Eachpair of genres should only appear once in the result. That is, if the triplegenre1, genre2, total appears in the result, then the triple genre2, genre1,total should not. [5 marks](d) Suppose that kid is the pid associated with Kevin Bacon. Write SQL thatreturns every pid for actors with a Bacon number of 2. This SQL should notinclude views. [5 marks](e) Simplify the SQL of Part (d) using views. [6 marks]2CST0+CST1.2019.3.32 DatabasesThis question develops an Entity-Relationship (ER) model for a new database. Thedatabase will be called Meta-ER because it contains Entity-Relationship models! Theentities of our ER model areentity name descriptionModel each Model represents an ER modelEntity each Entity represents an ER entityRelationship each Relationship represents an ER relationshipAttribute each Attribute represents an attributeEach of our entities will have an id attribute (the primary key) and a name attribute.In addition, the Attribute entity will have a type attribute indicating the data typeof the Attribute:entity name attributesModel id, nameEntity id, nameRelationship id, nameAttribute id, name, type]We start with one many-to-many relationship ModelHasEntity between Model and Entity that indicates which entities belong to the Model. For example, wemay have a model called “MoviesModel” related to the entities presented in lecture, or a model “Trucks-R-Us” for a transportation company. ModelHasEntityis many-to-many to allow different models to share entities. Your task now is tocomplete this ER model and consider implementing it in a relational database.(b) Define a relationship between Entity and Attribute called EntityHasAttribute.What cardinality should this relationship have? Justify your answer.[2 marks](c) Define a relationship between Relationship and Attribute called RelationshipHasAttribute. What cardinality should this relationship have? Justify youranswer. [2 marks](d) Define a relationship called RelationshipRelatesEntity between Relationship andEntity. What cardinality should this relationship have? Justify your answer.[2 marks](e) Should the relationship RelationshipRelatesEntity itself have attributes? Justifyyour answer. Let us assume that all of our relationships are binary. [2 marks](f ) Describe a relational implementation of your ER model, including keys andforeign keys. [4 marks](g) Given your relational implementation, write an SQL query that takes a modelname mname and returns all triples ename1, rname, ename2 where ename1 andename2 are names of entities in the model mname, and ename1 is related toename2 via the relationship with name rname. [8 marks Stirling’s approximation n! ? (2?) 1 2 n n+ 1 2 e ?n] 2 CST.93.2.3 6 In a chip factory three machines manufacture 25%, 35%, and 40% of the total production. Of their output, 5%, 4%, and 2% respectively are rejected as faulty. What is the probability that from a collection of chips drawn at random from the output two which are faulty were made on the same machine? What is the probability that three faulty chips were all made on different machines? SECTION C 7 Discuss the requirements of an Automatic Teller Machine (ATM) service under the headings: (a) security; (b) availability of service; (c) integrity of stored data; (d) procedure for dispute resolution. 3 [TURN OVER CST.93.2.4 8 Consider these ML functions for performing arithmetic in radix k, where k is an ML variable whose value is a positive integer. fun value [] = 0 | value (x::xs) = x + (k*value xs); fun carry c [] = [c] | carry c (x::xs) = ((c+x) mod k) :: carry ((c+x) div k) xs; fun sum c [] ys = carry c ys | sum c (x::xs) [] = carry c (x::xs) | sum c (x::xs) (y::ys) = ((c+x+y)mod k) :: sum ((c+x+y)div k) xs ys; (a) State and justify the rule of structural induction for lists. (b) Your client would like you to prove the correctness of sum, expressed by the property value(sum 0 xs ys) = value(xs)+value(ys). Generalize this formula so that it permits a useful structural induction proof, explaining your reasons. (c) Prove the base case of the structural induction. (d) Prove the inductive step of the structural induction. (e) What does the correctness proof say about the case where k equals 1? Discuss whether other properties are necessary to ensure correctness. Proofs may assume the analogous correctness property for carry and standard mathematical laws. State these assumptions clearly. (1 mark) StudentTotalScore[1:30] (1 mark) [2] (b) (i) – outside loop zeroing total for loop (sum in example below) – loop for all students – input name and all test scores – in loop adding a student’s total – storing the total – inside loop printing student’s name and total – outside loop calculating class average – printing class average sample algorithm: Sum Å 0 FOR Count Å 1 TO 30 INPUT Name StudentName[Count] Å Name INPUT Mark1, Mark2, Mark3 StudentMarksTest1[Count] Å Mark1 StudentMarksTest2[Count] Å Mark2 StudentMarksTest3[Count] Å Mark3 Total Å Mark1 + Mark2 + Mark3 StudentTotalScore[Count] Å Total Sum Å Sum + Total PRINT StudentName[Count], StudentTotalScore[Count] NEXT Count ClassAverage = Sum/30 PRINT ClassAverage [8] (ii) any relevant comment with regards to efficient code (e.g. single loop) [1] (c) Many correct answers, these are examples only. 1 mark per data set and reason Set 1: 20, 25, 35 Reason: valid data to check that data on the upper bound of each range check is accepted Set 2: 21, 26, 36 Reason: invalid data to check that data above the upper bound of each range check is rejected [2] 3 © UCLES 2019 0478/02/SM/20 [Turn over (d) (i) Maximum 5 marks in total for question part Maximum 3 marks for algorithm Description (max 3) – set variable called HighestScore to zero and variable called BestName to dummy value – loop 30 times to check each student’s total score in turn – check student’s score against HighestScore – if student’s score > HighestScore then – « replace value in HighestScore by student’s score and store student’s name in BestName – output BestName and HighestScore outside the loop Sample algorithm (max 3): HighestScore Å 0 BestName Å “xxxx” (1 mark) FOR Count Å 1 TO 30 IF StudentTotalScore[Count] > HighestScore (1 mark) THEN HighestScore Å StudentTotalScore[Count] BestName Å StudentName[Count] (1 mark) ENDIF NEXT Count (1 mark) PRINT BestName, HighestScore (1 mark) If algorithm or program code only, then maximum 3 marks [5] (ii) comment on which student(s)’ name will be output e.g. The first student with the highest score will be output [1] 4 © UCLES 2019 0478/02/SM/20 Section B 2 (a) 1 mark for value of c and message 51020: value of c: 5 message: PIN OK (1 mark) 5120: value of c: 4 message: error in PIN entered (1 mark) [2] (b) length check [1] 3 Engine Count Number Size Average OUTPUT 0 0 0 1.8 1.8 1 1 2.0 3.8 2 2 1.0 4.8 3 1.3 6.1 4 1.0 7.1 5 2.5 9.6 3 6 2.0 11.6 4 7 1.3 12.9 8 1.8 14.7 5 9 1.3 16.0 10 -1 1.6 1.6, 5 (1 mark) (1 mark) (1 mark) (1 mark) (1 mark) (1 mark) [6] 4 1 mark for each error identified + suggested correction line 5: this should read IF x > h THEN h = x line 7: PRINT h should come after the end of the repeat loop line 8: this should read UNTIL c = 20 or UNTIL c >= 20 or UNTIL c > 19 [3] 5 © UCLES 2019 0478/02/SM/20 [Turn over 5 (a) 5 [1] (b) Field: At Risk Age in Years Type Map Position Table: TREES TREES TREES TREES Sort: Show: 9 9 Criteria: True >100 or: One mark per correct column. [4] 6 (a) marking points: the way to find and print the largest value a 1 mark the way to find and print the largest value b 1 mark the way to find and print the largest value c 1 mark sample algorithm: INPUT a, b, c IF a > b AND a > c THEN PRINT a (1 mark) ELSE IF b > c THEN PRINT b (1 mark) ELSE PRINT c (1 mark) [3] (b) marking points: loop construct 1 mark check if number is an integer 1 mark counting the number of integers input 1 mark output count value (outside the loop) 1 mark sample algorithm: FOR x ? 1 TO 1000 (1 mark) INPUT Number Difference ? INT(number) – Number (1 mark) IF Difference = 0 THEN Total ? Total + 1 (1 mark) NEXT x PRINT total (1 mark) (NOTE: alternative to lines 3 and 4: IF INT(Number) = Number THEN Total ? Total + 1 (2 marks) ) [4] (c) Description of any two sets of test data. Many correct answers, these are examples only. 1000 whole numbers to ensure that loop works properly 900 whole numbers and 100 numbers with decimal places to ensure that the routine distinguishes correctly [2] 6 © UCLES 2019 0478/02/SM/20 7 (a) 7 [1] (b) Hg, Cs [2] (c) Element symbolCST0.2019.1.3 2  Computer Science Engineering & Technology Information Security COMMUNICAT 340 Share QuestionEmailCopy link Comments (0)