crt Write a Buffer interface defining an opaque object type, T,…

Question Answered step-by-step crt Write a Buffer interface defining an opaque object type, T,… crtWrite a Buffer interface defining an opaque object type, T, with the following methods: init: taking an argument specifying the buffer size and returning a suitably initialized object put: inserting a single character into the buffer get: extracting a single character from the buffer [4 marks] Sketch a corresponding implementation giving (a) the concrete revelation of the types [4 marks] (b) the three default methods j (t)} of continuous basis functions by projecting f(t) onto them. We express these projections in bracket notation denoting Explain what is happening. [5 marks] (b) Now give an expression for computing f (n) (t), the nth derivative of f(t) with respect to t, in terms of the same projections and continuous basis set. (You may assume the existence of all derivatives.) Explain your answer. [5 marks] (c) Now consider a linear, time-invariant system with impulse-response function h(t), having time-varying input s(t) and time-varying output r(t): s(t) ?? h(t) ?? r(t) In the case that the input is the complex exponential s(t) = exp(iµj t) (where i = ? ?1 and µj is a constant), what can you say about the output r(t) of such a system? [5 marks] (d) If the input s(t) has been represented in terms of a set of complex exponentials ?j (t) = exp(iµj t) as described at the beginning of this question, is it possible for different complex exponentials (not included in this set) to appear in the output r(t) when it too is represented in terms of complex exponentials? Justify your answer. [5 marks] 3 [TURN OVER CST.96.3.4 4 Compiler Construction Describe what is meant by a phrase structured grammar and a context free grammar. [3 marks] Describe an algorithm to calculate the set LT (P) of all terminal symbols that can start a string derived from the non-terminal P using one or more productions of a given context free grammar. Illustrate your answer by calculating LT sets for the following grammar: S -> U V V -> + U V | U -> X W W -> * X W | X -> ( S ) | n [6 marks] Describe an algorithm to calculate the set FOLLOW(P) of terminal and non-terminal symbols for a given context free grammar, where * FOLLOW(P) = { X | S => … P X … } i.e. all symbols that can follow P in a sentential form derived from the sentence symbol S. Illustrate your answer by calculating the FOLLOW sets for the grammar given above. [6 marks] Outline possible ways in which the space used by the Action and Goto matrices of an SLR(1) parser can be reduced.  A transaction processing system for a banking application is to be implementedusing object semantics. Bank account objects include the following among theiroperations:credit (account id, amount)debit (account id, amount)add interest (account id)By defining “transactions” based on this example, show what is meant by(a) a non-serialisable execution schedule [3 marks](b) a non-strict execution schedule leading to a cascading abort [3 marks]Explain the ACID properties of transactions, drawing on the above application forexamples. Indicate which properties are concerned with failure resilience and whichwith concurrency control. [8 marks]Again using the above application for examples, explain concurrency controlbased on(a) two-phase locking [3 marks](b) time-stamp ordering [3 marks]4CST.94.6.58 DatabasesDescribe how a data model is represented in a relational database, and explain howone might specify a relational database schema. [5 marks]What is meant by a referential integrity constraint in a relational database?[3 marks]Each year the number of tourists coming to Cambridge increases by 10%. Mostof the pressure falls on a limited number of identified sites in the city centre. TheTourist Board has restricted the size of any group visiting such a site to 20, andrequires a group of ten people or more to get a permit in advance. Most bookingsare made either by tour operators or directly by independent guides: the TouristBoard will arrange guides for groups if asked to do so.A database is being installed to coordinate bookings and to provide informationabout the opening times of sites. Each site has separate opening times for summerand winter (owing to college autonomy, changes of season differ from site to site).Permits are issued to start on the hour or on the half-hour: they are valid eitherfor 1 hour or for 2 hours, the duration being fixed for each site. The final permitsof each day are timed to expire at the site’s closing time. Each site has a fixedcapacity, and no booking can be accepted that would cause it to be exceeded. Thecharge for a permit depends only on the site and the season. (Occasionally sitesare closed for several hours during the normal opening period, for example whenrecording is taking place in King’s College Chapel. The protocol is to inform theTourist Board at least 6 months in advance.)The Tourist Board issues permits to visit an identified site at a given time on agiven day, specifying the booking agent and the number in the group. Bookingscan be made up to 6 months beforehand. Permits are issued to registered touroperators and guides on account, but in all other cases payment must be made inadvance. The data held for registered guides includes not only account details butalso their working hours and charges.Design a schema for the relational database that is to record this information forthe Tourist Board. You may find it helpful to use domain types DATE, TIME andMONEY in addition to standard programming language datatypes. You do not needto specify the transactions that maintain the database, but you should state clearlyany assumptions that influence the schema design. (a) Various languages provide a built-in ‘eval’ operator which evaluates anexpression passed as an argument. Discuss the extent to which this: (i) fitswith existing language features, naming languages or classes of languages forwhich it is easy or hard to implement; (ii) easily deals with variable scoping;(iii) is a security risk. [4 marks](b) (i) Explain and justify what goes wrong when the following code is given to aStandard ML system:fun id x = x;val fnlist = ref [id];fnlist := (fn x=>x+1) :: !fnlist;fnlist := Math.sqrt :: !fnlist;print (hd(!fnlist)(1))(ii) Explain, giving an example, a related problem involving polymorphicexceptions.[5 marks](c) (i) Explain the concept of a “value type” in an object-oriented language,including which, if any, primitive and non-primitive types in Java can beseen as value types.(ii) Discuss to what extent a programmer can use final to create value types inJava, and whether this implementation gives the expected space and timeusage. [Hint: You may find it useful to discuss arrays of complex numbers.][5 marks](d) An implementation of finite sets of natural numbers in Standard ML uses intlist as its representation. However, certain client code has been found to bebuggy, because it misuses :: to add elements (creating duplicates) and lengthto obtain the number of elements (miscounting duplicates).(i) Explain how ML modules might be helpful for addressing such bugs.(ii) Use the ML modules language to create a type natset which uses int listinternally but only exposes operations (a) to create an empty set, (b) to(functionally) insert one (non-negative) element into a set, (c) to sum theelements in a set, (d) to count the number of elements in a set. No otheroperation may create or manipulate an natset value.[6 marks]3 (TURN OVER)CST1.2018.7.42 Economics, Law and Ethics(a) Describe the possible market failures affecting anti-virus software firms in thelate 1980s and early 1990s, when viruses were a new threat to computer systemsand dozens of firms started up to offer anti-virus software. [5 marks](b) Describe how the incentives facing anti-virus software firms had changed 10 yearslater once the industry had consolidated into a handful of large firms. How mightthis affect attacker behaviour? [5 marks](c) How will the incentives have changed in recent years with the spread of onlinebanking and crypto currencies? [5 marks](d) How do you expect the anti-virus industry to change as computing shifts fromPCs and laptops to phones and tablets? What about the impact of systemsembedded in durable consumer goods such as cars? [5 marks]4CST1.2018.7.53 Formal Models of LanguageConsider the following grammar:S ? NP VPNP ? N SNP ? NVP ? V NVP ? VN ? {Alice, cats}V ? {saw, grinned}(a) The grammar can be used to generate the following sentences:(i) Alice saw cats(ii) Cats Alice saw grinnedDraw derivation trees for both of these sentences. [2 marks](b) What is the longest sentence that can be generated by the grammar? Describethis sentence. [2 marks](c) Is the language generated by the grammar a regular language? Provide a prooffor your answer. [8 marks](d) A psycho-linguistic experiment shows that, by the 2nd word in the sentence,Part (a)(ii) is harder to process than the sentence Part (a)(i). Yngvehypothesised that a speaker’s short-term memory functions as a stack. Explainhow this hypothesis might account for the experimental results by drawing thestack arising from a top-down parse of the two sentences. [4 marks](e) How might the sentence in Part (a)(ii) be altered so that it has the same meaningbut is easier to process? Explain your reasoning. [4 marks]5 (TURN OVER)CST1.2018.7.64 Further Graphics(a) Here are two methods for implementing a cube using signed distance fields:float methodOne(vec3 p) {return max(max(abs(p.x), abs(p.y)), abs(p.z)) – 1;}float methodTwo(vec3 p) {vec3 d = abs(p) – vec3(1);return min(max(d.x, max(d.y, d.z)), 0.0)+ length(max(d, 0.0));}One is preferable to the other for producing better images faster. Which one,and why? [4 marks](b) Complete the code below to implement the signed distance field function fora finite line segment with hemispherical end-caps (Figure 1) of arbitrary startpoint, end point, and radius. [4 marks]float lineSegment(vec3 p, vec3 start, vec3 end, float radius) {// [YOUR CODE HERE]}float getSdf(vec3 p) {return lineSegment(p, vec3(-PI, 0, 0), vec3(PI, 0, 0), 0.5);}(c) Implement a version of getSdf() that doubles the height of your line segmentand translates it by ?0.5 along the Z axis, to be centred at (0, 0, ?0.5) (Figure2). [4 marks](d) Implement a version of getSdf() that warps the original line segment into asine wave sin(X) (Figure 3). [4 marks](e) Modify getSdf() to render the sine wave model subtracted from the taller model(Figure 4). [4 marks]6CST1.2018.7.7Figure 1 Figure 2Figure 3 Figure 4Figure 1: A finite cylinder of radius 0.5 centred at (0, 0, 0) with hemisphericalend-caps, starting at (??, 0, 0) and ending at (?, 0, 0).Figure 2: The original finite cylinder has been enlarged to double its height onthe Y axis and has been translated in Z so that it is now centred at (0, 0, ?0.5).Figure 3: The original finite cylinder has been warped with a sine wave. Itscentre remains at (0, 0, 0) and its endpoints remain centred around (+/??, 0, 0),but in between its central axis falls to Y = ?1 and rises to Y = 1.Figure 4: The sine wave has been subtracted from the double-height cylinder.(Note: Ground plane shown at Y = ?1 for illustration purposes only)7 (TURN OVER)CST1.2018.7.85 Further Graphics(a) Write a GLSL function dartboard() which takes as input a texture co-ordinatetexCoord which ranges from (0, 0) ? (1, 1), and returns the colours of theprocedural texture for a black-and-white dartboard pattern of 16 squares aroundand 8 squares in radius (see figure below). The background behind the dartboardis gray.vec3 dartboard(vec2 texCoord) {// [YOUR CODE HERE]}[6 marks](b) What is . . .(i) the formula for the face angle ?(F, vi) of face F at vertex vi of a closedmanifold? [2 marks](ii) the formula for the angle deficit AD(v) of vertex v and its surrounding setof faces {F}? [2 marks](iii) the formula for the Poincar´e Formula of a surface with genus g and Eulercharacteristic ?? [2 marks](iv) the formula for Descartes’ Theorem of Total Angle Deficit? [2 marks](c) Consider a closed manifold surface with total angle deficit ?4?.(i) If your hypothetical surface has 20 vertices and 20 faces then how manyedges must it have? [2 marks](ii) Sketch a picture of your surface. [4 marks]8CST1.2018.7.96 Further HCI(a) Explain in general how the actions that a user takes are related to the user’sgoals. Your answer should make reference to the function of perception, and tothe nature of the cognitive processing that must occur. [8 marks](b) Describe a class of problems for which it is not possible to formulate goals. Givea specific example of a problem in this class, and with reference to that example,explain how it illustrates two significant attributes of the class. [6 marks](c) If an interactive system has several alternative models to describe the user’sgoal, how can Bayes’ theorem be used to improve the system usability? Imagine that you have been asked to implement a radical new design of your collegewebsite. The Senior Tutor has decided that, to make the college seem friendlier, thehome page and navigation should be implemented using a group photograph of allmembers of the college that was taken last summer. Your task is to design graphicalcontent that will be overlaid onto the photograph to provide all necessary informationand navigation.(a) Draw a sketch showing the main graphical features of your proposed design.(A few stick figures will be adequate to represent the original photograph. Noadditional marks will be given for realistic depictions of members of your college.)[4 marks](b) Explain how the display plane of the photograph has been segmented in yourproposed design, including explanation of any visual marks that were used toachieve this segmentation. [6 marks](c) Choose five specific visual aspects of your proposed design, and for each of thesefive:(i) Describe the graphical property used to implement this aspect (by referenceto your sketch); and(ii) Explain the mode of correspondence between this graphical property andthe meaning that is intended in this aspect of your design.[10 marks]10CST1.2018.7.118 PrologIn this question you should ensure that your predicates behave appropriately withbacktracking. You may not make use of extra-logical built-in predicates such asfindAll. Use of the cut operator is permitted unless specified otherwise. You mayignore the possibility of overflow or division by zero.(a) A term can either be an atom, variable or a compound term. Define each ofthese. [3 marks](b) Euclid’s algorithm for computing the greatest common divisor of two integerscan be implemented in ML as:fun gcd(a,0) = a| gcd(a,b) = gcd(b, a mod b);Provide an implementation in Prolog without using the cut operator.[4 marks](c) We can represent fractions using the compound term div/2. For examplediv(1,3) represents 13.Implement a predicate simplify which transforms a fraction into its smallestexact representation. For example, simplify(div(8,4),B) should unify B with2, and simplify(div(4,8),A) should unify A with div(1,2). Your predicateshould avoid unnecessary computation. Describe in detail an algorithm for finding the most general unifier of two terms.Illustrate your answer by unifying the following pairs of terms:f(x, a, x) with f(a, y, b)f(x, y, z) with f(g(y), z, a)f(g(y), y, z) with f(x, z, x)The variables above are x, y and z. [8 marks]”The resolution method relies on most general unifiers because they are unique.”Discuss. [3 marks]The resolution method can be applied directly to any first-order formula, regardlessof its structure. Discuss and evaluate the following proposals for dealing with specialcases:(a) If the formula has the form ¬A, then apply the resolution method to A. Failureto prove A establishes that ¬A is a theorem.(b) If the formula has the form of a disjunction A ? B, then apply the resolutionmethod separately to A and to B. If either proof succeeds then A ? B is atheorem.(c) If the formula has the form of a conjunction A ? B, then apply the resolutionmethod separately to A and to B. If both proofs succeed then A ? B is atheorem.(d) If the formula has the form A ? B, convert A to clauses. Then apply theresolution method to B, allowing A’s clauses to take part in applications ofthe resolution rule. If this proof succeeds then A ? B is a theorem.[9 marks]6CST.94.6.710 Foundations of Functional ProgrammingDescribe the operation of a graph reducer and its treatment of the combinators K,S, Y, if (for conditional expressions) and mult (integer multiplication). [6 marks]Describe the operation of the SECD machine, including its treatment of recursivefunctions. [5 marks]Exhibit an infinite family ?n of distinct fixed-point combinators. Justify youranswer by showing that ?n F(?n F) for all non-negative integers n and ?-termsF. You must also show that ?m 6= ?n for m 6= n, quoting standard results aboutthe ?-calculus if necessary. [9 marks]11 Computation TheoryExplain Turing’s Thesis. [5 marks](a) What is meant by saying that a Turing machine has searching states? Showthat any Turing machine computation can be effected by a machine withsearching states, equivalent in the sense that the head movements are identicaland the same symbols are written to the tape. [5 marks](b) Show that, subject to suitable encoding, any computation can be carried outby a Turing machine having only two states. [10 marks]12 Software EngineeringCompare and contrast the relative merits of Z and VDM as tools for specifying anddeveloping large software systems.  Describe and justify Dijkstra’s algorithm for finding the shortest path between two vertices in a directed graph with non-negative lengths associated with its edges. [8 marks] How can this algorithm be extended to consider graphs with some negative lengths? [6 marks] By considering the graph on {A, B, C} with A ? B having length ?2, B ? A having length 1 and A ? C having length 1, or otherwise, show that the “shortest path” is not always well defined if there are negative lengths. When is it well defined? [6 marks] 6 Data Structures and Algorithms Describe and justify the Graham scan algorithm for finding the convex hull of a set of points in the plane. [8 marks] How does its cost depend on the number of points? [4 marks] Give a technique for heuristically eliminating a number of points before doing the scan. In what circumstances can the heuristic fail to help and what would you do about it? [8 marks] 7 Structured Hardware Design A design is required for a novelty LED flasher that is to be small, battery operated and mounted inside a compact disc box as a promotional gimmick. The device has one LED only, and this produces bright pulses at approximately one Hertz. Instead of being entirely regular, the pulses are to be perceptibly irregular, in a way which grabs the attention of the careful observer. There will be a single production run of 18 million units. Discuss aspects of the design process, including the circuitry, whether to include a microprocessor, what, if any, ASIC technology to use, how many prototypes to generate and how they will be evaluated, and testing of the product. [15 marks] The design specification is now changed, so that now a meaning is attached to the slight deviations from a regular pulsing pattern. In particular, the pattern must slowly and repeatedly convey a built-in secret message of about 100 characters. It is acceptable that the decoding operation would be hard for the man in the street, but possible by an intelligent alien or computer scientist. How does this influence the design approach and cost? A computer with a 32-bit virtual addressing scheme uses pages of size 4 Kbyte. Describe, with the aid of diagrams, two practical schemes for managing its virtual address space, comparing them with regard to speed of access, efficiency (of space), and ease of memory sharing between processes. [10 marks] A Winchester-style disc has its head currently located at track 100, and the head is moving towards track 0. Given the reference string (27, 129, 110, 186, 147, 41, 10, 64, 120, 11, 8, 10) representing the (ordered) sequence of requests for disc tracks, give the sequence of disc addresses visited by the disc head under the SSTF, SCAN and C-SCAN disc scheduling algorithms. In each case briefly describe the algorithm, and compute the average cost of a disc access in terms of the mean number of tracks traversed per access. In what way is each of these algorithms biased in its service of disc requests? Describe an algorithm which reduces the bias. Computer Science Engineering & Technology C++ Programming CSCI-SHU MISC Share QuestionEmailCopy link Comments (0)