CS3342 – Assignment 3 due Mar. 27, 2024 2-day no-penalty extension until: Mar. 29, 11:59pm !!! Submit all your responses for Q1 – Q3 as a single pdf file to Assignment 3 Q1-Q3 and your Q4 Scheme code as alcs.rktfile to Assignment 3 Q4 (Scheme code). 1. (10pt) Using the numbers defined on slide 23, chap 11.1, and exponentiation operator defined on slide 25, prove that 2 3 = 8 using: (a) applicative order, (b) normal order. You can use online lambda calculators but do not post screen shots. 2. (20pt) Give an example of aλ-expression such that anα-conversion is needed during the applicative order reduction, but noα-conversion is necessary during the normal-order reduction. Show both reductions. 3. (20pt) Prove that the grammar forλ-expressions with minimum parentheses on the bottom of slide 5, chap.11.1, is unambiguous. 4. (50pt) Write a Scheme program,lcs.rkt, that computesalongest common subsequence of two lists: > (lcs ’() ’(a b)) ’() > (lcs ’(b a) ’(a b)) ’(b) > (lcs ’(a b c b d a b) ’(b d c a b a)) ’(b d a b) You are required to provide a pure functional implementation from scratch, that does not employ advanced functions or imperative features. Therefore, besides basic arithmetic operations and number comparisons, you are allowed to useonlythe following basic Scheme functional constructs: – function creation:lambda – binding:define,let,let*,letrec – booleans:not,and,or – conditionals:if,cond – list operations:car,cdr,cons,list,append,null?,member – comparison:eq?,eqv?,equal? – mapping:map,apply Notes: Online tools:You are allowed to use online tools such as JFLAP, LLMs (ChatGPT et al.), online lambda calculators, etc., to help you solve the assignment. You still need to explain clearly your solution. Also, make sure you understand what the tools do. No tool will be available during exams! L A T E X:For those interested, the best program for scientific writing is L A T E X. It is far superior to all the other programs, it is free, and you can start using it in minutes; here is an introduction: https://tobi.oetiker.ch/lshort/lshort.pdf. It is also available online at https://www.overleaf.com/. 1