Explain, with prose and no more than 15 lines of pseudocode, the "Jarvis's march" algorithm for finding the convex hull of a set of points

Subject:Computer SciencePrice:9.82 Bought3

Share With

Explain, with prose and no more than 15 lines of pseudocode, the "Jarvis's
march" algorithm for finding the convex hull of a set of points. Marks awarded
for: clarity of explanation, legibility of pseudocode, correctness of algorithm.
(b) Consider the following claim: "The cross-product trick can be used as a plug-in
substitution for the comparison operation between two arguments that gives
a three-way result (namely <, > or =). Therefore, given an arbitrary set of
2D vectors all starting from the origin, computing any angles, merely by applying a
standard sort algorithm with the comparison operation replaced by the crossproduct trick".
(i) Explain the "cross-product trick". 
 

 

 

address every question

(a) Write brief notes on exceptions in ML and on the functions and control
structures available for programming with them. [6 marks]
Parts (b) and (c) make use of the following ML exception:
exception Olive;
(b) Code in ML a function called cannot which takes two arguments, a function f
and a value x. Define the cannot function in such a way that it returns true
if and only if evaluation of f(x) causes exception Olive. For all other inputs,
it should return false. [Hint: evaluation of f(x) may cause exceptions other
than Olive.]
(c) Consider the following ML datatype and functions bun and cheese.
datatype 'a tree = Leaf of 'a
| Branch of 'a tree * 'a tree;
fun bun (x,Leaf y) = if x=y then raise Olive else Leaf y
| bun (x,Branch (t1,t2)) = Branch (bun(x,t1),bun(x,t2))
fun cheese (x,t) = if cannot(bun,(x,t)) then Leaf x else bun(x,t)
(i) Write down the type of cheese. [3 marks]
(ii) Write a function that is equivalent to cheese but makes no use of
exceptions. Briefly explain why your function is equivalent to cheese.
[7 marks]
3 (TURN OVER)
CST.2011.1.4
SECTION B
3 Discrete Mathematics I
This question is about structured proofs.
(a) Write down the introduction and elimination rules for implication and
negation. [4 marks]
(b) Using the rules from part (a), give a structured proof of
(P ⇒ Q) ⇒ ((¬Q) ⇒ (¬P))

 

 

(a) Consider integer division of one two's-complement binary number by another.
Programming languages may vary in the result when one argument is negative.
What differing conventions might they be following? [2 marks]
(b) Describe carefully, or give pseudocode for, the standard binary integer longdivision procedure. What common fault must it guard against? [6 marks]
(c) Describe the iteration technique known as successive approximation by bisection.
What does it have in common with standard long division? [3 marks]
(d) Describe carefully, or give code changes to, the standard long division algorithm
from part (b) so that it computes two bits of result per iteration. [3 marks]
(e) Single-precision floating-point representation uses a sign bit, eight bits of
exponent, a hidden bit and 23 bits of stored mantissa. Using a consistent
encoding, similar or identical to the IEEE standard, give hexadecimal
representations of the following four numbers: 1.0, 0.125, 4096.0 and −0.0.
[4 marks]
(f ) Consider different versions of an optimising compiler, each of which uses IEEE
standard representation for all variables. Give two reasons why they might
compile a floating-point program into code that, when run, produces differing
results.

 

 

A picnicker brings hot black coffee and cold milk in two identical insulated flasks and
then mixes them for his drink. His friend claims that the drink would have ended up
the same temperature if he had mixed the two at home and brought one flask.
Note: The temperature of an object is the heat energy within it divided by its heat
capacity. The rate of heat energy flow from a hotter to a cooler object is their
temperature difference divided by their insulation resistance. When two fluids are
mixed the resultant temperature is the sum of their initial temperatures weighted by
their proportions.
(a) Give a suitable state vector for a simple, finite-difference, time domain simulation
of the drink system. [3 marks]
(b) List the initial values and any other parameters that are needed for the
simulation. Sketch pseudocode for each of the two scenarios. Assume constant
ambient temperature and state any further assumptions. [7 marks]
(c) How would you select a fixed time step for these two simulations or should the
time steps be adaptive? What accuracy might you expect to achieve? Is the
choice of time step likely to affect whether the friend is proved right or wrong?
[3 marks]
(d) Suppose the two-flask simulation were phrased in flow-matrix form. What
determines how many rows the matrix would have? Is this a sensible approach
to modelling the system? [4 marks]
(e) Why is backwards stability normally a useful property of numerical methods?
Does that notion apply to this simulation? 

Let a dab be a set of disjoint segments on the real axis.
(a) Write a Dab class in Java that supports equality testing between two dabs
in linear time. Provide only the data members without any constructors or
methods, and highlight any noteworthy features and invariants.
Note: You may not use any pre-made lists, resizable arrays or other library
collections of any kind; use only integers, doubles, pointers, arrays and classes.
You are allowed to define additional classes if necessary.

 

 

Write  program using arrays in Java, to accept marks obtained in C Programming course for 'n' students. Sort and print the highest mark.

Write a program to print all alphabets from a to z. - using while loop

Write   program to sort a given array list
write function called productEven, that takes as its parameter an input file. The function should read two integers and calculate the total product of only even numbers between them

 

 Use the DPLL method to find a model satisfying the following set of clauses, or to prove that no such model exists. {P, Q} {R} {Q, ¬S, ¬Q} {¬Q, ¬R, S} {P, ¬Q} {P, Q, ¬S} {P, ¬R, S} {¬P, ¬S} [6 marks] (c) Describe the for constructing a BDD.using the variable order P < Q < R < S) for: (¬P ∨ (Q ∧ S)) ∨ (S ∨ (¬R ∨ S))

 

#include <iostream>

using namespace std;

void selectionSortArray(int [], int);

void displayArray(int[], int);

int main()

{

int data[] = {9, 2, 0, 11, 5, 43, 22, 3, 102, 17, -3};

int size = 11;

cout << "The values before the selection sort is performed are:" << endl;

displayArray(data, size);

selectionSortArray(data, size);

cout << "The values after the selection sort is performed are:" << endl;

displayArray(data,size);

system("pause");

return 0;

}

void displayArray(int array[], int length)

{

for (int count = 0; count < length; count++)

cout << array[count] << " ";

cout <<endl;

}

void selectionSortArray(int list[], int length)

{

int seek;

int minCount;

int minValue;

for (seek = 0; seek < (length-1);seek++)

{

minCount = seek;

minValue = list[seek];

for(int index = seek + 1; index < length; index++)

{

if(list[index] < minValue)

{

minValue = list[index];

minCount = index;

}

}

list[minCount] = list[seek];

list[seek] = minValue;

}

}

 selectedSortArray so that finding the index of the smallest element in the remainder of the list is done by a separate function. The definition of selectionSortArray function should be as following:

int getIndexOfMin(int list[], int first, int length)

/* function takes an array of int of size length and returns the index of the smallest element between positions first and length -1.

*/

{

// Complete function body here

}

void mySwap(int list[], int index1, int index2)

/* function swaps element at position index1 in array list with element at position index2 */

{

 

}

void selectionSortArray(int list[], int length)

{

int seek; // array position currently being put in order

int indexOfMin; // location of smallest value found

int minValue; // holds the smallest value found

for (seek = 0; seek < (length-1);seek++) // outer loop performs the swap

// and then increments seek

{

indexOfMin = getIndexOfMin(list, seek, length);

mySwap(list, seek, indexOfMin);

}

}

Write  c program to find the greatest number between two numbers.

Write  C++ Program to calculate Volume of Cube using constructor and destructor.

Write   program to find the input number is even or odd.

Write  C++ program to calculate the sum of two numbers

 

The chaining collision-resolution scheme for hash tables uses an array where each
element is a linked list.
(a) For a hash table that uses chaining to resolve collisions with an array of length
m and n keys inserted, the average asymptotic complexity for search and insert
is O(1 + n
m
).
(i) Explain why search and insert are considered to be O(1) and not O(n) in
practice. [2 marks]
(ii) Give the worst-case complexities for search and insert. State the factors
that determine the performance observed in practice. [5 marks]
(b) An alternative hash-table implementation replaces the linked lists in each slot
with red-black trees. Discuss the advantages and disadvantages of this change.
[4 marks]
(c) The linked lists may also be replaced by dynamically sized arrays. When full,
an array is expanded by a factor of k.
(i) Derive a potential to compute the amortised cost of adding an element to
such an array using the potential method. On inserting an element that
triggers an expansion, your potential should be zero just after the expansion
but before the insertion of the new element. [3 marks]
(ii) Use your potential to compute the amortised cost of adding an element to
the array. [3 marks]
(iii) What factors would influence your choice of k when using the arrays in a
hash table? [3 marks]
11 (TURN OVER)
CST0.2018.1.12
10 Algorithms
(a) Let dijkstra_path(g, a, b) be an implementation of Dijkstra's shortest path
algorithm that returns the shortest path from node a to node b in a graph g.
Prove that the implementation can safely terminate when it first encounters
node b. [5 marks]
(b) Consider all paths in a graph from a to b, ordered from shortest to longest.
Assuming p = dijkstra_path(g, a, b) is the first path in this collection, an
algorithm to find the second path considers deviations from the vertices of p.
An algorithm to do this is given below.
function second_path(Graph g, Vertex a, Vertex b):
p = dijkstra_path(g,a,b)
best_so_far = []
for i = 1 to len(p)-1:
t = p[:i] # First i elements of p
c = g.get_edge_weight(p[i], p[i+1])
g.set_edge_weight(p[i], p[i+1], infinity)
t.append(dijkstra_path(g,p[i],b))
if (len(best_so_far) == 0 or
cost(t) < cost(best_so_far)):
best_so_far = t
g.set_edge_weight(p[i], p[i+1], c)
return best_so_far
(i) Show the steps of this algorithm on the following graph, from A to B.
[5 marks]
(ii) What is the asymptotic complexity of this algorithm in terms of the number
of edges, E, and the number of vertices, V ? Assume the implementation
of Dijkstra's algorithm uses a priority queue based on a Fibonacci heap.
[4 mark

 

You are to design a 2-bit multiplier which takes inputs b1b0 a1a0 representing two
unsigned 2-bit numbers and produces a 4-bit result in the outputs z3z2z1z0.
(a) Give a truth table for the outputs. [5 marks]
(b) Give simplified forms for z3z2z1z0. [5 marks]
(c) Discuss alternatives for producing an 8-bit multiplier with special consideration
for gate count and speed. Give a full design for one of the alternatives for a
4-bit adder. [10 marks]
3 Digital Electronics
You are to design a circuit with the following inputs:
• D - the data input
• R - a reset input (active high)
• CLK - a clock
and one output, ERR.
ERR should be high if an error is found. An error occurs if, since the last reset, in
the sequence of D values which occur on the rising edge of the clock the number of
zeros exceeds the number of ones by three, or vice versa. R should be sampled on
the rising edge of the clock. When R is asserted, the D value is ignored.
(a) Give a state diagram for the circuit. [10 marks]
(b) Implement the circuit using J-K flip flops. [10 marks]
4
CST.98.2.5
SECTION C
4 Probability
A practical class which is conducted in Cockcroft 4 makes use of 10 DECstations
and 5 PWFs. It is known that the probability of any particular DECstation failing
during the class is a and the probability of any particular PWF failing during the
class is b. All failures may be assumed to be independent.
After the most recent class the demonstrator reported that two workstations had
failed. Write expressions for:
(a) the probability that both failures were of DECstations [5 marks]
(b) the probability that one DECstation failed and one PWF failed [5 marks]
(c) the probability that both failures were of PWFs [5 marks]
Hence or otherwise show that if a = b the probabilities in the three cases are
respectively 9/21, 10/21 and 2/21. 

 

The Gambler's Ruin Problem presupposes a game for two players, A and B, each
of whom has a pile of £1 coins. The game proceeds by a sequence of turns and at
each turn A wins with probability p and B wins with probability q (and p + q = 1).
When the outcome of a turn is known, £1 is transferred from the loser's pile to the
winner's pile. Play continues until one player is ruined by having no money left.
At a particular stage in the game A has £n and B has £(a − n). If un is
the probability that A ultimately wins from this position the following difference
equation holds:
un = p un+1 + q un−1 provided 0 < n < a
The right-hand side makes use of the multiplication theorem twice and the addition
rule once. Explain why such usages are justified. [3 marks]
Provide suitable boundary conditions to reflect the two possible end-of-game
outcomes. [2 marks]
Suppose that dn represents the duration of play, the expected number of turns from
the position described until the end of the game. Write down the related difference
equation for dn and provide suitable boundary conditions.