If p and q are atomic properties of states and R is a transition relation, then the property q is an immediate successor to p holds if and only if for every state s such that p s is true, there is at least one state s 0 such that R s s0 and q s0 are true

Subject:Computer SciencePrice:9.82 Bought3

Share With

If p and q are atomic properties of states and R is a transition relation, then the
property q is an immediate successor to p holds if and only if for every state s such
that p s is true, there is at least one state s
0
such that R s s0 and q s0 are true.
(a) Is it possible to express the property that q is an immediate successor to property
p in LTL? If so, write down the LTL formula that expresses it, if not give an
argument why it cannot be expressed. [10 marks]
(b) Is it possible to express the property that q is an immediate successor to property
p in CTL? If so, write down the CTL formula that expresses it, if not give an
argument why it cannot be expressed.

 

answer all que
(a) (i) Discuss the resilience of UWB impulse radio systems to multipath fading.
Explain how they avoid causing interference to traditional narrowband
communications systems. [5 marks]
(ii) The Wireless USB standard describes a high bandwidth radio protocol
intended to replace wired USB systems. In the course of its development,
both the 3.1-10.6 GHz UWB band and the unlicensed EHF radio band (57-
64 GHz) were considered for the physical layer. Suggest two advantages of
UWB over EHF in this context. Explain your answers. [4 marks]
(b) Describe how UWB radio can be used for pulse radar. Include in your answer
the two approaches for handling slow and fast-moving objects and explain why
there is a well-defined maximum operating distance for such systems. Explain
what effect separating the transmitters and receivers spatially would have.
 

(a) The ACID properties are often used to define transactional semantics.
(i) Define "atomicity" as used in the ACID context. [1 mark]
(ii) Define "durability" as used in the ACID context. [1 mark]
(b) Write-ahead logging is a commonly used scheme to accomplish transactional
semantics when storing a database on a block storage device, such as a hard
disk.
(i) Under what circumstances, during write-ahead log recovery, can a
transaction in the UNDO list be moved to the REDO list? [2 marks]
(ii) Synchronously flushing commit records to disk is expensive. How can we
safely reduce synchronous I/O operations on a high-throughput system
without sacrificing ACID properties? [2 marks]
(iii) Describe two performance changes that might arise from using your solution
to part (b)(ii). [2 marks]
(c) (i) Transaction records in a write-ahead logging scheme contain five fields:
hTransactionID, ObjID, Operation, OldValue, NewValuei, but storing the
complete old and new values can consume significant amounts of space. One
strategy that might be employed, for reversible operations being applied
to some data such as XOR by a constant, is to store only the constant
arguments, rather than the full before and after data. What problems
might occur as a result of this design choice? [4 marks]
(ii) Write-ahead logging systems must know the actual on-disk sector size for
the write-ahead log to behave correctly. An errant disk vendor decides to
rebrand its 512-byte sector disks as 2K-sector disks, and adjusts the value
reported back to the database system. How might this affect database
integrity? [4 marks]
(iii) Explain how a database vendor who is aware of the problem described in
part (c)(ii) mitigate this problem in software, and what limitations might
there be to this approach. [4 marks]
9 (TURN OVER)
CST.2013.5.10
9 Concurrent and Distributed Systems
Sun's Network File System (NFS) is the standard distributed file system used with
UNIX, and has gone through a progression of versions (2, 3, 4) that have gradually
improved performance and semantics.
(a) Remote procedure call (RPC)
(i) Explain how Sun RPC handle byte order (endianness). [2 marks]
(ii) This approach may result in unnecessary work. State when this occurs and
how might this be avoided. [2 marks]
(b) Network File System version 2 (NFSv2) and version 3 (NFSv3)
(i) A key design premise for NFS was that the server be "stateless" with respect
to the client. State what this means for distributed file locking in NFSv2
and NFSv3. [2 marks]
(ii) Another key design premise for NFSv2 was the "idempotence" of RPCs;
what does this mean? [2 marks]
(iii) One key improvement in NFSv3 was the addition of the READDIRPLUS
RPC. Explain why did this helps performance. [4 marks]
(iv) NFSv3 implements what is termed "close-to-open consistency" for file data
caching: if client C1 writes to a file, closes the file, and client C2 now
opens the file for read, then it must see the results of all writes issued by
C1 prior to close. However, if C2 opens the file before C1 has closed it,
then C2 may see some, all, or none of the writes issued by C1 (and in
arbitrary order). Close-to-open consistency is achieved through careful use
of synchronous RPC semantics, combined with file timestamp information
piggybacked onto server replies on all RPCs that operate on files.
Explain how close-to-open consistency allows performance to be improved.
[4 marks]
(v) NFSv3 adds a new RPC, ACCESS, allowing the client to delegate access
control checks at file-open time to the server, rather than performing them
on the client. This allows client and server security models to differ.
Explain how this addition also helps implement close-to-open consistency
in the presence of read caching.

 

(a) For each type variable α, the option type Oα is defined to be the PLC type
Oα
def = ∀β (β → (α → β) → β).
Prove that there are closed PLC expressions None, Some and Case with the
following typing and beta-conversion properties.
(i) ` None : ∀α (Oα)
(ii) ` Some : ∀α (α → Oα)
(iii) ` Case : ∀α, β (β → (α → β) → Oα → β)
(iv) Case α β y f (None α) =β y
(v) Case α β y f (Some α x) =β f x.
[10 marks]
(b) Use Case and None to define a closed PLC expression Lift of type
∀α1, α2 ((α1 → Oα2
) → Oα1 → Oα2
) with the property that for all closed
types τ and all closed expressions M of type Oα[τ/α], Lift τ τ (Some τ ) M =β
M. You may assume that any closed beta-normal form of type Oα[τ/α] is
beta-convertible either to None τ , or to Some τ N where N is a beta-normal form
of type τ . Any standard results about PLC that you use should be carefully
stated.

 

 

Pelagus Sensing Ltd is consulting you about the design of a system to monitor sea
water content along the coasts of Britain.
(a) Initially, imagine that fixed sensors need to be installed on buoys in the sea. The
system needs to be able to report data on sea water, such as temperature and
saline composition, ten times a day for more than a year over a coastal area of
one kilometre.
(i) List the challenges in defining the above defined architecture and suggest
a physical architecture of the system. [2 marks]
(ii) Describe the Low-Energy Adaptive Clustering Hierarchy (LEACH) approach, presented in the lectures. [2 marks]
(iii) Illustrate how LEACH can be employed to design a solution to the request
of Pelagus Sensing Ltd, indicating advantages and disadvantages.
[4 marks]
(b) Now imagine that Pelagus Sensing Ltd coordinates with zoologists monitoring
seals through sensors attached to the animals in the same coastal area. The
zoologists offer to put additional water temperature and saline composition
sensors on their seal tags to help Pelagus Sensing Ltd with sea water monitoring.
(i) Describe an effective physical architecture (specifying which radio the tags
would use and which other hardware devices should be present in the
network, if any) which would allow sensing data to be collected through
the animal tags and illustrate advantages and limitations. [2 marks]
(ii) Illustrate the MAC and routing protocols that you would use in such an
architecture explaining advantages over other protocols described in the
lectures. [4 marks]
(iii) Indicate how data aggregation could be used in this setting, highlighting
advantages and disadvantages. [3 marks]
(iv) If the mobile sensors attached to the seals were to be eventually
reprogrammed, which protocol would you suggest to be installed on them
and why? [3 marks]
8
CST.2012.9.9
8 Natural Language Processing
The following shows a simple context free grammar (CFG) for a fragment of English:
S -> NP VP NP -> Sandy
VP -> V NP Det -> a
VP -> V NP NP N -> puppy
VP -> V NP PP N -> garden
VP -> VP PP V -> walks
NP -> Det N V -> gives
PP -> P NP P -> to
NP -> Kim P -> in
(a) Give all analyses (parse trees) this grammar assigns to the following sentences:
Kim gives a puppy to Sandy.
Kim walks a puppy in a garden.
Which of the analyses is correct? [6 marks]
(b) The example sentences in (a) illustrate a type of ambiguity common in natural
languages. Characterise it, and explain how it arises. [4 marks]
(c) Indicate at least two (other) sources of incorrect analyses in the above grammar,
illustrating them with the corresponding ungrammatical sentences. Explain
what causes the incorrect analysis. [4 marks]
(d) The incorrect analyses in (a) could be avoided using an appropriate feature
structure based grammar. Describe the exact mechanism for how this can be
done. Does this treatment also deal with your incorrect analyses in (c)?

 

Write  program to Print first 5 even numbers using for loop

Write  java program that asks the user to enter 2 integers, obtains them from the user, determines if they are even or odd numbers and prints their sum, product, difference, and quotient

Write  program that takes three numbers as separate inputs and prints their sum.

Write  program to generate new array for store the elements of two another

 

 An enthusiast for programming with closures proposes extending Java so that the following method definition would be valid: Closure myCounter (int start) { int counter = start; return { System.out.println (counter ++); } } The programmer intends that no output would be produced when this method is executed, but that it would return an object of a new type, Closure, and that invoking apply() on that object would cause successive counter values to be printed. By using an inner class definition, show how this example could be re-written as a valid Java program.

 

Error("Supplied value is not numeric");
 }
}
}

/// <summary>
/// Gets a validated Boolean value.
/// </summary>
/// <param name="prompt">Text used to ask the user for input.</param>
/// <returns>A Boolean value supplied by the user.</returns>
public static bool GetBool(string prompt)
{
while (true)
{
 string response = GetInput(prompt);

 bool result;

 if (bool.TryParse(response, out result))
 {
  return result;
 }
 else
 {
  Error("Supplied value is not a boolean");
 }
}
}

 

/// <summary>
/// Gets a single line of text from user.
/// </summary>
/// <param name="prompt">Text used to ask the user for input.</param>
/// <returns>Returns a single line of text from user.</returns>
public static string GetInput( string prompt ) {
Console.WriteLine( "{0}:", prompt );
return Console.ReadLine();
}

/// <summary>
/// Gets a single line of text from user. The text is processed one
/// character at a time, and the input is concealed.
/// </summary>
/// <param name="prompt">Text used to ask the user for input.</param>
/// <returns>Returns a single line of text from user.</returns>
public static string GetPassword( string prompt ) {
Console.WriteLine( "{0}:", prompt );
StringBuilder password = new System.Text.StringBuilder();

while ( true ) {
 var keyInfo = Console.ReadKey(intercept: true);
 var key = keyInfo.Key;

 if ( key == ConsoleKey.Enter )
  break;
 else if ( key == ConsoleKey.Backspace ) {
  if ( password.Length > 0 ) {
   Console.Write( "b b" );
   password.Remove( password.Length - 1, 1 );
  }
 }
 else {
  Console.Write( "*" );
  password.Append( keyInfo.KeyChar );
 }
}

Console.WriteLine();
return password.ToString();
}

/// <summary>
/// Displays an error message and asks user to try again.
/// </summary>
/// <param name="msg">The message to display</param>
public static void Error( string msg ) {
Console.WriteLine( $"{msg}, please try again" );
Console.WriteLine();
}

/// <summary>
/// Displays the content of an arbitrary object.
/// </summary>
/// <param name="msg">The object to display</param>
public static void Message( object msg ) {
Console.WriteLine( msg );
Console.WriteLine();
}
}
}

(a) Explain the core ideas of strictness analysis, including the abstract values used for abstracting non-function values and what concrete values
they represent. Briefly explain how program functions f are abstracted
to strictness functions f
]
. Give the abstractions of λ(x,y).x+y and
λ(x,y). if random() then x else y. [5 marks]
(b) Justify or correct the following statements: (i) "since abstract interpretation
replaces real-world computation with a directly corresponding abstract computation then strictness analysis fails to terminate on non-terminating programs";
and (ii) "when a strict function is applied to an expression e then e is necessarily
evaluated during the call". [4 marks]
(c) We now wish to extend strictness analysis from simple int expressions to allow
also (lazy) int list expressions. These represent lists whose head and tail
components are only evaluated when required. Wadler suggested capturing
strictness-like properties on lazy lists using an abstract interpretation with four
abstract values for int list concrete values:
0: non-termination
∞: a chain of cons cells, either infinite or having some tail component which
does not terminate
0∈: a chain of cons cells ending in nil but having at least one member which
does not terminate
1∈: a possibly empty chain of cons cells ending in nil every member of which
terminates
By analogy with ordinary strictness functions, give abstract interpretations in
truth-table form (noting that values of type int list have four values rather
than the standard two) for the following functions involving lazy list values:
(i) λ(x:int list). nil [1 mark]
(ii) λ(x:int list). cons(42,x) [1 mark]
(iii) λ(x,y:int list). if random() then x else y
Explain how you resolved any choice which arose. [3 marks]
(iv) hd [2 marks]
(v) tl [1 mark]
(vi) append [2 marks]
(vii) reverse [1 mark]
10
CST.2012.9.11
10 Principles of Communications
(a) Describe the operation of Distance Vector (D-V) and Link State (L-S) routing
algorithms, with particular reference to their complexity in terms of number of
messages given the number of nodes and edges in the network. [5 marks each]
(b) Small world networks are a particular form of random graph which exhibit
clustering.
(i) Describe two common ways this clustering can occur in the way the graph
is created. [3 marks each]
(ii) Discuss the design of a routing algorithm for a small world network. Would
you stick with existing schemes like D-V or L-S? [4 marks]
11 (TURN OVER)
CST.2012.9.12
11 System-on-Chip Design
(a) Give a basic formula for modelling delay in logic circuits once wiring length is
known. [2 marks]

Give the name of this modification, say why is it performed and fully explain
the role of the additional latch. [4 marks]
(d) Three power saving techniques used in current SoCs are dynamic voltage and
frequency scaling (DVS), clock gating and power supply gating. Compare and
contrast these three techniques in terms of
(i) physical granularity [3 marks]
(ii) temporal granularity [3 marks]
(iii) the manual complexity they add to the design flow [3 marks]
(e) Including power consumption, discuss what design considerations result in
a product using an FPGA (field-programmable gate array) rather than an
application-specific integrated circuit (ASIC)?