(a) What are the main criteria to be considered in the design of a line drawing algorithm for a raster graphics display? (b) Describe an algorithm to fill a series of pixels running from (x0, y0) to (x1, y1) that meets these criteria, explaining why it does so

Subject:Computer SciencePrice: Bought3

Share With

(a) What are the main criteria to be considered in the design of a line drawing
algorithm for a raster graphics display?
(b) Describe an algorithm to fill a series of pixels running from (x0, y0) to (x1, y1)
that meets these criteria, explaining why it does so. Answers should consist of
more than a fragment of pseudo-code.
(c) A new volumetric display stores an image as a three-dimensional array of
volume elements or voxels. Reformulate the design and implementation of
the line-drawing algorithm to fill a series of voxels running from (x0, y0, z0) to
(x1, y1, z1).

 

tackle everything

A fair coin is secretly flipped until the first head occurs. Let X denote the
number of flips required. The flipper will truthfully answer any "yes-no"
questions about his experiment, and we wish to discover thereby the value of X
as efficiently as possible.
(i) What is the most efficient possible sequence of such questions? Justify your
answer.
(ii) On average, how many questions should we need to ask? Justify your
answer. 
(iii) Relate the sequence of questions to the bits in a uniquely decodable prefix
code for X. 
(c) Define complex Gabor wavelets, restricting yourself to one-dimensional functions
if you wish, and list four key properties that make such wavelets useful for
encoding and compressing information, as well as for pattern recognition.
Explain how their self-Fourier property and their closure under multiplication
(i.e. the product of any two of them is yet again a Gabor wavelet) gives them
also closure under convolution. Mention one disadvantage of such wavelets for
reconstructing data from their projection coefficient

 

(a) Describe the basic algorithm for performing local search. Give an example of
a search problem for which it is an appropriate solution, and an example of a
search problem for which it is not. When would an algorithm such as A?
search
be preferred
(b) Give two examples of a situation that might reduce the effectiveness of the
basic local search algorithm. For each example you give, describe in detail a
modification to the basic algorithm that might be used to overcome it.
[8 marks]
(c) It is suggested to you that an application previously addressed as a constraint
satisfaction problem might alternatively be solved using some variant of local
search. Is this a reasonable suggestion? If it is, then outline a way in which it
might be achieved. If not, then provide a reasoned discussion explaining why.
 

(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.

 

 

 

(a) Throughout the 1990s mainstream microprocessors were developed with ever
deeper pipelines. Since then manufacturers have scaled back to more moderate
pipeline depths.
(i) What were the benefits from implementing deep pipelines and why were
they scaled back? [4 marks]
(ii) How do pipelines that support in-order and out-of-order execution differ in
their microarchitectural components? [4 marks]
(b) Modern high-performance processors incorporate a dynamic branch predictor to
avoid stalling when branches are fetched.
(i) What is a tournament branch predictor and why might it outperform either
a global or local branch predictor alone? [4 marks]
(ii) You develop a new branch predictor that is significantly more accurate than
existing designs. However, its complexity means that it takes several cycles
to produce a prediction. How can you make use of this predictor without
always introducing a pipeline bubble? [4 marks]
(iii) If you were designing an out-of-order core, why might you decide not to
allow predicated execution?

Consider a birth death process X(t) for t ≥ 0 with states 0, 1, 2, . . . and where the
birth rate is λj
in states j = 0, 1, . . . and the death rate is µj
in states j = 1, 2, . . .
(a) Draw the state space diagram for the birth death process. [2 marks]
(b) Derive the Chapman-Kolmogorov differential equations for the birth death
process in terms of Pj (t) = P(X(t) = j) for j = 0, 1, . . . and t ≥ 0. [4 marks]
(c) State the detailed balance conditions for an equilibrium distribution pj = Pj (t)
for j = 0, 1, . . . to solve the Chapman-Kolmogorov equations with dPj (t)
dt = 0
and determine a further condition to ensure the existence of the equilibrium
distribution. Derive an expression for equilibrium distribution pj when your
further condition holds. [4 marks]
(d) Describe a birth death process model for an M /M /K system in the limit as the
number of servers K → ∞. Draw the state space diagram, give the birth and
death rates and derive the equilibrium distribution stating whether there are
any conditions for its existence. [5 marks]
(e) Now consider the Chapman-Kolmogorov equations derived in part (b) in the
special case of a pure birth process with constant birth rates λj = λ for j =
0, 1, . . . and zero death rates µj = 0 for j = 1, 2, . . . Suppose that the
process starts in state 0 at time t = 0 (that is P0(0) = 1 and Pj (0) = 0
for j = 1, 2, . . .). Thus X(t) is the number of events in a Poisson process
of rate λ. Determine the Chapman-Kolmogorov differential equations for the
time-dependent solution Pj (t) for j = 0, 1, 2, . . . and t ≥ 0 in this case and solve
for the explicit solutions Pj (t) obeying the initial conditions.

 

(a) Various languages provide a built-in 'eval' operator which evaluates an
expression passed as an argument. Discuss the extent to which this: (i) fits
with existing language features, naming languages or classes of languages for
which 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 a
Standard 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 polymorphic
exceptions.
[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 be
seen as value types.
(ii) Discuss to what extent a programmer can use final to create value types in
Java, and whether this implementation gives the expected space and time
usage. [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 int
list as its representation. However, certain client code has been found to be
buggy, because it misuses :: to add elements (creating duplicates) and length
to 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 list
internally but only exposes operations (a) to create an empty set, (b) to
(functionally) insert one (non-negative) element into a set, (c) to sum the
elements in a set, (d) to count the number of elements in a set. No other
operation may create or manipulate an natset value.
[6 marks]
3 (TURN OVER)
CST1.2018.7.4
2 Economics, Law and Ethics
(a) Describe the possible market failures affecting anti-virus software firms in the
late 1980s and early 1990s, when viruses were a new threat to computer systems
and 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 years
later once the industry had consolidated into a handful of large firms. How might
this affect attacker behaviour? [5 marks]
(c) How will the incentives have changed in recent years with the spread of online
banking and crypto currencies? [5 marks]
(d) How do you expect the anti-virus industry to change as computing shifts from
PCs and laptops to phones and tablets? What about the impact of systems
embedded in durable consumer goods such as cars?

 

Consider the following grammar:
S → NP VP
NP → N S
NP → N
VP → V N
VP → V
N → {Alice, cats}
V → {saw, grinned}
(a) The grammar can be used to generate the following sentences:
(i) Alice saw cats
(ii) Cats Alice saw grinned
Draw derivation trees for both of these sentences. [2 marks]
(b) What is the longest sentence that can be generated by the grammar? Describe
this sentence. [2 marks]
(c) Is the language generated by the grammar a regular language? Provide a proof
for 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). Yngve
hypothesised that a speaker's short-term memory functions as a stack. Explain
how this hypothesis might account for the experimental results by drawing the
stack arising from a top-down parse of the two sentences.

(a) Present five experimental observations about human vision that support the
thesis that "vision is graphics": what we see is explicable only partly by the
optical image itself, but is more strongly determined by top-down knowledge,
model-building and inference processes

 

Write  program to Print first 5 even numbers using for loop
Write  program to input and print the greater of three numbers.

Write  program to input and print whether a number is positive or negative.
Write  complete java program that prompts the user for their name and two numbers.

 

Algorithms (a) State the Max-Flow Min-Cut Theorem. [2 marks] (b) For an arbitrary integer k ≥ 1, give an example of a flow network with at most five vertices on which the basic Ford-Fulkerson method takes at least k steps to terminate. [4 marks] (c) Consider the following flow network G: Given an initial flow f with f(s, u) = f(u, w) = f(w, t) = 2, perform one iteration of Ford-Fulkerson; that is, draw the residual graph Gf , specify an augmenting path in Gf , and update the flow f. Is this new flow a maximum flow? Justify your answer. [5 marks] (d) Given an undirected, connected graph G = (V, E), the edge-connectivity of G is the size of a smallest set of edges X ⊆ E so that the graph G0 = (V, E X) becomes disconnected. (i) Describe an algorithm that computes the edge-connectivity of G, and analyse its runtime and correctness. [7 marks] (ii) Extend your algorithm so that it also returns a set X satisfying the conditions above

 

The complex form of the Fourier series is: f(x) = X +∞ k=−∞ cke i2πkx where ck is a complex number and ck = c ∗ −k . (a) Prove that the complex coefficient, ck, encodes the amplitude and phase coefficients, Ak and φk, in the alternative form: f(x) = X +∞ k=0 Ak cos(2πkx − φk) [10 marks] (b) What is special about the case k = 0? [2 marks] (c) Explain how the coefficients, ck, of the Fourier series of the periodic function, f(x): f(x) = f(x + T), ∀x can be obtained from the Fourier transform, FL(ν), of the related function, fL(x): fL(x) = f(x), − T 2 6 x < T 2 0, otherwise [8 marks] 2 Concurrent Systems An interprocess communication environment is based on synchronous message passing. A server is to be designed to support a moderate number of simultaneous client requests. Clients send a request message to the server, continue in parallel with server operation, then wait for the server's reply message. Discuss the design of the server's interaction with the clients. Include any problems you foresee and discuss alternative solutions to them. [20 marks]

 

Further Java (a) Describe how mutual-exclusion locks provided by the synchronized keyword can be used to control access to shared data structures. In particular you should be clear about the behaviour of concurrent invocations of different synchronized methods on the same object, or of the same synchronized method on different objects. [6 marks] (b) Consider the following class definition: class Example implements Runnable { public static Object o = new Object(); int count = 0; public void run() { while (true) { synchronized (o) { count ++; } } } } Show how to start two threads, each executing this run method. [2 marks] (c) When this program is executed, only one of the count fields is found to increment, even though threads are scheduled preemptively. Why might this be? [2 marks] (d) Define a new class FairLock. Each instance should support two methods, lock and unlock, which acquire and release a mutual exclusion lock such that calls to unlock never block the caller, but will allow the longest-waiting blocked thread to acquire the lock. The lock should be recursive, meaning that the thread holding the lock may make multiple calls to lock without blocking. The lock is released only when a matched number of unlock operations have been made. You may wish to make use of the fact the Thread.currentThread() returns the instance of Thread that is currently executing.

 

ensure to answer every question