ECM2418 Computer Science Past Paper - University of Exeter - January 2024 PDF

ECM2418 UNIVERSITY OF EXETER FACULTY OF ENVIRONMENT, SCIENCE AND ECONOMY COMPUTER SCIENCE Examination, January 2024 Computer Languages and Representations Module Leader:...

ECM2418 UNIVERSITY OF EXETER FACULTY OF ENVIRONMENT, SCIENCE AND ECONOMY COMPUTER SCIENCE Examination, January 2024 Computer Languages and Representations Module Leader: Dr David Wakeling Duration: TWO HOURS Answer all questions. Questions 1 and 2 are worth 40 marks each; question 3 is worth 20 marks. No word count specified. The marks for this module are calculated from 60% of the percentage mark for this paper plus 40% of the percentage mark for associated coursework. No electronic calculators of any sort are to be used during the course of this examination. This is a CLOSED BOOK examination.  ECM2418 Question 1 (a) Write a Haskell function part that computes the partition of a list with a predicate, so that part even [17,1,2,16,4,15,5] ====> ([2,16,4],[17,1,15,5]) Give a polymorphic type for your function. (5 marks) (b) Write the polymorphic type of the Haskell function alpha below, and explain what it computes. alpha ([],ys) = [] alpha (xs,[]) = [] alpha (x:xs, y:ys) = (x,y) : alpha (xs,ys) (5 marks) (c) Simplify this λ-expression, showing your working. (λx. λy. λz. z y x) 8 5 (λp. λq. p + q) (5 marks) (d) Write the polymorphic type of the Haskell function beta below, and explain what it computes. beta p xs = foldr ((++). sel) [] xs where sel x | p x = [x] | otherwise = [] (5 marks) (e) Write a Haskell function suitable for calculating factorials on a parallel machine, so that parfact 5 ====> 120 Give a polymorphic type for your function. How much faster do you think parallel calculations would be in practice? ECM2418 (January 2024) 1  ECM2418 (5 marks) (f) Explain what the following Haskell function computes, write its polymor- phic type, and an equivalent function that does not use a list comprehension. omega n = [ x | x [a] reverse2 xs = loop [] xs where loop a [] = a loop a (x:xs) = loop (x:a) xs (5 marks) (h) Write the polymorphic type of the Haskell function delta below, and explain what it computes. delta xs = foldr (\x -> \y -> 1 + y) 0 xs (5 marks) (Total 40 marks) ECM2418 (January 2024) 2 Please Turn Over  ECM2418 Question 2 (a) Write a Prolog predicate isort, along with any auxiliary predicates that you need, to sort a list of integers using an insertion sort, so that isort( [5,2,7,1,8], WS ). WS = [1,2,5,7,8] (5 marks) (b) The strength of an acidic or alkaline solution is measured using the pH scale as follows: a solution with a pH of 0-3 is strongly acidic; a solution with a pH of 4-6 is weakly acidic; a solution with a pH of 7 is neutral; a solution with a pH of 8-10 is weakly alkaline; a solution with a pH of 11-14 is strongly alkaline. Show how this information can be implemented as a Prolog predicate. (5 marks) (c) With the aid of an example, explain what the predicate gamma below computes. gamma( [], 0 ). gamma( [_|XS], N ) :- gamma( XS, M ), N is 1 + M. (5 marks) (d) Write a Prolog predicate prefix that is true if one list is a prefix of another, so that prefix( [1,2,3,4], [1,2,3,4,5,6,7,8] ). true Now write a Prolog predicate that is true if one list is a suffix of another, so that suffix( [5,6,7,8], [1,2,3,4,5,6,7,8] ). true (5 marks) ECM2418 (January 2024) 3  ECM2418 (e) Why might one discourage the use of the Prolog assert and retract predicates? (5 marks) (f) Unlike Haskell programs, Prolog programs are not strongly typed. What does this mean, and why might it cause problems? (5 marks) (g) A student has written the following Prolog predicate that is supposed to be true for ascending lists of integers, so that ascending( [1,3,5,6,8,10 ] ). true What needs to be done to make it operate correctly? ascending( [X,Y|XYS] ) :- X =< Y, ascending( XYS ). ascending( [X,Y|XYS] ) :- X > Y, ascending( XYS ). (5 marks) (h) After the collapse of an e-commerce company, an investigation by the auditors blames the following Prolog predicates. Explain what has gone wrong, and how it could have been put right. airfreight( X ) :- valuable( X ). valuable( ’Microsoft XBox’ ). valuable( ’Sony Playstation’ ). (5 marks) (Total 40 marks) ECM2418 (January 2024) 4 Please Turn Over  ECM2418 Question 3 (a) Show the transition table for the following Deterministic Finite State Automaton (DFA) over the the alphabet { ‘0’, ‘1’ }. 0 q2 1 0,1 0 1 q1 q3 For states [2 marks]; for transitions [3 marks]. (5 marks) (b) Show a Deterministic Finite State Automaton over the alphabet { ‘0’, ‘1’ } that accepts strings starting with the regular expression 0(10)*0 ∪ 1(01)*1 (5 marks) (c) Write a regular expression describing the strings accepted by the following Deterministic Finite State Automation (DFA) over alphabet { ‘0’, ‘1’ }. 1 q2 1 0 q1 q4 0 1 q3 0 (5 marks) ECM2418 (January 2024) 5  ECM2418 (d) Show a simplification of the following Deterministic Finite Automaton (DFA) over the alphabet { ‘0’, ‘1’ } that uses three nodes instead of five. q1 1 q3 1 0 0 0 0 q5 1 q2 q4 1 (5 marks) (Total 20 marks) ECM2418 (January 2024) 6 End of Paper