Describe, and estimate the costs of, procedures to (a) insert a new item into an existing heap; (b) delete the topmost item from a non-empty heap; (c) starting from an array holding N items in arbitrary order, rearrange those items so that they form a heap, taking time less than that which would be needed if the items were just inserted into the heap one after the other. [6 marks] A stable sorting method is one where items whose keys compare as equal will appear in the output in the same order that they appeared in the input list. Would a heap sort based on the algorithms you have documented be stable? Justify your answer. [5 marks] 6 Topics in Artificial Intelligence Give some reasons why some tasks are suited to being solved by using constraints. Illustrate your answer with examples of such tasks and the methods by which constraints are used to solve them. Consider the operation of a scheduler in a system where there are system level and user level processes. User processes may be IO bound or CPU bound and may have user controlled (negative) priority. Describe the data structures that the scheduler might use, including parts of process descriptors that the scheduler would operate on. [10 marks] Describe in detail the circumstances under which the scheduler would be entered and for each different circumstance outline a scheduling algorithm that might be used. [10 marks] 4 CST.95.11.5 8 Operating System Functions An operating system for a smart card is required that is a common run-time system for the smart card, which hosts some set of applications loaded into the card at the time the card is issued. What operations should the memory management component of the operating system support in such a system? [12 marks] The hardware engineers are concerned about complex memory management hardware consuming too much power, but the customer demands memory protection between the applications. Describe some solutions that could meet these demands. [8 marks] 9 Graphics Explain the purpose and operation of the A-buffer in rendering a sequence of images into a framestore. [12 marks] Exhibit an example that shows an advantage over the use of a Z-buffer.

(a) State the Fermat-Euler theorem, carefully defining any terms that you use. Deduce that 2p 2 (mod p) for any prime p. [5 marks] (b) Explain how this result can be used to show that a number is composite without actually finding a factor. Give an example. [3 marks] (c) Let Mm = 2m 1 be the mth Mersenne number. Suppose that m is composite. Prove that Mm is composite. [3 marks] (d) A composite number m that satisfies 2m 2 (mod m) is known as a pseudo-prime. (i) Suppose that m is prime. Prove that Mm is either prime or a pseudoprime. [3 marks] (ii) Suppose that m is a pseudo-prime. Prove that Mm is a pseudo-prime. [3 marks] (iii) Deduce that there are infinitely many pseudo-primes.

The William Gates Building has a centrally managed security system, dividing the building into zones to which different classes of user can gain access. All building users are issued with security cards that let them pass through doors into permitted zones. (a) Imagine you are designing the security system from scratch. Draw two diagrams suitable for discussing the operation of the system with (i) future building users; (ii) client engineering staff who will approve and manage the data model. [4 marks each] (b) Outline a project plan suitable for the management of this project, including a brief explanation of the kind of activity to be carried out in each phase. [6 marks] (c) The glass front doors to the building, originally conventional manual swing doors that required card access outside working hours, were inappropriate for wheelchair access. It was decided to replace them with automatic doors that slide open as you approach. Draw two statechart diagrams showing the behaviour of the doors (i) before this change; (ii) after this change, when the door operation state must be combined with the operation of the access-control system. [2 marks each] (d) If the software to control the sliding doors were to be implemented as an additional component of the security system, what earlier design precautions might have made such a change more straightforward?

Write program that prints your full name. Write program that prints your full name using asterisk(*)

Write a function to find sum of all even numbers between 1 to n.

Write method to find the smallest element in an array

create python code with the following information:

We are given a model with 4 parameters: N: Grid size; your overall grid should be NN. You may leave N as a parameter in your code, but all your deliverables should use the same value of N, which should be at least 30. red_blue_split: the fraction of total agents that are blue; between 0 and 1 inclusive. t: the satisfaction (contentedness) threshold; the fraction of an agent's neighbors that it wants to be its own type for it to be satisfied. That is, if t=0.4 and I have 5 neighbors, I am satisfied (contented) if at least 2 of them are the same type as me. Between 0 and 1 inclusive.

pct_empty: the percentage of grid squares that are empty. If pct_empty=1, this means the grid is completely empty; if pct_empty=0.1, this means the grid is only 10% empty. Between 0 and 1 inclusive.

The program must do:

1. Initialize an NN grid with agent types split according to red_blue_split and empty squares allocated according to pct_empty. The agents should be dispersed randomly. 2. Iterate through the society and check if each agent is satisfied. Satisfaction is defined as: at least a t fraction of your neighbors (occupying the 8 squares surrounding you) are the same type as you. Move each non-satisfied agent to an empty space (select the empty space at random from the available empty spaces). 3. Repeat step 2 until either: Every agent is satisfied, or A maximum iteration count (of your choosing) has been reached. (or use this advanced stopping criterion: track the cross-type-fraction CTF of your society over time, and if it goes a long time without changing much, terminate).

After all of that information, the program to code is the following:

1. Implement Schelling's model of segregation (on square grids) using the python code.

2. How segregated is the map throughout a simulation run? Create a function which checks the cross-type-fraction (CTF) of a snapshot of the map. As demonstrated in class, this function will divide the number of different-type neighbors (summed over all agents) by the total number of neighbors (summed over all agents). You should be able to call your function at each step along a simulation to see how the CTF changes as agents move around.

based on step 2: Create a series of plots which demonstrate how the CTF changes over the course of several simulation runs of the model. Each plot should have iteration number on the horizontal axis. You should choose at least 3 sets of parameter values (i.e., at least 3 different combinations red/blue split, satisfaction threshold t, and % empty). For each of these 3 sets of parameter values, do 5-10 simulation runs and plot their CTF traces together. You should have one plot with 5-10 traces for each of the 3 sets of parameter values, for a total of 3 plots. Clearly mark what parameter values gave rise to each of the plots.

3. How does segregation depend on parameter values? Create function which measures the average CTF at the end of a simulation run as a function of input parameters. Your function's call signature should be average_CTF(red_blue_split, t, pct_empty) When called, this function should perform 10 simulation runs with those parameters, record the CTF found at the end of each run, and then return the average of those 10 CTF values. Deliverable 3: Three plots created using your average_CTF function: (a) Plot 1 should display average CTF as a function of red blue split with the other parameters held constant, (b) Plot 2 should display average CTF as a function of t with the other parameters held constant, and (c) Plot 3 should display average CTF as a function of pct empty with the other parameters held constant. Each plot should have at least 10 points on the horizontal axis so that you can see the general shape of the curve. Note that each time you call average CTF, it performs 10 simulation runs, so if you have 10 points on the horizontal axis of each of these plots, this deliverable requires a total of 300 simulation runs.

Consider two natural numbers a, b N. (a) Define the highest common factor (a, b) of a and b. [2 marks] (b) Show that the set of linear combinations of a and b is equal to the set of multiples of their highest common factor: {as + bt | s, t Z} = {v (a, b) | v Z} [8 marks] Suppose that a and b are co-prime, so (a, b) = 1. Define a natural linear combination of a, b N to be as + bt with s, t N0. (c) Show that ab a b cannot be expressed as a natural linear combination of a and b. [2 marks] (d) Show that any natural number greater than ab a b can be expressed as a natural linear combination of a and b. [6 marks] [Hint: recall the complementary function for a linear Diophantine equation.] (e) Royal Mail first class stamps cost 32p each and second class stamps cost 23p each. What is the largest postage that cannot be paid exactly with first and second class stamps?

(a) What does it mean for a function to be an injection, surjection and bijection? [3 marks] (b) Let I = {x R | x > 1}. Define a binary relation g I I by taking (u, v) g iff 1 u + 1 v = 1 . (i) Express v as a formula in u for (u, v) g. Deduce that g is a function g : I I. [2 marks] (ii) State what properties are required of a function h : I I in order for h to be an inverse function to g. Define an inverse function to g and prove that it has the desired properties. Deduce that g : I I is a bijection. [6 marks] (c) (i) Let X be a set. Prove there is no injection f : P(X) X. [Hint: consider the set Y def = {f(Z) | Z X f(Z) / Z}.] [5 marks] (ii) Suppose now that the set X has at least two distinct elements. Define an injection k : P(X) (X X), from the powerset of X to the set of functions from X to X. [2 marks] (iii) Prove that there is no injection from (X X) to X when the set X has at least two distinct elements. [You may assume that the composition of injections is an injection.

(a) Write a polymorphic curried function prefix which, when applied to x and a list L, gives the list of pairs (x, y) for each y in L. For example, prefix "a" [1,2] = [("a",1), ("a",2)] What is the type of prefix? [5 marks] (b) Using your definition of prefix, write a definition of a function cartesian which, when applied to a pair of lists L1 and L2, produces a list of pairs containing the pair (x, y) for every element x in L1 and y in L2. For example, cartesian (["a","b"], [1,2]) = [("a",1), ("a",2), ("b",1), ("b",2)] What is the type of cartesian? [5 marks] (c) Write definitions in ML for the built-in higher-order functionals foldl and map. [6 marks] (d) Combine your definition of prefix with the functionals map and foldl to give an alternative definition of cartesian, which is not explicitly recursive. [4 marks] 12 Computer Vision Understanding, classifying, and identifying human faces has been a longstanding goal in computer vision. Yet because the face is an expressive social organ, as well as an object whose image depends on identity, age, pose and viewing angle, and illumination geometry, many forms of variability are all confounded together, and the performance of algorithms on these problems remains very poor. Discuss how the different kinds and states of variability (e.g. same face, different expressions; or same identity and expression but different lighting geometry) might best be handled in a statistical framework for generating categories, making classification decisions, and recognising identity. In such a framework, what are some of the advantages and disadvantages of wavelet codes for facial structure and its variability? Theory (a) Give a precise definition of the complexity class NP and of NP-completeness. [2 marks each] (b) For any natural number k, the problem k-colourability is defined as the following decision problem. Given a graph G = (V, E), is there a mapping : V {c1, . . . , ck} such that if (u, v) E, then (u) 6= (v)? (i) Explain why, for each k, the problem k-colourability is in the class NP. [2 marks] (ii) For what values of k is the problem k-colourability decidable in polynomial time? Why? [2 marks] (iii) For which values of k is the problem k-colourability NP-complete? Give a brief indication how this might be proved. [2 marks] (c) The company Fon-X runs a mobile 'phone service. It has 2000 'phone masts stationed across the country. The frequency spectrum assigned to the company is split into 20 bands. Each mast is to be assigned a frequency band in such a way that masts within 50 miles of each other do not share the same frequency band. (i) What is the relationship between this problem and k-colourability? [2 marks] (ii) What can you say about the complexity of the problem Fon-X is trying to solve?