Question: Definition and explaination the following Fourth Normal…

Question Answered step-by-step Question: Definition and explaination the following Fourth Normal…  Question:Definition and explaination the following Fourth Normal Form.  Give an example of a database schema that is in 2NF form but not in 4NF, showing how it is possible for mutually contradictory data to be recorded. Explain your assumptions about the semantics underlying the database schema. [7 marks] Are there applications where normal forms are unnecessary or even unhelpful? [3 marks] SECTION C 9 Logic and Proof Describe the main features and applications of ordered binary-decision diagrams (OBDDs). [3 marks] Describe an algorithm for computing OBDDs efficiently. Be careful to distinguish optimisations from essential features of the data structure.Suppose that data is stored by initially creating a really tiny hash table (say a vector of size just 8). Entries are added to the table from time to time. Whenever the table becomes 3/4 full a new hash table, twice the size, is created: all existing data is taken out of the old table, and inserted instead into the new one. Thus in general the table that is in use will be between 3/8 and 3/4 full, and looking things up in it will be efficient. Although the above method has good predicted costs for retrieving information stored in the table, there remains some worry that the repeated cost of copying data from smaller to larger tables may be excessive. Suppose that at some stage N items have been inserted and that the very last insertion provoked the copying step. Estimate the ratio between the total number of hash probes performed while building the table and N. How does it compare with the number that would have been used if the table had been built full-sized to start with rather than having to grow stage by stage on the way?For each of the following situations identify one data structure or algorithm that it would be sensible to use, and another that would in principle achieve the desired result but which would have significant disadvantages. You may identify standard methods by name and need not describe in detail how they work, but should make it clear what properties the schemes that you identify have that make some of them more appropriate than others. (a) You need to represent some (directed) graphs where when a graph has N vertices it will have around N log N edges. The number of vertices, N, may become quite large. [4 marks] (b) In the process of rendering a graphical image you have already sorted all the objects that have to be drawn with an ordering based on their distance from the viewpoint. Now the image has been changed slightly so that you can start to display the next frame of the video sequence, so all the distances have changed, and you need to sort the objects again. [4 marks] (c) You need to build a table. It will be possible to insert objects into the table or retrieve previously stored ones. The only operation you are permitted to perform on objects is a pair-wise comparison that can tell if two objects are equal and if not indicates an ordering between them. There will be both plenty of insertion operations and plenty of lookups. [4 marks] (d) You need to find the shortest distance (through a directed graph that has lengths associated with each edge) from a nominated source point A to each of a collection of destinations {Bi}. [4 marks] (e) Blocks of material, each identified by a key, are to be stored on a large disc. From time to time new blocks (and associated keys) will need to be added, but mostly you need to service requests where a user submits a key and wants the corresponding information recovered. There is so much data that the disc is fairly full. Describe and justify Dijkstra’s algorithm for finding the shortest path between twovertices 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 ? Ahaving length 1 and A ? C having length 1, or otherwise, show that the “shortestpath” is not always well defined if there are negative lengths. When is it welldefined? [6 marks]6 Data Structures and AlgorithmsDescribe and justify the Graham scan algorithm for finding the convex hull of a setof 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 thescan. In what circumstances can the heuristic fail to help and what would you doabout it? [8 marks]7 Structured Hardware DesignA design is required for a novelty LED flasher that is to be small, battery operatedand mounted inside a compact disc box as a promotional gimmick. The device hasone LED only, and this produces bright pulses at approximately one Hertz. Insteadof being entirely regular, the pulses are to be perceptibly irregular, in a way whichgrabs the attention of the careful observer. There will be a single production runof 18 million units.Discuss aspects of the design process, including the circuitry, whether to includea microprocessor, what, if any, ASIC technology to use, how many prototypes togenerate 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 theslight deviations from a regular pulsing pattern. In particular, the pattern mustslowly and repeatedly convey a built-in secret message of about 100 characters. Itis 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 influencethe design approach and cost? [5 marks]5 [TURN OVERCST.96.3.68 Operating System FunctionsA 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 virtualaddress 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 headis 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 disctracks, 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 thealgorithm, and compute the average cost of a disc access in terms of the meannumber 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. [10 marks]9 Computation TheoryShow how to code the program and initial data for an n-register machine intonatural numbers p and d. In what sense do the codes p and d determine a uniquecomputation? [9 marks]Using your codes establish a precise statement of the Halting Problem for RegisterMachines. [3 marks]Assume that the Halting Problem is in general undecidable. Prove that it cannotbe decided whether a general program p terminates when the initial data is zero inevery register.  (a) Define what is a Turing machine and a Turing machine computation.[7 marks](b) What is meant by a partial function from Nnto N? Define what it means forsuch a partial function to be Turing computable. [4 marks](c) Describe the Church-Turing Thesis and some evidence for its truth. [4 marks](d) Assuming the existence of a universal register machine, give an example, withjustification, of a partial function that is not Turing computable.  Define the notion of a program expressed as a flowgraph of three-addressinstructions being in single static assignment (SSA) form. [4 marks]Given a program expressed in a language like C, explain how one might deal with(a) temporaries used to express a complicated expression as a sequence ofthree-address instructions, and(b) (non-address taken) formal parameters and local variablesso that the resulting flowgraph is in SSA form. [6 marks]Give a program for which performing a “map to SSA form” pass before registerallocation is likely to result in better code, noting any assumptions you make onhow register allocation works. [5 marks]Commonly SSA form is discussed only for temporaries and non-address-taken localvariables. To what extent is it possible to arrange that accesses to address-takenlocals or statically allocated global variables can be transformed into SSA form?What effect might such a transformation have on register allocation of suchvariables? [5 marks]3 [TURN OVERCST.99.7.45 Information RetrievalYou are asked to design a modern information management system for a largemulti-volume encyclopedia like the Encyclopaedia Britannica.Describe in detail the ways in which you would organise and index the encyclopediatext, and the facilities you would offer the system user. [12 marks]Justify your choices. [4 marks]Comment on the issues that would arise if you wanted to evaluate systemperformance. [4 marks]6 SecurityYou have been hired by a company which is bidding to take over the NationalLottery when Camelot’s franchise expires, and your responsibility is the securityarchitecture. State the security policy you would recommend and outline themechanisms you would implement to enforce it. [20 marks]4CST.99.7.57 Neural ComputingExplain the mechanisms and computational significance of nerve impulse generationand transmission. Discuss each of the following aspects:(a) The equivalent electrical circuit for a nerve cell membrane.(b) How different ion species flow across the membrane, in terms of currents,capacitance, conductances, and voltage-dependence. (Your answer can bequalitative.)(c) The role of positive feedback and voltage-dependent conductances.(d) The respect in which a nerve impulse is a mathematical catastrophe.(e) The approximate time-scale of events, and the speed of nerve impulsepropagation.(f ) What happens when a propagating nerve impulse reaches an axonal branch.(g) What would happen if two impulses approached each other from oppositedirections along a single nerve fibre and collided.(h) How linear operations like integration in space and time can be combined indendritic trees with logical or boolean operations such as AND, OR, NOT,and veto.(i) Whether “processing” can be distinguished from “communications”, as it isfor artificial computing devices.(j) The respects in which stochasticity in nerve impulse time-series may offercomputational opportunities that are absent in synchronous deterministiclogic.  Write  bout two of the following. Describe how each technique can be used in thesolution of a natural language processing (sub)task and the problems which remain.(a) Active chart parsing(b) Part-of-speech disambiguation using finite-state machines(c) Probabilistic context-free grammar(d) Plan recognition for discourse comprehension[10 marks each]9 Denotational SemanticsSuppose that f : D ? D is a continuous function on a domain. What is meant bythe least pre-fixed point, fix (f ), of f? [2 marks]Show that fix (f ) exists and is in fact the least fixed point of f. (a) State precisely what it means for a language (i) to be co-NP-complete, (ii) tobe in NL and (iii) to be in PSPACE. [6 marks](b) Consider the following two decision problems.Problem 1: Given an undirected graph G = (V, E) with |V | even,does G contain a clique with at least |V |/2 vertices?Problem 2: Given an undirected graph G = (V, E), does G containa clique with at least |V | ? 3 vertices?(i) Which of the two problems is in P and which one is NP?complete?[2 marks](ii) For the problem in P, describe a polynomial-time algorithm. [4 marks](iii) For the other problem, prove that it is NP-complete. [8 marks]3 (TURN OVER)CST.2014.6.43 Computation Theory(a) Explain how to code register machine programs P as numbers pPq ? N so thateach e ? N can be decoded to a unique register machine program prog(e).[10 marks](b) Find a number e1 ? N for which prog(e1) is a register machine program forcomputing the function one ? N ? N with one(x) = 1 for all x ? N. [2 marks](c) Why is it important for the theory of computation that the functions involvedin the coding and decoding given in part (a) are themselves register machinecomputable? (You are not required to prove that they are computable.)(d) Define what it means for a set of numbers S ? N to be register machine decidable.[2 marks](e) Let ?e ? N*N denote the partial function of one argument computed by theregister machine with program prog(e). Prove that {e ? N | ?e = one} isregister machine undecidable (where one is the function mentioned in part (b)).State carefully any standard results that you use in your proof. [4 marks]4CST.2014.6.54 Computation Theory(a) Give the recursion equations for the function ?n(f, g) ? Nn+1 ? N defined byprimitive recursion from functions f ? Nn ? N and g ? Nn+2 ? N. [2 marks](b) Define the class PRIM of primitive recursive functions, giving exact definitionsfor all the functions and operations you use. [5 marks](c) Show that the addition function add(x, y) = x + y is in PRIM.(a) Define what it means for a set of numbers S ? N to be register machine decidable.Why are there only countably many such sets? Deduce the existence of a set ofnumbers that is not register machine decidable. (Any standard results that youuse should be clearly stated.) [4 marks](b) A set of numbers S ? N is said to be computably enumerable if either it is emptyor equal to {f(x) | x ? N} for some total function f : N ? N that is registermachine computable.(i) Show that if S is register machine decidable, then it is computablyenumerable. [Hint: consider separately the cases when S is, or is notempty.] [4 marks](ii) Show that if both S and its complement {x ? N | x /? S} are computablyenumerable, then S is register machine decidable. [Hint: consider a registermachine that interleaves the enumeration of S and its complement.]Explain how the 32 bits are arranged to store the sign, exponent, and significand in asingle precision number under the IEEE binary floating-point standard (IEEE 754).How is the exponent stored? [2 marks]Explain the terms emax, emin, normalized number, denormal number, hidden bit,N aN. [5 marks]In terms of the stored bit-pattern, how can each of the following be recognized: ±0,±?, normalized number, denormal number, N aN? Computer Science Engineering & Technology Networking LOG 501 Share QuestionEmailCopy link Comments (0)