the former is expensive for arrays and the latter interacts badly with side effects. [2 marks] (iii)
Question:
the former is expensive for arrays and the latter interacts badly with side effects". [2 marks] (iii) What parameter-passing mechanism(s) do C and Java use, and how do such languages deal with an array being passed as a parameter? [2 marks] (b) A side-effect-free call-by-value language has its ML-like syntax of expressions e extended to be able to model representation of e as a value for later evaluation by force and eval respectively. Sketch two programs (differing only in whether they use suspend and force or quote and eval) which give different results. [Note: Answers using side-effecting operators can only gain partial marks.] [4 marks] (c) A
library defines a generic class Foo in a Java-like language. A user's program declares a class C and subclasses it as class D, creating variables fc and fd of types Foo and Foo respectively. (i) Construct a declaration of Foo along with a program of the above form containing the assignment fc=fd which, if this statement were legal, would be the cause of a later run-time error when executed. [5 marks] (ii) How might the language syntax be changed to optionally express that the above assignment is to be allowed, indicating any compensating restrictions required for the declaration of Foo or fc to avoid run-time errors. [3 marks] (iii) How do Java arrays of type T[] fit in with your answer to Part (c)(i)? [2 marks] 2 CST1.2019.7.3 2 Economics, Law and Ethics (a) Describe five different types of auctions. [5 marks] (b) If you were in the business of selling advertisements, what would be an efficient way to price them? [5 marks] (c) How might one political candidate achieve a better price per advertisement than their opponents? [5 marks] (d) What are bidding rings and what might game theory tell us about them? [5 marks] 3 (TURN OVER) CST1+CST2.2019.7.4 3 Economics, Law and Ethics (a) What do sections 1, 2 and 3 of the
Computer Misuse Act 1990 prohibit? [6 marks] (b) Eve is operating a DDoS-for-hire service and has recruited 100,000 CCTV cameras into a botnet. If Mallory pays Eve $2 to take down a gaming teamspeak server for five minutes, what offences, if any, are being committed by Eve and Mallory? [8 marks] (c) How might the Wimbledon case (R v. Lennon 2005 ) apply to this case? [6 marks] 4 CST1+CST2.2019.7.5 4 Formal Models of Language This question relates to an information source that produces symbols from an alphabet. (a) X is an information source, which produces symbols from the set {a, b, c, d, S} (i) If we assume X produces symbols with equal probability, what is the entropy of X? [1 mark] (ii) In fact, X produces symbols with non-equal probabilities. What do you know about the entropy of X compared to your previous answer? [1 mark] (iii) X produces symbols with probability distribution: p(a) = 0.4, p(b) = 0.2, p(c) = 0.2, p(d) = 0.1, p(S) = 0.1 Give an
expression for the entropy of information source X. [2 marks] (b) The symbol sequence produced by X represents consecutive words of a language, where S indicates whitespace. (i) Describe and provide an equation for the entropy of the language produced by the symbol sequence. [2 marks] (ii) A student observes that when a word in the language contains c it is always followed by b. Explain how this redundancy helps communication over a channel that tends to swap b with d. [2 marks] (c) Define a noisy channel and describe how it could be interpreted with respect to human language communication. [6 marks] (d) Computational Linguists have hypothesised that natural languages have evolved to be both efficient and robust to noise. Do you agree? Justify your answer by referring to information theory and giving appropriate examples. [6 marks] 5 (TURN OVER) CST1+CST2.2019.7.6 5 Formal Models of Language This question concerns lexical grammars. (a) Tree Adjoining Grammars contain two types of
elementary tree. (i) What are these trees called? [1 mark] (ii) If one were building a grammar for English which aspects of language do the two tree types model? [2 marks] (b) Provide a Tree Adjoining Grammar that can parse the string: students enjoy easy exams [5 marks] (c) Show how a parse for this string is constructed. Explain the operations. [5 marks] (d) Provide a Categorial Grammar that can parse the same sentence. [4 marks] (e) When children learn their first language they usually acquire nouns before verbs before modifiers. They also usually produce single word strings before moving on to longer strings. With reference to Tree Adjoining Grammars and/or Categorial Grammars propose some hypotheses for this. Justify your proposals. [3 marks]
1 Foundations of Computer Science Three alternative representations for non-negative integers, n, are: • Peano: values have the form S(... S(Z) ...), applying S n times to Z where S and Z are
constructors or constants of some data type. • Binary: values are of type bool list with 0 being represented as the empty list, and the least-significant bit being stored in the head of the list. • Church: values have the form fn f => fn x => f(... f(x) ...), applying f n times to x (a) Write ML functions for each of these data types which take the representation of an integer n as argument and return n as an ML int. [6 marks] (b) Write ML functions for each of these data types which take representations of integers m and n and return the representation of m + n. Your answers must not use any
value or operation on type int or real. [Hint: you might it useful to write a function majority: bool*bool*bool -> bool (which returns true when two or more of its arguments are true) and to note that the ML inequality operator '' acts as exclusive-or on bool.] [10 marks] (c) Letting two and three respectively be the Church representations of integers 2 and 3, indicate whether each of the following ML expressions give a Church representation of some integer and, if so what integer is represented, and if not giving a one-line reason. (i) two three (ii) three two (iii) two ? three (iv) three ? two [4 marks] 2 CST0.2019.1.3 2 Foundations of Computer Science (a) We are interested in performing operations on nested lists of integers in ML. A nested list is a list that can contain further nested lists, or integers. For example: [[3, 4], 5, [6, [7], 8], []] We will use the datatype: datatype nested_list = Atom of int | Nest of nested_list list; Write the code that creates a value of the type nested list above. [1 mark] (b) Write the function flatten that flattens a nested list to return a list of integers. [3 marks] (c) Write the function nested map f n that applies a function f to every Atom in n. [4 marks] (d) What is the type of f in Part (c)? [1 mark] (e)
function pack as xs n that takes a list of integers and a nested list; the function should return a new nested list with the same structure as n, with integers that correspond to the integers in list xs. Note: It is acceptable for the function to fail when the number of elements differ. Example: > pack_as [1, 2, 3] (Nest [Atom 9, Nest [Atom 8, Atom 7]]); val it = Nest [Atom 1, Nest [Atom 2, Atom 3]]: nested_list [6 marks] (f ) What does the data type nested zlist correspond to? [2 marks] datatype nested_zlist = ZAtom of int | ZNest of (unit -> nested_zlist list); (g) Write the function that converts a nested zlist to a nested list. [3 marks] 3 (TURN OVER) CST0.2019.1.4 SECTION B 3 Object-Oriented Programming (a) You are given the following implementation for an element of a list: class Element { int item; Element next; Element(int item, Element next) { super(); this.item = item; this.next = next; } @Override public String toString() { return item + " " + (next == null ? "" : next); } } (i) What does the statement super() mean? [1 mark] (ii) What is the meaning of this in the line this.item = item? [1 mark] (iii) What is the purpose of the annotation @Override? [2 marks] (iv) Rewrite the class to be immutable. You may assume that there are no sub-classes of Element. [2 marks] (b) Use the immutable Element class to provide an
Expert Answer:
