Define the higher order function foldl ("fold left") such that foldl (op+) (0,[1,2,3]) evaluates to 6, and foldl (op^) ("doh",["ray","me"]) evaluates to "dohrayme" (Recall that ^ is a function to concatenate two strings.) [3 marks] Define the higher order function foldr ("fold right") such that foldr (op+) (0,[1,2,3]) evaluates to 6, and foldr (op^) ("doh",["ray","me"]) evaluates to "raymedoh" [3 marks] Use either foldl or foldr to write the following functions. (a) The function append, such that the expression append([1,2],[3,4]) evaluates to [1,2,3,4]. [2 marks] (b) The function length, such that the expression length([1,6,9,15]) evaluates to 4. [4 marks] (c) The function map, such that the expression map (fn x => x+1) [1,2,3] evaluates to [2,3,4]. [4 marks] In some cases, foldl and foldr can be interchanged, i.e. the theorem foldl f (e,xs) = foldr f (e,xs) holds. Assuming that the list xs is finite, give two conditions concerning f and e that are sufficient for this theorem to be true. [Hint: you may find it helpful to consider the expansion of the expressions foldl (op+) (0,[1,2,3]) and foldr (op+) (0,[1,2,3]).] [4 marks] 6 CST.99.13.7 11 Computer Vision Contrast the use of linear versus non-linear operators in computer vision, giving at least one example of each. What can linear operators accomplish, and what are their fundamental limitations? With non-linear operators, what heavy price must be paid and what are the potential benefits? [8 marks] When shape descriptors such as "codons" or Fourier boundary descriptors are used to encode the closed 2D shape of an object in an image, how can invariances for size, position, and orientation be achieved? Why are these goals important for pattern recognition and classification? [6 marks] Define the general form of "superquadrics" used as volumetric primitives for describing 3D objects. What are their strengths and their limitations?

What impact would changing from S-2PL to ordinary 2PL have (i) during a transaction's execution, (ii) when a transaction attempts to commit and (iii) when a transaction aborts? [6 marks] (d) You discover that the system does not perform as well as intended using S-2PL (measured in terms of the mean number of transactions that commit each second). Suggest why this may be in the following situations and describe an enhancement or alternative mechanism for concurrency control for each: (i) The workload generates frequent contention for locks. The commit rate sometimes drops to (and then remains at) zero. [2 marks] (ii) Some transactions update several objects, then perform private computation for a long period of time before making one final update. [2 marks] (iii) Contention is extremely rare.

Implement the method existConsecutive(LinkedNode vals), which returns true if there are duplicate values next to each other.

import java.util.Scanner;

class LinkedNode { T value; LinkedNode next;

public LinkedNode(T value, LinkedNode next) { this.value = value; this.next = next; } }

public class Test { public static void main(String[] args) { Scanner stdin = new Scanner(System.in);

LinkedNode head = null;

while (stdin.hasNext()) { head = new LinkedNode(Integer.valueOf(stdin.nextInt()), head); }

System.out.println(existConsecutive(head));

}

public static boolean existConsecutive(LinkedNode head) { code starts here

code ends here

} }

package linked;

class CharNode { private char ch; private CharNode next;

CharNode(char ch) { this.ch = ch; }

CharNode getNext() { return next; }

void setNext(CharNode next) { this.next = next; }

char getData() { return ch; } }

---------------------------------

package linked;

import java.util.*;

public class CharLinkedList { private CharNode head; // Empty if head and private CharNode tail; // tail are null

public CharLinkedList() { }

public CharLinkedList(CharNode head, CharNode tail) { this.head = head; this.tail = tail; }

public CharLinkedList(String s) { for (int i=s.length()-1; i>=0; i--) insertAtHead(s.charAt(i)); }

public CharNode find(char ch) { CharNode n = head;

if(head == null) return null; while(n!=null) { if(n.getData() == ch) { return n; } n = n.getNext(); } return null; }

//the first node in the list whose data is equal to ch.

public void duplicate(char ch) { CharNode current = find(ch); if(current == null) { throw new IllegalArgumentException("The node is not exist."); //This code executes, if there is a duplicate. }

if(head == current) { //If ch is the first node itself, (Note that, this condition also handles the situation of single node list) this.insertAtHead(ch); } else if(tail == current) { CharNode node = new CharNode(ch); tail.setNext(node); tail = node; tail.setNext(null); } else { CharNode node = new CharNode(ch); node.setNext(current.getNext()); current.setNext(node); } }

public void insertAtHead(char ch) { assert hasIntegrity(); // Precondition CharNode node = new CharNode(ch); node.setNext(head); head = node; if (tail == null) tail = node; // Corner case: inserting into empty node assert hasIntegrity(); // Postcondition }

public String toString() { String s = ""; CharNode node = head; while (node != null) { s += node.getData(); node = node.getNext(); } return s; }

boolean hasIntegrity() {

if (head == null || tail == null) return head == null && tail == null; // Check tail integrity (tail.next must be null). if (tail.getNext() != null) return false; // Check for loops. Set visitedNodes = new HashSet<>(); CharNode node = head; while (node != null) { if (visitedNodes.contains(node)) return false; visitedNodes.add(node); // First visit to this node node = node.getNext(); }

// Make sure tail is reachable from head. CharNode node1 = head; while (node1 != null && node1 != tail) node1 = node1.getNext(); return node1 == tail; } }

Write program that prompts the user to enter the name of a file. The program encoded sentences in the file and writes the encoded sentences to the output file.

Create program to calculate grades as well as descriptive statistics for a set of test scores. The test scores can be entered via a user prompt or through an external file.

Write program that reads a sequence of integers into an array and that computes the alternating sum of all elements in the array.

Write program that receives a positive integer n from the user and then calculates the sum below by using a loop. Your program needs to ask the user to re-enter a different number if the user enters a non-positive one.

Explain what is meant by a deterministic and a non-deterministic Turing Machine and the idea of such machines solving a decision problem. [7 marks] If a non-deterministic Turing Machine solves a certain problem in at most N time-steps, what information must be noted to document the exact state of the machine at each stage as it performs the calculation? [5 marks] Part of the information you have just identified will be the sequence of states q0, q1, . . . that the machine goes through. Taking account of the fact that the machine is non-deterministic show how (a) this part of the information can be represented by the values of a number of boolean variables, and (b) a formula in the style used in the problem 3-SAT can be written down to ensure that the sequence of states is one that does correspond to a valid computation of the machine.