: (i) What data structures are maintained by the page manager. (ii) What happens when a machine performs a read operation to a page. (iii) What happens when a machine performs a write operation to a page. [8 marks] (b) Someone observes that the centralized page manager may form a bottleneck and a single point of failure. Do you agree with these observations? [2 marks] (c) Sketch the implementation of a scalable spin-lock for use on shared-memory multiprocessor machine

Illustrate different ways of connecting these components together to span a range of performance requirements. [10 marks] For each of the performance categories that you identify state today's typical memory size, bus width and CPU speed. [6 marks] 3 Self-timed logic circuits may enable an existing technology to achieve higher performance. Explain the principle of self-timed circuits. [8 marks] Comment on the possible opportunities for improved performance. [6 marks] Is it likely that large logic systems will become easier to.1.2 4 design using self-timed logic rather than more traditional arrangements? Explain. [6 marks] each, five of the following terms: (a) barrel shifter; (b) depletion layer; (c) state assignment; (d) signal combination with diodes; (e) dynamic logic; (f ) binary addition; (g) static hazard. [4 marks eachStudy the following ML function definitions and answer the questions below: fun prefix [ ] [ ] = [ ] | prefix (x::xs) (y::ys) = (x::y)::prefix xs ys; fun se will return a row of length n + 1 cells initialised with zeros. For instance: mkrow(1) = Cell(ref 0, ref(Cell(ref 0, ref Z, ref Z)), ref Z) [5 marks] Define a function zip(row1, row2) of type A*A->A that will return row1 with row2 joined above it. This function is entitled to change some of the ref A pointers in row1. For example val root = zip(mkrow(3), mkrow(2)); would give root a value representing the following arrangement. 0 0 0 root : 0 0 0 0 [5 marks] Next define a function mkarr(m,n) of type (int*int)->A that will return a value representing a rectangular array of n + 1 rows each of which are of length m + 1 in which each cell is initialised to zero [5 marks] Paths originating from the bottom leftmost cell (which will be referred to by the variable root) are represented by values of the type dir list where dir is declared as follows: datatype dir = Right | Up; Finally define a function inc path cells of type A->A list->unit that will increment the integers in all the cells that lie on a specified path within a given collection of cells. For instance after root had been set up as above, the two calls 4 CST.94.1.5 inc path cells root [Right, Up, Right]; inc path cells root [Right, Right, Right]; would leave root representing the following arrangement: 0 1 1 root : 2 2 1 1 You may assume that the path does not try to reach cells outside the given arrangement. [5 marks] 7 Show, by defining suitable selector and constructor functions, how the ML type defined as follows: datatype L = N of int * unit->L; can be used in the representation of lazy integer lists. [5 marks] Define a function makeseq(f) that will yield a lazy list representing the following infinite sequence: 0, f(0), f(f(0)), ... where the integer at position i has the value f i (0). [5 marks] Define a function 'matches s seq', where s is of type int list and seq is a lazy list, that will yield a lazy list of integers giving the positions where s matches consecutive items in seq. For example, if matches [1 1] is applied to the lazy list 1,1,2,1,1,1,0,1,2,1,1,... it will produce a lazy list starting 0,3,4,9,... [10 marks] 5 [TURN OVER CST.94.1.6 8 Sets of distinct integers can be implemented in ML as values of type set declared below: datatype set = Leaf | N of set * int * set; Describe how you would use this data type to represent sets. [4 marks] Give simple definitions for the follow well as all the elements of the given set; [4 marks] (b) mkset: int list->set Creates a set containing all the integers from the given list; [3 marks] (c) mklist: set->int list Makes a list of all the integers present in the given set; [3 marks] (d) union: set*set->set Forms a set from all integers in the two arguments, avoiding the introduction of repeated entries; [3 marks] (e) select : set->int*set Returns an arbitrary integer from the set, and also the set with that item removed. select should raise an exception if the given set is empty. [3 marks] Your definitions should aim for simplicity and elegance rather than efficiency. 6 CST.94.1.7 SECTION C 9 The Imperial system for Sterling currency was based on the pound, the shilling and the penny, with 12 pence per shilling and 20 shillings per pound. Define a Modula-3 record type to store an amount of money in pounds, shillings and pence. Allow for both positive and negative sums, and use sub-range types to restrict the values of fields in your data structure so that (for instance) the pence field always contains a number in the range 0 to 11. [4 marks] Write procedures to convert an integer value in pence to the Imperial type you have just defined, and to convert from the Imperial type to text. The following examples illustrate aspects of the desired text corresponding to various numbers of pence. The library procedure Fmt.Int may be used to convert integer values to text. 0 zero 1 1 penny 10 10 pence 60 5 shillings 80 6 shillings and 8 pence 252 1 pound and 1 shilling 479 1 pound, 19 shillings and 11 pence 1201 5 pounds and 1 penny 2400 10 pounds -252 minus 1 pound and 1 shilling [16 marks] Credit will be given for a clearly explained, concise and tidily presented solution. Minor syntax or punctuation errors in the Modula-3 code will not count heavily against you. 7 [TURN OVER CST.94.1.8 10 Modula-3 allows the user to declare arrays with any sort of contents for instance arrays of integers, reals, TEXT or structures, but the index type for an array is restricted and in particular cannot be of type TEXT. It is sometimes useful to achieve an effect analogous to having an array that can be indexed using values of type TEXT. One way of doing this is to use a structure known as a hash table: given an index value of type TEXT an integer is computed using a hash function and this is then used to index an array. The library procedure Text.Hash computes a suitable integer from a TEXT value. Two complications arise. First the integer computed by the hash function may lie outside the valid range of index values for the array. Secondly two different TEXT objects may give rise to the same hash value. The problems can be resolved first by reducing the raw hash value modulo the size of the array and arranging that each array entry refers to the start of a linked list of (index,value) pairs. Retrieving a value from the table involves accessing the array to obtain the correct list of pairs and then scanning the list to find an index value that is identical (use the library function Text.Equal) with the TEXT index being sought. The corresponding value can then be returned. Storing into the table will involve adding a new (index,value) pair to one of the lists. Design appropriate data structures for such a table, and write procedures to store and retrieve values, using the following signatures: PROCEDURE Put(VAR table: Table; key, value: TEXT) RAISES {DuplicateKey} PROCEDURE Get(READONLY table: Table; key: TEXT): TEXT RAISES {MissingKey} [20 marks] 8 CST.94.1.9 11 In Modula-3 what are object types, and how do they differ from simple record data types? In this context give a brief explanation of method invocation, inheritance and of each of the keywords METHODS, NEW and OVERRIDES. Include short examples where appropriate. [10 marks] Describe briefly the facilities in Modula-3 for defining and using array and reference types. Explain the concept of an open array, showing how access to an array that is received as an argument by a procedure may differ from direct references to the same array. Give an example of a programming task that would be harder in Modula-3 if open arrays were not provided. [10 marks] 9 [TURN OVER CST.94.1.10 12 A Unix user (with the BASH shell) sets up a file containing the executable: echo $1 $2 mv $1 $1.temp mv $2 $1 mv $1.temp $2 The user at the next terminal sets up a file that is very similar, but which uses cp rather than mv. Describe the behaviour each can expect when they use these files as command scripts. Assuming that the files concerned are both called sw, explain carefully the consequences of such uses as sw somefile somefile sw firstfile.temp secondfile.temp sw only/one.file [7 marks] In another file, called de (say) the following commands exist: echo $# files >> de.info for n in $* do echo $n >> de.info mv $n backup/$n done What do the various substitutions (involving '$' signs) do in this case? Given that '>>' is much like '>' but appends new data to an existing file rather than creating a new one, what will build up in de.info over the course of time? Discuss the effect of issuing the command "de *". [7 marks] Many Unix commands, for example xlsfonts and even just ls, can generate more output than will fit on the screen at once. Give a brief account of (a) how to use more to inspect the output and (b) how to collect a copy of the output in a file for inspection using a text editor. Write a shell script that will run ls with the -l flag (to get a full detailed listing of file sizes and dates) on one or more directories, will collect all the output in a single temporary file, enter an editor to allow you to inspect the information you have gathered and at the end get rid of the temporary file. [6 marks

In a distributed electronic conference application each participant has a replica of a shared whiteboard. Only one user at a time may write to the whiteboard, after which the user's update is propagated to all conference members. A dedicated process manages each whiteboard replica. Define and discuss a protocol that the replica managers could use to achieve this mutual exclusion. [10 marks] A service database is replicated within a widely distributed system to achieve high availability and low access latency. Within a hierarchy of replicas a set of top-level primary servers maintain strong consistency of their replicas. Describe how this strong consistency could be achieved.

In the following, N is a feedforward neural network architecture taking a vector x ) of n inputs. The complete collection of weights for the network is denoted w and the output produced by the network when applied to input x using weights w is denoted N(w, x). The number of outputs is arbitrary. We have a sequence s of m labelled training examples s = ((x1, l1),(x2, l2), . . . ,(xm, lm)) where the li denote vectors of desired outputs. Let E(w; (xi , li)) denote some measure of the error that N makes when applied to the ith labelled training example. Assuming that each node in the network computes a weighted summation of its inputs, followed by an activation function, such that the node j in the network computes a function g w (j) 0 + X k i=1 w (j) i input(i) ! of its k inputs, where g is some activation function, derive in full the backpropagation algorithm for calculating the gradient E w = E w1 E w2 w1, . . . , wW denotes the complete collection of W weights in the network. [20 marks]

) Describe the way in which a problem should be represented in order to allow its solution using a heuristic search technique. [5 marks] (b) Define what it means for a search algorithm to be complete, and to be optimal. [2 marks] (c) Define what it means for a heuristic function to be admissible, and to be monotonic. [2 marks] (d) Describe the operation of the A? heuristic search algorithm. [5 marks] (e) Prove that the A? heuristic search algorithm is optimal when applied in conjunction with a monotonic heuristic. State the conditions under which the algorithm is also complete, and explain why this is the case. [6 marks]

The following protocol is meant to establish a strong shared secret between two wireless devices A and B through a Diffie-Hellman exchange over radio. To guard against man-in-the-middle attacks, in message 3 device A sends device B a 16-bit secret random value R over a different channel, for example by showing the value on A's screen and having the human user retype it into B's keypad. Notation: x|y indicates the concatenation of bit strings x and y, while mK(x) indicates the MAC (message authentication code) of message x using (3) A B : R (4) A B : mKA (A|g a |g b |R) (5) A B : mKB (B|g a |g b |R) (6) A B : KA (7) A B : KB (8) (on their own) : (verification) (9) A B : (confirmation) (a) Explain what the resulting shared secret will be and what additional verification and confirmation steps each side must take after exchanging the first 7 messages shown above. [3 marks] In the following questions, "explain in detail" means with reference to the exact messages exchanged and expected by A, B and a man-in-the-middle M; and, where appropriate, with suitable protocol diagrams involving all three. (b) Explain in detail how a man-in-the-middle M could successfully attack this protocol if R were not used or if M could eavesdrop on message 3. [4 marks] (c) Explain in detail how the introduction of R stops the man-in-the-middle. [5 marks] (d) Explain in detail how the man-in-the-middle could still successfully attack this protocol if the confirmation of step 9 were omitted. [8 marks]

Compose program to information and print whether a number is positive or negative. complete java program that prompts the client for their name and two numbers. Compose program that will request that the client enter your name and your class segment

Some systems administration scientists wish to explore the way of behaving of a systems administration convention when it is working over significant distance (high dormancy) joins. To do this, they mean to assemble an organization postpone test system , which they will use to interconnect a couple of organization hubs. Working simultaneously on each connection bearing, the gadget will get the information stream, postpone it, then send it onwards to the next hub. The organization utilizes a sequential connection working at one gigabit each second, and the analysts expect to have the option to shift the postponement, for example, to reenact connections of between 1 and 5000 kilometers long. network hub

Programming answers ought to be written in some documentation approximating SML or OCaml. (a) Describe what is implied by tail recursion. [4 marks] (b) Eliminate tail recursion from foldl given underneath. Make sense of your response. (* foldl : ('a - > 'b - > 'a) - > 'a - > 'b list - > 'a *) let rec foldl f accu l = coordinate l with [] -> accu | a::l - > foldl (f accu a) l [8 marks] (c) Eliminate tail recursion from the accompanying commonly tail-recursive capacities. Make sense of your response. let rec is_even n = if n = 0 then evident else is_odd (n - 1) also, is_odd n = if n = 0 then, at that point, misleading else is_even(n - 1)

Consider composing a compiler for a straightforward language of articulations given by the accompanying language, e ::= n (whole number) | ? (peruse whole number contribution from client) | e + e (expansion) | e e (deduction) | e e (augmentation) | (e, e) (match) | fst e (first projection) | snd e (second projection) (a) Describe the assignments that ought to be conveyed in carrying out a front end for this language and any hardships that may be experienced. [5 marks] (b) Suppose that the objective virtual machine is stack-situated and that the stack components are whole number qualities, and addresses can be put away as numbers. Make sense of which different highlights are expected in a particularly virtual machine. Concoct a straightforward language of directions for such a machine and show how it would be utilized to carry out every one of the articulations. this is ok. (c) Suppose that the accompanying guidelines are proposed as potential advancements to be executed in your compiler. articulation streamlines to articulation (fst e, snd e) e fst (e1, e2) e1 snd (e1, e2) e2 Depict how you could execute these principles with the goal that the improvements are made just when the program's semantics is accurately safeguarded. [5 marks]

5 Concepts in Programming Languages (a) Explain what is implied by a monad in a programming language, giving the two major tasks of a monad alongside their sorts. [3 marks] (b) Consider the utilization of a monad for input-yield. For the reasons for this inquiry, accept the IO monad as including two activities readint and writeint which separately read whole numbers from stdin and compose whole numbers to stdout. Give the sorts of these administrators.

Let f : N 1+m+n* N be a register machine processable fragmented limit of 1+m+n

disputes for some m, n N.

(I) Why is the inadequate limit f : N 1+m+n* N satisfying for all (z, ~x, ~y)

N 1+m+n

f(z, ~x, ~y) f(S1+m,n(z, z, ~x), ~x, ~y) (2)

register machine processable? [3 marks]

(ii) By pondering S1+m,n(e, e, ~x) where e is a record for the partial limit

f somewhat (b)(i), exhibit that there is a totally defifined register machine

measurable limit fifix f : Nm N with the property that for all ~x Nm

moreover, ~y Nn

(n)

fifix

f(~x)(~y) f(fifix f(~x), ~x, ~y) (3)

[7 marks]

6CST1.2021.6.7

6

Estimation Theory

A set An outfitted with a matched movement @ : A A A can't avoid being a combinatory polynomial math

accepting there are parts K, S A magnificent for each of the a, b, c A

@(@(K, a), b) = a

(1)

@(@(@(S, a), b), c) = @(@(a, c), @(b, c)) (2)

(a) Show that there is a twofold methodology on the plan of equivalence classes of closed

-terms for the indistinguishable quality association of -change that makes it a combinatory

variable based math. [5 marks]

(b) Show that each combinatory variable based math A contains a part I satisfying

@(I, a) = a

(3)

for all of the a A. [Hint: what does (2) let us in on when a = b = K?] [2 marks]

(c) For an inconsistent combinatory polynomial math A, let A[x] mean the plan of enunciations

given by the accentuation

e ::= x | p aq | (ee)

where x is some fifixed picture not in An and a ranges over the parts of A.

Given e A[x] and a A, let e[x := a] mean the part of An ensuing from

interpreting occasions of x in e by a, unraveling the assertions of the design

p a0 q by a0 and unraveling explanations of the construction (ee0 ) using @.

(I) Give the arrangements in a defifinition of e[x := a] by recursion on the plan of

e. [2 marks]

(ii) For each e A[x] tell the most effective way to defifine a part xe A with the property

that

@(xe, a) = e[x := a] (7)

for all of the a A. [6 marks]

(d) Recall the standard encoding of Booleans in -math. Using Part (c)(ii), show

that in any combinatory polynomial math A there are parts True, False An and a

work If : A A A superb

@(If (a, b), True) = a

(11)

@(If (a, b), False) = b

(12)

for each of the a, b A

[5 marks]

7CST1.2021.6.8

7

Data Science

(a) Let xt be the amount of new COVID defilements on date t. We anticipate

generally emotional turn of events or decay, xt+1 (1 + )xt , and we would

like to survey from a dataset (x1, . . . , xT ).

(I) Find the most outrageous likelihood assessor for for the model

Xt+1 Poisson

Utilizing the data gave for the situation study, would you have the choice to gather a Context outline, Level 0 Data Flow Diagram, and an ERD utilizing any outlining programming.

The 2020 Covid pandemic has affected different endeavors across the globe and Australia's normal thing picking industry is no prohibition. Ordinary thing pass contributes commonly on to Australia's exchange. Most typical things are generally speaking brief and along these lines customary thing picking is something that should be done marvelously and with care. Despite the way that Australia's regular thing picking industry faces two or three issues, one of them is nonattendance of adequate work. This issue, among many, has exasperated taking into account COVID 19. To help the ranchers and the standard thing picking industry, Zaf Soft, an Australian Information System supplier alliance has concocted an electronic arrangement that would assist with fruiting ranchers pick regular thing well on schedule. The CEO of Zaf Soft, Rabee James has chosen to deliver off a site donesloching.com. The reasoning is fundamental, inventive and explicitly it adds financial worth. donesloching.com would permit Australian ranchers and regular thing pickers to enroll on this site. While ranchers can select freely, the site additionally permits pack enrollment for regular thing pickers. Ordinary thing pickers are typical individuals living in Australia who wish to add to regular thing picking. These individuals frequently wish to work/get pay or on occasion be basic for the normal thing picking process for loosening up in a manner of speaking. The choice cycle for the ranchers is fundamental. Ranchers give their contact subtleties, ranch address or all the more all; their business charge subtleties

The checkteam goal will crash and burn accepting any player is ineligible then again if any player is recorded more

than once. [10 marks]

4CST.2000.6.5

8 Databases

Depict the principal plan of the ODMG standard for Object Data

The board. [10 marks]

What sponsorship is obliged trades? What locking modes are available, and

how are they used by the data base runtime structures? [4 marks]

The request language OQL is seen as a standard by the Object Management

Pack (OMG). How much is it like SQL, and in what ways gets it going

diffffer? [6 marks]

Fragment C

9 Semantics of Programming Languages

What's the importance here to say that two confifigurations of an undeniable change system

are bisimilar? [3 marks]

Depict a named change structure for a language of conveying processes

with input prefifixing (c(x). P), yield prefifixing (

ch Ei . P), a torpid collaboration (0),

choice (P + P0 ), equivalent construction (P|P0 ) and channel impediment ( c . P). You

may acknowledge there is an association E n which defifines when a number explanation E

evaluates to an entire number n. [7 marks]

For all of the going with sets of cycles, say assuming that they are bisimilar.

Legitimize your reaction for every circumstance.

(a)

ch 1i .((

ch 2i . 0) + (

ch 3i . 0)) and (

ch 1i . ch 2i . 0) + (

ch 1i . ch 3i . 0) [4 marks]

(b) P and c .((c(x). 0)|(

ch 1i . P)), where c doesn't occur in P

[6 marks]

10 Foundations of Functional Programming

Give as direct a lot of rules as you can for changing lambda math to a construction

where there are no bound elements referred to, but where there are numerous events

of the three standard combinator constants S, K and I. [6 marks]

Portray tree-revamps sensible for reducing verbalizations composed similarly as

combinators. [6 marks]

Figure out how you could deal with the issue of observing the potential gains of bound

factors assuming you some way or another happened to clearly unravel lambda investigation. [8 marks]

5

[TURN OVERCST.2000.6.6

11 Logic and Proof

For all of the given arrangements of terms, give a most expansive unififier or show why

none exists. (Here x, y, z are factors while a, b are consistent pictures.)

h(x, y, x) and

h(y, z, u)

h(x, y, z) and

h(f(y), z, x)

h(x, y, b) and

h(a, x, y)

h(x, y, z) and

h(g(y, y), g(z, z), g(u, u))

[4 marks]

A standard unifification computation takes a few terms t1 and t2 and returns a

substitution so much that t1 = t2. Show how this computation can be used to fifind

the unififier of a couple (n > 2) terms t1, t2, . . . , tn: a supplanting with the ultimate objective that

t1 = t2 = = tn. Show how the unififier is created from the unififiers

of n 1 arrangements of terms. (Expect that all important unififiers exist and ignore the

question of whether the unififiers are by and large expansive.) [6 marks]

Exhibit using objective the formula

A plan is expected for an oddity LED flasher that will be little, battery worked furthermore, mounted inside a conservative plate box as a limited time contrivance. The gadget has one LED in particular, and this produces splendid heartbeats at around one Hertz. All things being equal of being altogether standard, the beats are to be noticeably unpredictable, in a way which gets the notice of the cautious spectator. There will be a solitary creation run of 18 million units. Examine parts of the plan interaction, including the hardware, whether to incorporate a microchip, what, if any, ASIC innovation to utilize, the number of models to create and how they will be assessed, and testing of the item. [15 marks] The plan particular is currently different, so presently an importance is appended to the slight deviations from a normal beating design. Specifically, the example must gradually and more than once pass on an underlying mystery message of around 100 characters. It is OK that the translating activity would be hard for the man in the road, be that as it may, conceivable by a shrewd outsider or PC researcher. How does this impact the plan approach and cost? [5 marks] 5 [TURN OVER CST.96.3.6 8 Operating System Functions A PC with a 32-digit virtual tending to plot utilizes pages of size 4 Kbyte. Depict, with the guide of graphs, two reasonable plans for dealing with its virtual address space, contrasting them with respect with speed of access, productivity (of space), also, simplicity of memory dividing among processes. [10 marks] A Winchester-style plate has its head as of now situated 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) addressing the (requested) grouping of solicitations for plate tracks, give the grouping of plate tends to visited by the circle head under the SSTF, Sweep and C-SCAN plate planning calculations. For each situation momentarily depict the calculation, and figure the normal expense of a plate access concerning the mean number of tracks navigated per access. How is every one of these calculations one-sided in its administration of plate demands? Depict a calculation which lessens the predisposition. [10 marks] 9 Computation Theory Tell the best way to code the program and introductory information for a n-register machine into normal numbers p and d. In what sense do the codes p and d decide a special calculation? [9 marks] Utilizing your codes lay out an exact articulation of the Halting Problem for Register Machines. [3 marks] Accept that the It is overall undecidable to Halt Problem. Demonstrate that it can't be concluded whether an overall program p ends when the underlying information is zero in each register.

(a) Define what is a Turing machine and a Turing machine calculation. [7 marks] (b) What is implied by a fractional capacity from N

answer the question clearly