A binary tree has nodes whose values are non-empty lists

Subject:Computer SciencePrice:9.82 Bought3

Share With

A binary tree has nodes whose values are non-empty lists. A tree node is
represented using a term that takes the form Left-SomeList+Right or nil
(note that parentheses can be used to enforce precedence). For example, the
following term would be a valid tree:
nil-[root,1,2]+(nil-[child,4]+nil)
(i) Write a predicate preorder(+Tree,-ValueList) that unifies ValueList
with a list containing all of the tree nodes' values from a pre-order tree
walk (i.e. emit node value, then left subtree, then right subtree). The
predicate should fail if any of the tree nodes' values are not of the correct
form. For the above example tree, preorder/2 would unify ValueList
with [[root,1,2],[child,4]]. You may assume that append/3 has
been defined already. [6 marks]
(ii) Now write a predicate preorderdl/2 that behaves exactly like your
preorder/2 predicate, but in its implementation makes use of difference
lists, instead of querying append/3.

(a) Describe the waterfall model for software development and list three of its
advantages for software development. [5 marks]
(b) When discussing system development Fred Brooks says, "plan to throw one
away - you will anyway". What disadvantages of the waterfall model is he
referring to? Outline an alternative software development model that deals
with these disadvantages.
(c) You work for a large "social networking" company which has recently
introduced a one-to-one chat mechanism, promising that they will never censor
conversations. Users are now reporting that their friends' computers are being
compromised by malicious software. When users click on links within messages
sent by this malicious software, their machine is also compromised, and spreads
the infection still further. A crisis meeting has decided that the chat software
must be modified to block this "worm" behaviour.

 

Consider the calculation of light emanating from a point on a surface.
(a) What is meant by the following terms? Explain how their contribution to the
overall amount of reflected light is calculated.
(i) Ambient illumination [2 marks]
(ii) Diffuse reflection [4 marks]
(iii) Specular reflection [4 marks]
(b) Suppose that the surface is represented as a polyhedral mesh with triangular
faces. Explain how illumination is calculated across a face using each of the
following.
(i) Gouraud shading [3 marks]
(ii) Phong shading [3 marks]
(c) Explain where the calculations for Gouraud and Phong shading should be
performed when using OpenGL.

 

 

In this question, where appropriate, you may use a short fragment of code to
complement your explanation.
(a) What is the difference between declaration and definition?
(b) Describe the layout of the memory components: Dynamic Memory Allocation,
Data Segment, Code Segment and Stack. You may use an illustration as part
of your explanation.
(c) Using an example, explain what stack unwinding is in C++.
(d) How may I use template meta programming to inline recursive functions?
(e) Why did the designers of the C++ language decide to make an empty class
1 byte in length?
[4 marks each]
4 Compiler Construction
(a) In a stack-based runtime system, what problem does the static link method
attempt to solve, and how does it work? [4 marks]
(b) Can static linking be used to implement a language with first-class functions?
If yes, then explain how. If no, give an example and explain how static linking
fails. [6 marks]
(c) Explain how exceptions (ML-like raise and handle) could be implemented
with a stack-oriented machine. [5 marks]
(d) A program may evaluate to an exception that has been raised all the way
to the top-level and never handled. Discuss how you might modify your
implementation in part (c) to dump debugging information when such toplevel exceptions are raised. The debugging information should include some
description of the state of the computation just before the top-level exception
was raised. [5 marks]
4
CST.2011.3.5
5 Compiler Construction
Consider a simple grammar for arithmetic expressions:
E ::= n | x | −E | E + E | ( E )
with n ranging over integer constants and x ranging over variables. We want to
compile expressions to code for a simple stack-based machine with the following
instruction set.
instruction meaning
pushvar k push the value of the k-th variable on top of stack
push n push n on top of stack
add replace the top two stack items with their sum
neg replace the top stack item with its negation
For this problem, we will not worry about how variables are bound to values nor
how abstract syntax trees are produced.
(a) How will your compiler generate code from expressions of the form −E?
[4 marks]
(b) How will your compiler generate code from expressions of the form E1 + E2?
[4 marks]
(c) What code will your compiler generate for the expression -(-x + (17 + y))?
[4 marks]
(d) Suppose we now want to extend the language of integer expressions with
multiplication
E ::= · · · | E ∗ E
but we cannot extend the machine with an instruction for multiplication.
Can you implement this extended language directly with the machine
instruction set presented above? If not, suggest a minimal extension to the
instruction set that allows for the implementation of multiplication using the
addition from the instruction set. Explain the semantics of your extensions
and how you would use them to implement multiplication. [8 marks]
5 (TURN OVER)
CST.2011.3.6
6 Concepts in Programming Languages
(a) Give one difference and one similarity between the programming languages:
(i) Algol and SIMULA [2 marks]
(ii) LISP and Smalltalk [2 marks]
(b) What is the type of the expression fn f => fn x => f(f(x)) inferred by
the SML interpreter? Explain your answer. [6 marks]
(c) Give an example in the SML Modules language of two distinct signatures, say
IN and OUT, and of a functor that takes structures matching IN to produce
structures matching OUT. [6 marks]
(d) Comment on the mechanism for parameter-passing in the programming
language Scala. [4 marks]
You may wish to consider the following two code samples.
def whileLoop( cond: => Boolean )( comm: => Unit )
{ if( cond ) comm; whileLoop( cond )( comm ) }
def qsort[T]( xs: Array[T] )( implicit o: Ord[T] ): Array[T]
= if( xs.length <= 1 ) xs else
{ val pivot = xs( xs.length/2 )
Array.concat
( qsort( xs filter (x => x.lt(x,pivot)) ) ,
xs filter (x => x == pivot ) ,
qsort( xs filter (x => x.lt(pivot,x)) ) ) }
6
CST.2011.3.7
7 Further Java
In this question you will need to fill in missing parts of a Java program. You may
ignore any exception handling and will not be penalised for minor syntactic errors.
You are provided with a class Eval:
public class Eval {
public static int f(Record r) { ... }
}
(a) Add another method Integer maxf(Iterator<Record> it) to the class
Eval. Your method should return the maximum value computed by f for
every Record returned by the iterator or null if there are no records available.
The relevant portion of the Iterator interface is as follows:
interface Iterator<T> {
// return true if there are more values available
public boolean hasNext();
// return the available value and advance to the next one
public T next();
}
[5 marks]
(b) Complete the methods run() and join() in the following abstract class. You
may add additional fields or methods if you wish.
abstract class Joinable implements Runnable {
abstract void exec();
final public void run() {
// ... call the exec() method ...
}
void join() throws InterruptedException {
// block the calling thread until exec() completes in run()
}
}
[7 marks]
(c) Provide a method Integer parmaxf(Iterator<Record> it, int n) which
is functionally equivalent to Eval.maxf, except that it should create n parallel
threads of execution to speed up the calculation of the result. You may assume
that Iterator<Record> is thread-safe. You may find it helpful to subclass the
Joinable class.

 

converting the java class into a python class

class Library:
 
def __init__(self):
 
def addAuthor(self, Author):
 
def addPublisher(self, Publisher):
 
def addBook(self, Book):
 

Here is the original java class:

import java.util.ArrayList;
import java.util.List;

public class Library {

private List<Book> books;
private List<Author> authors;
private List<Publisher> publishers;

public Library(){
this.books=new ArrayList<>();
this.authors=new ArrayList<>();
this.publishers=new ArrayList<>();
}

public void addAuthor(String name){
authors.add(new Author(name));
}

public void addPublisher(String name, String address){
publishers.add( new Publisher(name,address));
}

public void addBook(String title,String location, int yearPub, String authorName, String publisherName ) throws AuthorNotFoundException, PublisherNotFoundException {
//Find Author
Author author=null;
for (Author a:authors){
if (a.getName().equals(authorName)){
author = a;
break;
}
}
if (author==null) {
throw new AuthorNotFoundException("Author is not in the system");
}

//Find Publisher
Publisher publisher=null;
for (Publisher p:publishers){
if (p.getName().equals(publisherName)){
publisher=p;
break;
}
}
if (publisher==null){
throw new PublisherNotFoundException("Publisher is not in the system");
}

books.add(new Book(title, location,yearPub,author,publisher));
}

public List<Book> getBooks(){return books;}
public List<Author> getAuthors(){return authors;}
public List<Publisher> getPublishers(){return publishers;}

}

write  c program to show the relation btw variables, addresses, and pointers

Write  C Program to demonstrate Optimal Page Replacement Algorithm

 C program to find the greatest common divisor of two numbers .

 

How  to format the code below and have it in the same layout and create the output

 

cout << "*** Max Temperature for this Week *******" <<

 

endl;

 

cout << " Monday Tuesday Wednesday Thursday Friday Average" <<

 

endl;

 

 

: Write  program that takes n number of elements from user (where, n is specified by user), stores data in an array and calculates the average of those numbers.
Java program to clone an array list to another array list. 2. Write a Java program to empty an array list. 3) Write a Java program to test an array list is empty or not. 4)
Java program to reverse an array of integer values.

Write  Java program to find the duplicate values of an array of integer value

 

Consider display technologies for hand-held devices.
(a) Explain the principles of operation of each of the following.
Note: You may illustrate your answers with a diagram.
(i) Liquid crystal displays [5 marks]
(ii) Electrophoretic (electronic paper) displays [5 marks]
(b) Compare and contrast their characteristics. [6 marks]
(c) Explain how liquid crystal and electrophoretic displays can show coloured
images.

 

Consider the following Java class that is intended to represent a specific day in an
eight-week University term.
public class TermDay {
public int day; // The day of the week as a number 0-6
public int week; // The week of the term as a number 0-7
};
(a) Create a class EncapsulatedTermDay, which applies the principles of data
encapsulation as an alternative to TermDay. Your modified class should throw
an exception if an invalid day of the week or week number is specified.
[4 marks]
(b) The use of two int variables to represent the day and the week requires
64 bits of storage. How many bits are actually required? Adapt
EncapsulatedTermDay class to achieve the same functionality using only one
member variable of a primitive type. You should justify your choice of type.
[4 marks]
(c) Create a class ImmutableTermDay that is an immutable version of TermDay.
[3 marks]
(d) By applying one or more appropriate design patterns and adapting
ImmutableTermDay appropriately, show how to ensure that only one
ImmutableTermDay object is ever created for a given day/week combination.

Consider rendering a triangular mesh using OpenGL. A uniform material is used for
the entire mesh and the reflection model of the material consists of ambient, diffuse
and specular components. There are two point light sources in the scene. Given these
assumptions, answer the following questions:
(a) Gourand and Phong shading are two different methods of interpolating colours
between vertices. Explain how each method interpolates colours. [5 marks]
(b) Discuss the trade-offs in terms of quality and computational costs for Phong and
Gourand shading. Assume that the number of rendered pixels is much larger
than the number of vertices. What kind of artefacts can one of the methods
produce and what is the reason for those artefacts?

(a) Explain the principles of operation of each of the following.
Note: You may illustrate your answers with a diagram.
(i) Liquid crystal displays [5 marks]
(ii) Electrophoretic (electronic paper) displays [5 marks]
(b) Compare and contrast their characteristics. [6 marks]
(c) Explain how liquid crystal and electrophoretic displays can show coloured
images.

 

 

Discuss the lessons learned from the London Ambulance Service disaster under the
following headings:
(a) capturing user requirements
(b) project management
(c) quality assurance
(d) testing [16 marks]
What in your view would be the single most important measure to take in
developing a mission-critical system in order to reduce the likelihood of such a
disaster? [4 marks]
7 [TURN OVER
CST.98.2.8
9 Software Engineering II
Consider the following code fragment, whose purpose is to form the product m × n
in the integer variable x:
x := 0; i := n;
while i<>0 do
begin
x := x+m;
i := i-1
end;
What is the loop invariant? [3 marks]
Argue informally that the invariant holds at the appropriate points. Using the
invariant, show that the loop is correct. [5 marks]
Outline the main features of the Z specification language. [9 marks]
To what extent can a formal specification language help a safety-critical system
meet the requirement of being extremely reliable? [3 marks]
10 Structured Hardware Design
The user interface to a microwave oven consists of a washable membrane keyboard
and an LCD panel. All of the interface electronics is to be integrated onto a single
ASIC (application-specific integrated circuit).
(a) Briefly sketch or describe the overall structure of the microwave oven and define
the connections to the ASIC. [5 marks]
(b) The keyboard has 25 keys that are simple push-to-make switches. For minimal
pin use, these are to be scan multiplexed. Sketch or describe the way the
keypad is connected to the ASIC and the circuitry to scan the keypad. How
is debouncing handled? [12 marks]
(c) If the main functions within the ASIC are implemented with software on an
imbedded microprocessor, discuss whether it is worthwhile having dedicated
electronics to scan the keyboard and display.

 

address all