Developments in Technology Light is incident from air on the end face of a multimode optical fibre at angle of incidence as shown below.

Developments in Technology Light is incident from air on the end face of a multimode optical fibre at angle of incidence α as shown below. n n 1 2 α The refractive indices of the core and cladding are n1 and n2 respectively, where | n1 − n2 | 1. Prove the following condition for the incident light to be guided by the fibre sin α 6 q n 2 1 − n 2 2 [4 marks] What is the main 

cause of pulse spreading in a step index multimode fibre? [3 marks] Show, for the same fibre parameters as given above, that the bandwidth × length product for the fibre is given approximately by B.L = nc (n 2 1 − n 2 2 ) where c is the speed of light in free space, and the approximation n1 ≈ n2 ≈ n has been made. [5 marks] Explain carefully how, by appropriate design of the multimode fibre, the bandwidth might be increased. [3 marks] Explain carefully what is meant by the term material dispersion in an optical fibre, explaining its relative importance for single and multimode fibres. How might it be minimised? [5 marks] 3 [TURN OVER CST.95.9.4 6 Security The Tatebayashi-Matsuzaki-Newmann protocol may be described as follows: A → S : rA 3 (mod N) B → S : rB 3 (mod N) S → A : rA ⊕ rB Explain what is happening here, including the goal and the assumptions. [4 marks] How can this protocol be attacked? [10 marks] It has been suggested that the protocol can be strengthened by changing the contents of the last message to {rB}rA (rB encrypted by rA using a secret key algorithm). Does this help? Explain your answer. [6 marks] 7 Optimising Compilers Carefully define, illustrating your method using the following definitions: f(x,y,z) = h(g(x,y), g(y,z)) g(a,b) = if h(a,b)=0 then a else f(a-1,b,a) h(p,q) = if p=0 then f(q,p-1,p) else if q=0 then 1 else 0 [10 marks] Discuss how strictness information can be used in the optimisation of pure functional languages on (a) simple single processor machines (b) parallel processing hardware

Sketch a generic implementation of the Table module giving a concrete revelation of T and providing appropriate default methods. It is not necessary to protect the data structure against concurrent access. [8 marks] What constraints do your interface and implementation impose on interfaces supplied for Key and Value when instantiating Table? [2 marks] Show how Table could be instantiated to provide an array of integers indexed by text strings, and indicate how this might be used to manage a (write-once) telephone directory. [4 marks] 1 [TURN OVER CST.94.4.2 2 Programming Language Compilation Carefully describe how to construct the precedence matrix for a given grammar, illustrating your answer by investigating whether the following is a precedence grammar. S -> a P Q b | c Q P d P -> X Q -> Y X -> p | X x Y Y -> q | y Y z [10 marks] Explain why replacing the productions S -> a P Q b | c Q P d by S -> a X Y b | c Y X d would introduce conflicts in the precedence matrix. [2 marks] Give a detailed description of a parsing algorithm that uses a precedence matrix. [8 marks] 3 Formal Languages and Automata Explain what is meant by a context-free language. [5 marks] Show that the union of two context-free languages (over the same alphabet Σ) is again context-free. [5 marks] Consider the language L over the alphabet {a, b, c} consisting of all strings of the form a ` b mc n, where `, m, n > 0 and either ` = m or m = n. Is L context-free? Is it a regular language? Justify your answers, stating carefully any well-known results that you use. [10 marks] 2 CST.94.4.3 4 Operating System Functions Describe the use of a table of pointers and a table of extents to store the list of disc blocks which compose a file. Pay particular attention to how such data structures can be designed to enable the efficient support of very large files, and give estimates of their performance for finding the location of a block chosen at random. [14 marks] Describe how such data structures would be used in the implementation of a log-structured file system with consideration of the impact of garbage collection. [6 marks] 5 UNIX Case Study For the UNIX operating system, define (a) process [2 marks] (b) the execution environment of a process [3 marks] (c) the fork system call [3 marks] Explain how a command line of the form given below is implemented: command & [9 marks] Outline the essential difference in the implementation of command lines of the form given below: command1 & command2 command1 | command2 [3 marks] 6 Data Structures and Algorithms Explain how it is possible to construct red/black search trees, using one extra bit per node, so that the trees remain reasonably balanced. [13 marks] How out of balance can your tree get and what are the worst case costs for adding a new item and finding an existing one? [7 marks] 3 [TURN OVER CST.94.4.4 7 Data Structures and Algorithms Suppose that you have been provided with a procedure that can, given n items, find the one that would come at position n/3 if the items were sorted into ascending order. Further suppose that when this procedure is called it always costs exactly 10n comparisons. Explain how this would allow you to implement a variant on Quicksort exhibiting guaranteed good computing time. [7 marks] Estimate very roughly (but justify your estimate) how much data would be needed before you could be certain that the worst case for a simple implementation of Quicksort would involve more comparisons than the worst case of your new algorithm. [10 marks] Would you ever expect anybody to want to use your new method in practical applications? [3 marks] 8 Graphics Describe the method of Douglas & P¨ucker for approximating one line chain by another to within some tolerance. Are there any special cases? [20 marks] 4 CST.94.4.5 9 Numerical Analysis I With reference to a decimal floating-point implementation with 4-digit precision (β = 10, p = 4), describe the two most common methods of rounding. (Use 1.2345 and 1.2375 as examples.) Which method is unbiased? [3 marks] What do you understand by the terms machine epsilon, and guard digit? [4 marks] Suppose the largest representable floating-point number is about 1050, and consider evaluation of p x 2 − y 2. How would you compute the result? (Use x ' 5.1040 , y ' 3.1040 as an example.) How could your method also improve accuracy on some machines? [3 marks] A programmer writes (x+y)+z but a compiler evaluates the right-hand side in the form x + (y + z). Explain how this could be harmful in floating-point arithmetic (a) when x, y and z are large, and (b) when x, y and z are numbers of moderate size. Which of these two problems would be more likely to occur in practice: (a) or (b)? [3 marks] Explain the term N aN as used in IEEE arithmetic. Roughly, how many N aN values are there in IEEE single precision? Consider an operation to be any one of + − ∗ /. Give examples of (a) an operation that yields a N aN value when neither of its arguments is a N aN, (b) an operation with finite arguments that yields +∞, (c) an operation with an argument +∞ that yields a finite result. [5 marks] What two rules govern operations where at least one argument is a N aN value? [2 marks] 10 Structured Hardware Design For each of the following entities which are held in the design database of a digital CAD/CAE system, describe their function and the attribute values or data structures that the system must maintain for each instance. Include both the simulation phase and the mask or PCB generation phase of the design process. (a) a signal net, including provision for back annotation of layout delays [10 marks] (b) a stable master clock oscillator [3 marks] (c) a tri-state buffer, with output load dependent delay [4 marks] (d) an artificial stimulus source, used to model an existing external interface componentSuppose we wish to implement this diagram in a relational database using three tables, S(sid, A), T(tid, C), and R(· · ·). Describe the schema you would use for R depending on the cardinality of the relationship. (i) When R is a many-to-many relationship between S and T. [2 marks] (ii) When R is a one-to-many relationship between S and T. [2 marks] (iii) When R is a many-to-one relationship between S and T. [2 marks] (iv) When R is a one-to-one relationship between S and T. [2 marks] (b) Suppose R is a many-to-one relationship. Rather than implementing a new table for R, can we modify one of the tables representing S or T to implement this relationship? Discuss the advantages and disadvantages of such a representation. [4 marks] (c) Suppose that we add the following diagram to our ER model. U uid E Q D tid T C February 17, 2017 1 / 1 Note that this implicitly defines a relationship between S and U resulting from the composition of relationships R and Q. Discuss the difficulties that you might encounter in attempting to implement this derived relationship directly in a table W. For example, would the results of evaluating this SQL select sid, tid, B, D from R join Q on R.tid = Q.tid always be equivalent to the contents of such a W? [8 marks] 2 CST0.2017.3.3 2 Databases Consider the following three tables. S(sid, A) R(sid, tid, B) T(tid, C) sid A s1 a1 s2 a2 s3 a3 sid tid B s1 t1 b1 s1 t2 b2 s2 t1 b4 s2 t3 b5 tid C t1 c1 t2 c2 t3 c3 t4 c4 (a) Represent the information in these three tables in a single table, using NULL values where needed. [4 marks] (b) Represent the information in these three tables as three JSON objects, each associated with one of the values of the sid key. Is any information lost? [4 marks] (c) Represent the information in these three tables as four JSON objects, each associated with one of the values of the tid key. Is any information lost? [4 marks] (d) We now have three distinct ways of representing the same information (the original tables, one big table, and the collection of JSON objects from parts (b) and (c)). Carefully compare and contrast these approaches and discuss their related advantages and disadvantages. [8 marks] 3 (TURN OVER) CST0.2017.3.4 SECTION B 3 Graphics 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. [4 marks] 4 CST0.2017.3.5 4 Graphics 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? [7 marks] (c) For each of Gourand and Phong shading, explain how you would implement each shading method using vertex and fragment shaders in OpenGL. Complete the diagram shown below by listing all inputs, outputs and uniforms for each shader. Then, explain what is computed in each shader in the case of both shading methods. There is no need to write equations or code, but you may include them if it helps your explanation. Vertex Shader Fragment shader in: in/out: out: uniforms: uniforms: [8 marks] 5 (TURN OVER) CST0.2017.3.6 SECTION C 5 Interaction Design Your company has been asked to design and implement an interface called GestureDriver which is envisioned to be a remote driving interface based on visual gesturing and speech. Hand motions will be tracked based on colour vision, and the system will classify the gestures using a simple geometric model. The gestures will be mapped into six motion commands: start, right, left, forward, reverse, and stop. These commands can also be provided via speech and transmitted to the remote vehicle. The major requirements are that the system displays the current location of the vehicle to the user, monitors location change, captures the motion and vocal command of the user in real time, and moves the vehicle based on the received command. (a) One of the Principles of Good Design is to 'balance automated and human control'. Give four examples and explain how this can be achieved for the context provided above. [4 marks] (b) Describe, with an example, each of the five different interaction spaces beyond the desktop as classified by Winograd. Briefly discuss which one(s) would be more appropriate to use for creating this application, and why. [6 marks] (c) Assuming that the initial system status is OFF, draw a task model for the user using the GestureDriver interface with the goal of reversing the vehicle they are operating remotely. The task model should capture activities at multiple levels starting with at least three activities. Explain any sequential dependencies you identify. [8 marks] (d) Describe one generic problem that task analysis can help identify, and give an example of how this can be done. [2 marks] 6 CST0.2017.3.7 6 Interaction Design (a) Describe three problems that affect the data and requirements gathering process, and provide one solution for each problem. [3 marks] (b) State and briefly describe each of the six principles of Gestalt psychology that have implications for user interface design. Explain how each of the six principles of Gestalt psychology have been employed in the design of the interface given in the figure below. [12 marks] (c) A company has just completed the heuristic evaluation of a digital music player, and identified the problem areas provided in the list below. Indicate which usability principle or principles each problem violates for five of the following problems. [Note: it is possible that each problem violates more than one usability principle, and that the same principle is violated multiple times for different problems.] P1. Inconsistencies between menus and buttons. P2. Some language does not correspond with user terminology. P3. There are buttons that the user may not realize are buttons. P4. Not all buttons have tooltips. P5. There are inconsistencies with Windows operating system standards. P6. Undo commands basically unsupported. P7. Help content uses different terminology from application. P8. System does not always provide user with enough information about the task being performed. [5 marks] 7 (TURN OVER) CST0.2017.3.8 SECTION D 7 Machine Learning and Real-world Data Suppose that a very large collection of documents describing the University of Cambridge has been collected. Your task is to build a classifier which assigns sentiment to each document, using the classes: positive, negative and neutral. (a) There is no ground truth sentiment associated with the documents, but 200 have been manually classified by three human annotators. Fleiss' Kappa is 0.65 for this set. Explain what Kappa is and outline how it is calculated. You do not need to state the full formula for Kappa. [4 marks] (b) Given the limited amount of annotated data, you decide to classify the documents using a standard sentiment lexicon. Explain how you would perform an experiment to do this. [5 marks] 8 CST0.2017.3.9 (c) (i) How would you evaluate the results of the system you have described in your answer to part (b) using the annotated data? Give details of the evaluation metrics you would use. [4 marks] (ii) If the primary objective were to identify the documents with negative sentiment, how might your proposed evaluation change? [2 marks] (d) It is suggested to you that the classes automatically assigned by the sentiment lexicon approach could be used to provide training data for a Naive Bayes classifier. Could such a classifier perform better than the sentiment lexicon classifier which provided the decisions it was trained on? Explain your answer. [5 marks] 9 (TURN OVER) CST0.2017.3.10 8 Machine Learning and Real-world Data Consider the following graph of users in a social network. (a) Give definitions of the following quantities, and state their values for nodes 1, 2 and 3: (i) Degree [1 mark] (ii) Clustering Coefficient [2 marks] (iii) Betweenness Centrality [2 marks] (b) (i) Which property of nodes in a network do clustering coefficient and betweenness centrality attempt to model? Give examples from naturally occurring networks. [4 marks] (ii) In the network depicted above, do the betweenness centrality values you calculated correspond to your intuition about the function of nodes 1, 2, and 3? If not, which factors of the formula are responsible for the divergence? [3 marks] (c) Suppose the link between 3 and 4 is removed and a link between 2 and 4 is added. How does this affect the betweenness centrality of 2 and 3, and why? [3 marks] (d) Some pairs of nodes in the new network from part (c) now have more than one shortest path that connects them. Identify these paths, and explain how their existence affects the calculation of betweenness centrality. [2 marks] (e) Professor Miller claims that it is possible for a particular pair of nodes in a graph to be connected by a number of shortest paths which is exponential with respect to the number of nodes in the graph. Give an example where this is the case, or prove that it cannot be the case. [3 marks] 10 CST0.2017.3.11 9 Machine Learning and Real-world Data Hidden Markov Models (HMM) can be used to find names in text. In the following HMM created for this purpose, the two emitting states are q1 = i (for "inside a name") and q2 = o (for "outside a name"). Each word in the training data is labelled with either i or o. There are two sequences in the training data, as follows: today may bakes a nice cake o i o o o o peter bakes and mary bakes may like sue i i o i i o o i (a) Give the general formula for estimating transition probabilities from training data. Provide the full transition matrix A for this HMM based on the training data shown. [6 marks] (b) Give the general formula for calculating emission probabilities from training data, and calculate the emission probabilities P(may|o), P(may|i), P(bakes|o), P(bakes|i). [3 marks] (c) An HMM trained with the above training observations is exposed to the following test observation: may bakes Which probabilities does the HMM assign to the following two interpretations? (i) may is a name, and bakes is not [2 marks] (ii) bakes is a name, and may is not [2 marks] (d) The first training observation is now replaced with: today peter bakes a nice cake How does this change your answers to part (c)? [2 marks] (e) A comparable situation to part (d) can arise even with substantial amounts of training data. Describe why this is a problem and indicate a solution to it. [5 mar(iii) Give an example of how asymmetric expansion of query terms can usefully model users' expectations. Is asymmetric expansion of query terms more or less efficient than equivalence classing? Justify your answer. [2 marks] (iv) How would you evaluate an Information Retrieval task for which there is high tolerance for overlooked relevant information items? How might you modify the F measure for such a task? Justify your answer. [3 marks] (b) (i) Given the query "elvis music" and the following term frequencies for the three documents doc1, doc2 and doc3 : elvis presley mississippi pop music life doc1 3 4 0 6 0 0 doc2 4 0 4 0 0 3 doc3 5 3 0 4 4 0 calculate the cosine similarity between the query and each document (you can ignore the idf term) in order to rank these documents in order of relevance. Show your workings. [2 marks] (ii) The Rocchio algorithm is a classic algorithm for implementing relevance feedback. Use Rocchio to compute the new query vector for "elvis music" using doc3 for relevance feedback (i.e., doc3 has been marked as relevant). Give suitable values for Rocchio's weight parameters. As above, calculate cosine similarity (you can ignore the idf term) in order to rank the documents in order of relevance. Show your workings. [4 marks] (iii) In Rocchio's algorithm, positive feedback is typically more useful than negative feedback. Give two example cases of negative documents being fed back that can decrease the retrieval effectiveness of the Rocchio re-formulated query. Propose one way in which you can incorporate negative feedback more effectively, and explain why this helps with the two examples you provided. Motivate your answer. [5 marks] 8 CST2.2018.8.9 8 Machine Learning and Bayesian Inference Evil Robot has decided to become a gambling cheat. He has a biased coin with Pr(head) = p and two dice. The first die is biased with Pr(n) = pn for the nth outcome with n ∈ {1, 2, 3, 4, 5, 6}. The second die is also biased, and has different numbers: its distribution is Pr(n) = qn with n ∈ {4, 5, 6, 7, 8, 9}. Evil Robot flips the coin. If he gets a head then he rolls the first die, otherwise he rolls the second. He then tells you the outcome. You see only the number obtained and nothing else. He does this m times, so you observe a sequence of m numbers in the range 1 to 9. Your aim is to estimate p and the distributions of each die, given the m numbers. In the following, n is the vector of m observed numbers (n1 · · · nm) T , θ is the set of parameters {p, p1, . . . , p6, q4, . . . , q9} and we define q = 1 − p. (a) Write down an expression for the distribution Pr(n|θ) where n ∈ {1, . . . , 9}. [2 marks] (b) Define the variable zi = ( 1 if ni was obtained by rolling die 1 0 otherwise. and let z denote the corresponding vector with m values. Write down an expression for log Pr(n, z|θ). [3 marks] (c) Describe the EM algorithm for maximizing likelihood in a problem involving latent variables. [3 marks] (d) Show that, with the distribution Pr(z|n, θ), E(zi) = 1 if ni ∈ {1, 2, 3} 0 if ni ∈ {7, 8, 9} ppni ppni+qqni otherwise. [4 marks] (e) Define γi = E(zi) as in Part (d). By applying the EM algorithm to this problem, show that you can estimate the parameters in θ using the following updates p = γ m pn = 1 γ X {i|n=ni} γi qn = 1 m − γ X {i|n=ni} (1 − γi) where γ = Pm i=1 γi . [8 marks] 9 (TURN OVER) CST2.2018.8.10 9 Mobile and Sensor Systems A leisure park has decided to adopt a variety of mobile and sensing technologies to monitor the usage of its attractions. An app is offered to customers willing to install it on their smartphone, which tracks customers' location throughout the park and uses the phone accelerometer to monitor activity. (a) Describe how app developers could make sure the app delivers the best accuracy on location and activity tracking while preserving the phone battery as much as possible through system and sensor sampling optimizations. [6 marks] (b) A customer installs the app on their device. They have two other applications on the phone which monitor their physical activity as well as their location throughout the day for clinical reasons. Describe how the phone operating system could optimize the battery efficiency of the sensing across applications. [5 marks] (c) A variety of wireless sensors are scattered throughout the park to monitor the operation of the attractions by continuously gathering temporal data (e.g., mechanical vibration, load, temperature, humidity). (i) Describe a combination of medium access and network layer protocols for infrastructure-less multi-hop networks to aid the sensor data delivery to the park management servers. Discuss advantages and disadvantages of the solution devised. [5 marks] (ii) Describe a solution which uses protocols from the Internet of Things domain to offer a non multi-hop solution. Discuss the advantages and disadvantages of the solution devised. [4 marks] 10 CST2.2018.8.11 10 Principles of Communications (a) There are two main ways in which traffic sources can be controlled: open-loop and closed-loop. Describe the overall operation and use of these two kinds of network system: What are the key components of an open-loop controlled protocol? What are the key components of a closed-loop, or feedback controlled system? What kinds of applications are suited to each class of control loop? [10 marks] (b) Two important approaches to fairness are max-min, and proportional. Describe what properties each of these offer, how they differ in how they can be used, and what happens in each case when demand exceeds supply of network capacity. [10 marks] 11 (TURN OVER) CST2.2018.8.12 11 Quantum Computing (a) In the quantum teleportation protocol, Alice and Bob are each in possession of one qubit of a pair in the joint state √ 1 2 (|00i + |11i). In addition, Alice has a qubit in an arbitrary state |φi. Explain how the protocol works. In particular, show that it involves the transmission of exactly two classical bits of information from Alice to Bob and demonstrate how, at the end of the protocol, Bob is in possession of a qubit in state |φi. [10 marks] (b) Suppose now that Alice has two qubits in a state |θi = α0|00i + α1|01i + α2|10i + α3|11i. In addition, there is a pair of qubits in the state √ 1 2 (|00i + |11i) such that Alice is in possession of one qubit of the pair while Bob is in possession of the other. Alice now uses the quantum teleportation protocol to transmit to Bob the first qubit of |θi. What is the resulting joint state of the two-qubit system composed of the second of Alice's qubits and the qubit in Bob's possession? [10 marks] 12 CST2.2018.8.13 12 Security II (a) Name three different families of algebraic groups that are commonly used in cryptographic applications of the Diffie-Hellman problem, where any group element (other than the neutral element) can be used as a generator. Briefly outline some of their main attributes, such as the set of elements and the group operator. [9 marks] (b) You are preparing to participate in a password-cracking competition. During the competition, you will be given the 128-bit hash-function output MD5(p). You have to find p, an 8-character password, each character having been chosen uniformly at random from a known alphabet of 64 ASCII characters. In the weeks preparing for the competition, you have access to a small cluster of GPU graphics cards that can evaluate MD5 109 times per second. During the competition, you have only access to a laptop computer that can evaluate MD5 106 times per second. Without any pre-computation, how long would it take to evaluate MD5 for all possible passwords p in a brute-force attack (i) on the laptop? [2 marks] (ii) on the GPU cluster? [2 marks] You decide to use the GPU cluster to pre-compute a rainbow table for this challenge. (iii) What functions other than MD5 will the GPU cluster have to evaluate as often as MD5 when building the rainbow table? [3 marks] (iv) Your laptop has enough RAM for storing the rainbow table as a hash table of 232 key-value pairs (x, y) with x, y ∈ {0, 1} 128. If you execute MD5 250 times while generating your rainbow table, how long will your laptop need (worst case) to find a password p stored in it, given its MD5 hash value MD5(p)? Assume that the runtime is entirely dominated by the MD5 evaluations. [4 marks] 13 (TURN OVER) CST2.2018.8.14 13 System-on-Chip Design (a) At the lowest level, what is the primary consumer of electrical power in digital logic today? Give a formula for the expected energy or power use for a CMOS gate. [2 marks] (b) A matrix (a 2-dimensional array) is stored on-chip in static RAM. What main factors contribute to the time and energy needed to transpose it? [4 marks] (c) Assume now a square matrix is to be held in DRAM. (i) When might it be helpful to store multiple-copies of a given matrix in different DRAM banks? [1 mark] (ii) When might it be helpful to store multiple-copies of the matrix (or another example data structure) in one DRAM bank? [2 marks] (iii) One way to avoid transposing a matrix is simply to hold an annotation that it has been transposed and to then swap over the row and column arguments for each operation. Why might physically performing the transpose ultimately benefit performance? Where would the annotation be held? [2 marks] (d) A computation operates on square matrices of size 105 × 105 . The inner loop, to be accelerated in hardware, has the following basic structure: for (int i= ...) for (int j= ...) { DD[i, j] = ff(SS[i-1, j], SS[i, j-1]) } (i) Are there any loop-carried dependencies? What does this mean for performance optimisation? [1 mark] (ii) If the DRAM timings are 11-11-11, meaning row activation, column activation and writeback each take 11 clock cycles, estimate roughly the minimum time for a naive implementation of the computation. Assume a simple linear data layout. State all further assumptions. [6 marks] (iii) What determines whether it is possible or a good idea to perform the operation 'in place' (ie. using the same memory for DD and SS)? [2 marks] 14 CST2.2018.8.15 14 Types (a) Give typing rules for the introduction form pack(τ, M) and elimination form unpack M as (x, α) in N of the existential type ∃α(τ ). [4 marks] (b) An infinite stream of booleans can be represented in the polymorphic lambda calculus using the existential type stream , ∃α(α × (α → (bool × α))) (i) Using the encoding above, define a function head : stream → bool. [3 marks] (ii) Using the encoding above, define a function tail : stream → stream. [3 marks] (iii) Using the encoding above, define a function unfold : ∀α(α → (α → (bool × α)) → stream).

address all