Hidden Markov models (HMM) are widely used in Bioinformatics. (i) In a HMM when would you use the Baum-Welch algorithm, and when the Viterbi algorithm, and why? Give biologically motivated examples. (ii) Any machine learning model (such as a HMM) for protein secondary structure determination or gene finding relies on discovering characteristic statistical properties of protein sequences. Name a property (and justify your answer) that helps to localise (and distinguish) transmembrane segments and coils in a protein sequence, or exon/intron boundaries in a genomic region. (b) Discuss the complexity of an algorithm to reconstruct a genetic network from microarray perturbation data. (c) What is the difference in terms of connectivity between a scale-free network and a random network? Give biological examples of scale-free networks

 

answer every question

Consider a software routine that converts the sampling rate of digital audio data from 8 kHz to 48 kHz, without changing the represented sound. It reads an input sequence {xi} and produces an output sequence {yi}. The routine first inserts five samples of value 0 between each consecutive pair of input samples. This results in a new intermediate sequence {x 0 i } with x 0 6i = xi and x 0 6i+k = 0 for all k {1, . . . , 5}. The sequence {x 0 i } is then low-pass filtered, resulting in {yi}. (a) How can the process of taking discrete-time samples {xi} from a continuous waveform x(t) be modelled through a function x(t) that represents the sampling result but can still be analysed using the continuous Fourier transform? (b) What effect does sampling with 8 kHz have on the Fourier spectrum of the signal? (c) How and under what condition can this sampling process be reversed? (d) Can x(t) also model another sampling process that results in the discrete sequence {x 0 i }, and if so, what is its sampling frequency? [2 marks] (e) How does the continuous spectrum associated with {x 0 i } relate to that of {xi}? (f ) What purpose is served by the low-pass filter that the routine applies? In particular, what would happen to a 1 kHz sine tone input if this filter were not applied and {yi} = {x 0 i } were output instead? What cut-off frequency must the filter have?

The development manager of a website for online book-buying has asked you to carry out a heuristic evaluation of its usability. He has specifically proposed the three heuristics listed below. 1. "There should be between five and nine navigation options on each page." 2. "There should be a good match between the navigation buttons and the users' goals." 3. "It should be easy for users to change their plans." (a) Has the manager misunderstood heuristic evaluation? Briefly justify your answer. [2 marks] (b) Please comment on the above three heuristics suggested by the manager. For each of the proposed heuristics, your comments should include: (i) any theoretical justification for (or against) this heuristic; (ii) any additional evaluation steps that might be required in applying it; and (iii) the likely impact of such evaluation on the system design.

(a) Switches are used in a variety of different communications networks. (i) Describe how switch architectures that are used to forward samples in Time Division Multiplexed networks, such as the digital telephone network, are designed to scale to large numbers of input and output ports. (ii) In asynchronous networks such as Asynchronous Transfer Mode (ATM) or Internet Protocol (IP) packet networks, switches are also used to forward packets. What are the basic components of a router with input and output buffering? (b) Distributed routing algorithms in communications systems are designed to provide a fault-tolerant computation of end-to-end paths in the event of link or router failure (or repair). (i) Describe how this occurs, using as an example the distance-vector algorithm. (ii) Distance-vector routing is said to be slow to react to changes. Explain why, and outline why link-state protocols are therefore preferred in today's Internet.

Members of an open process group manage distributed replicas of data values stored in persistent memory. To allow the system to operate in the presence of transient failures of some replica managers, a quorum assembly scheme is used. Replica managers are assumed to be non-malicious and fail-stop. To update a managed data item, the operations provided by the managing process include: lock(item) update(item, value, timestamp) read(item, timestamp) unlock(item) (a) Suppose the data item is an initially empty list of values and the update operation appends a value. Illustrate the quorum assembly scheme for five replicas, showing a number of update and read operations. [8 marks] (b) How is a total order of updates achieved by quorum assembly in the presence of concurrent update requests by clients to the open group? Discuss how any problems that might arise can be solved. [4 marks] (c) When can unlock(item) be executed safely by the initiating replica manager? Describe any additional protocol that is needed. [5 marks] (d) Suppose that the process group is managing non-overlapping partitions of a distributed database instead of replicas. Can quorum assembly play any part in making the related updates required for distributed transactions? Justify your answer.

(a) Extraction of visual features from images often involves convolution with filters that are themselves constructed from combinations of differential operators. One example is the Laplacian 2 2 x2 + 2 y2 of a Gaussian G(x, y) having scale parameter , generating the filter 2G(x, y) for convolution with the image I(x, y). Explain in detail each of the following three operator sequences, where signifies two-dimensional convolution. (i) 2 [G(x, y) I(x, y)] [2 marks] (ii) G(x, y) 2 I(x, y) [2 marks] (iii)

2G(x, y)

I(x, y) [2 marks] (iv) What are the differences amongst their effects on the image? [2 marks] (b) In human vision, the photoreceptors responsible for colour (cones) are numerous only near the fovea, mainly in the central 10 degrees. Likewise high spatial resolution is only found there. So then why does the visual world appear to us uniformly coloured? Why does it also seem to have uniform spatial resolution? What implications and design principles for computer vision might be drawn from these observations? [4 marks] (c) Outline a scheme for accomplishing transcription of handwriting (not cursive, that is, with letters already separated). Explain the core modules in your system, from low-level feature extraction to high-level classification of letters. At the highest level of the classifier, explain how the system could use Bayesian methods to incorporate expert knowledge such as a lexicon of actual words and knowledge about relative letter frequencies. [4 marks] (d) How can dynamic information about facial appearance and pose in video sequences (as opposed to mere still-frame image information), be used in a face recognition system? Which core difficult aspects of face recognition with still frames become more tractable with dynamic sequences? Are some aspects made more difficult? [4 marks] Describe, in detail, the radiosity method for calculating illumination. Ensure that your answer gives an overview of the algorithm, describes an implementable method of calculating form factors, and explains an efficient way of iterating to a solution.

Sequences (lazy lists) and trees are fundamental types in functional programming. Here are definitions of sequences and trees with integer elements: type iseq = Nil | Cons of int * (unit -> iseq) type itree = Leaf of int | Branch of itree * itree (a) In an ascending sequence such as 1, 3, 3, 7, . . . each element is at least as large as the previous elements. Given two ascending sequences, write a function merge2 that produces a sequence of the elements of both in ascending order. For example, passing 1, 3, 3, 7, . . . and 2, 4, 5, 9, . . . to merge2 should produce the sequence 1, 2, 3, 3, 4, 5, 7, 9, . . .. [5 marks] (b) Sequences are considered to be equal if corresponding elements are equal. (i) Define a function equal_seq that compares two sequences for equality. [5 marks] (ii) Define sequences s1 and s2 for which equal_seq s1 s2 does not terminate. [3 marks] (c) The fringe of a tree is the left-to-right sequence of the values at the leaves. For example, the fringe of Branch (Leaf 3, Branch (Leaf 10, Leaf 4)) is the sequence 3, 10, 4. (i) Define a function fringe that computes the fringe of a tree. Your function should have the following type: val fringe : itree -> iseq [5 marks] (ii) Using the functions you have defined above or otherwise, write a function equal_fringes that determines whether two trees have equal fringes

Write program to find the average of a given set of numbers. 2- Write a program to find the smallest and the largest number from a given set of numbers.

Write program to encrypt the plain text using transposition cipher.

write program to find solution of 8 number problem

In this question we deal with a general two-class supervised learning problem. Instances are denoted by x X, the two classes by c1 and c2, and h : X {c1, c2} denotes a hypothesis. Labelled examples appear independently at random according to the distribution P on X {c1, c2}. The loss function L(ci , cj ) denotes the loss incurred by a classifier predicting ci when the correct prediction is cj . (a) Show that if our choice of hypothesis h is completely unrestricted and L is the 0-1 loss function then the Bayes optimal classifier minimising E [L(h(x), c)] where the expected value is taken according to the distribution P is given by h(x) = c1 if Pr(c1|x) > 1 2 c2 otherwise. [10 marks] (b) We now define a procedure for the generation of training sequences, denoted by s. Let H be a set of possible hypotheses, let p(h) be a prior on H, let p(x) be a distribution on X and let Pr(c|x, h) be a likelihood, denoting the probability of obtaining classification c given instance x and hypothesis h H. A training set s is generated as follows. We obtain a single h H randomly according to p(h). We then obtain m instances (x1, . . . , xm) independently at random according to p(x). Finally, these are labelled according to the likelihood such that p(s|h) = Ym i=1 Pr(ci |xi , h)p(xi). We now wish to construct a hypothesis h 0 , not necessarily in H, for the purposes of classifying future examples. The usual approach in a Bayesian context would be to construct the hypothesis h 0 (x) = c1 if Pr(c1|x, s) > 1 2 c2 otherwise. By modifying your answer to part (a) or otherwise, show that this remains an optimal procedure in the case of 0-1 loss.

(a) Distributed storage approaches can be divided into network attached storage (NAS) and storage area networks (SANs). Explain with the aid of a diagram the basic differences between the two approaches. [4 marks] (b) The network file system (NFS) is often used in local area networks. (i) Why is NFS not normally considered suitable for wide area networks? [2 marks] (ii) Briefly discuss how one could modify NFS to better support wide area networks. [2 marks] (c) Distributed shared virtual memory can be used within a computing cluster to transparently allow multi-threaded programs to run across multiple machines. Sketch the design of a DSVM system. Be sure to explain what happens both when a memory read and when a memory write occurs. Comment on the expected performance and robustness of your system. [6 marks] (d) EROS is a capability-based operating system. (i) What is a capability? [1 mark] (ii) Explain with the aid of a diagram how EROS uses traditional paging hardware to emulate capability hardware.

Given any polymorphic lambda calculus (PLC) type and any function mapping type variables to values n {1, 0, 1}, a value [[ ]] in {1, 0, 1} is defined by recursion on the structure of as follows. [[]] = () [[1 2]] = 1 if [[1]] [[2]] [[2]] otherwise [[( )]] = the minimum of the values [[ ]]([ 7 n]) for n = 1, 0, 1 (where [ 7 n] is the function mapping to n and every other 0 to ( 0 )). If is a non-empty PLC typing environment, let [[]] denote the minimum value of [[ ]] as ranges over the types in ; in the case that is empty, we define [[]] to be 1. (a) Prove that if ` M : is a valid PLC typing judgement, then for any , [[]] [[ ]]. You may assume without proof that if is not free in then [[ ]]([ 7 n]) = [[ ]] and also that type substitutions [ 0 /] satisfy [[ [ 0 /]]] = [[ ]]([ 7 [[ 0 ]]]) [Hint: show that the property (, M, ) = "for all , [[]] [[ ]]" is closed under the rules of the typing system.] [16 marks] (b) Deduce that there is no closed PLC expression of type , ((( ) ) )

A W H matrix can be represented in OCaml by a flat list: a list that concatenates the rows in order. For each of the following alternative ways to represent a 2D matrix in OCaml: State the type T of the representation; Give a function create w m: int -> float list -> T that constructs the matrix of type T equivalent to the input flat list m with row width w; Give a function get r c m: int -> int -> T -> float that gets the element of the matrix m at row r and column c. State the asymptotic complexity of the get function in terms of W and H (a) A list of lists. [5 marks] (b) An array of arrays. [6 marks] (c) A functional array of functional arrays. [9 marks] Your answers may use the List module and assume this functional array code: type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;; exception Subscript;; let rec update = function | Lf, k, w -> if k = 1 then Br (w, Lf, Lf) else raise Subscript | Br (v, t1, t2), k, w -> if k = 1 then Br (w, t1, t2) else if k mod 2 = 0 then Br (v, update (t1, k / 2, w), t2) else Br (v, t1, update (t2, k / 2, w));; let rec sub = function | Lf, _ -> raise Subscript | Br (v, t1, t2), 1 -> v | Br (v, t1, t2), k when k mod 2 = 0 -> sub (t1, k / 2) | Br (v, t1, t2), k -> sub (t2, k / 2);;