; Assignment 01
; This assignment is on Scheme language. You can use jdoodle to run the Scheme code.
; https://www.jdoodle.com/execute-scheme-online/
Copyright By PowCoder代写 加微信 powcoder
; WARNING:
; Since we want a “pure” functional program, you should not any imperative features such as “set”, “while”, “print”, and “begin”. You may, however, use “let”.
; If you use any helper functions, you have three options:
; 1. Define them globally but with a name not conflicting with other questions.
; 2. Define them locally using (define …).
; 3. Use lambda.
; The sample test cases may not be complete, but they provide a simple way to check for correctness. You should try adding your own test cases. We will check with other test cases.
; Make sure your code runs, you do not have to worry about time-complexity unless specified otherwise.
; The mark of each question is specified and the total is 10 marks.
; Question 1
; This is a general numerical problem to get you started.
; a) Write a recursive function to check if a number is a prime number or not.
; A number is prime if and only if it is divisible only 1 and also itself.
; Note that the number 1 is not a prime (since itself is already 1, so the “also” is not satisfied).
; You may assume that the input will always be a positive integer.
; [1 mark]
(define (is-prime? num)
() ; replace this with your code
; Sample Test Cases:
; (display (is-prime? 1))
; (display (is-prime? 2))
; (display (is-prime? 3))
; (display (is-prime? 8))
; (display (is-prime? 9))
; b) This prime checking is inefficient because we do not need to check if the number n is NOT divisible by 2, 3, …, n-1.
; Instead, we can stop once we check sqrt(n) because if there is a counterexample, a * b = n, then assuming that a < b, the largest possible value of a is when a = b in which we get a * a = n.
; Solving for a, we get a = sqrt(n).
; Write a recursive function to check if a number is prime efficiently using this concept. If your answer in part (a) is already efficient, you can submit the same code.
; HINT: Should you stop at sqrt(n), sqrt(n)-1 or sqrt(n)+1.
; HINT: How do you compute sqrt(n)? How do you ensure the result is integer? Can you not use sqrt?
; HINT for the hint: a * a = n
; [2 marks]
(define (efficient-is-prime? num)
() ; replace this with your code
; Sample Test Cases:
; (display (is-prime? 1))
; (display (is-prime? 2))
; (display (is-prime? 3))
; (display (is-prime? 8))
; (display (is-prime? 9))
; Question 2
; This question is about list, recursively defined as follows:
; +------------------------------------------+
; | +-----+ +------------------------------+ |
; | | car | | cdr (the rest of the list) | |
; | +-----+ +------------------------------+ |
; +------------------------------------------+
; You can use the following functions for simplicity, but nor marks will be penalised for not using them:
(define (emp-list) ()) ; make an empty list
(define (get-val lst) (car lst)) ; get the element of the list (assuming non-empty)
(define (get-rest lst) (cdr lst)) ; get the rest of the list
(define (add elem lst) (cons elem lst)) ; add to the front of the list
; a) Write a recursive function that would return the last element of a list. You are guaranteed that the list will not be empty.
; [1 mark]
(define (get-last lst)
() ; replace this with your code
; Sample Test Cases:
; (display (get-last `(1 2 3 4 5)))
; (display (get-last `(1)))
; b) Write a recursive function to zip two lists of equal length. A zip is converts a pair of lists into a list of pairs.
; The first element of lst1 is paired with the first element of lst2, and so on...
; You are guaranteed that the two lists will be of equal length, but they both may be empty.
; [1 mark]
(define (zip lst1 lst2)
() ; replace this with your code
; Sample Test Cases:
; (display (zip `(1 3 5) `(2 4 6)))
; > ((1 . 2) (3 . 4) (5 . 6))
; NOTE: The notation (x . y) is formed by (cons x y)
; c) Write a recursive function merge two sorted lists into a single sorted list. The two lists may be of unequal length.
; The sorted list in the input and the output are sorted in ascending order. You may assume that the numbers are unique.
; NOTE: This is the standard merging for merge sort.
; [2 marks]
(define (merge lst1 lst2)
() ; replace this with your code
; Sample Test Cases:
; (display (merge `(1 3 5) `(2 4 6)))
; > (1 2 3 4 5 6)
; (display (merge `(1 2 3 4 5) `(0)))
; > (0 1 2 3 4 5)
; (display (merge `() `(1 2 3 4 5 6)))
; > (1 2 3 4 5 6)
; d) To make a merge sort, we typically split a single list into two and sort the two lists separately. The difficulty with scheme list is that we cannot just find the middle element and then slice the lists. As such, we will need a different way of splitting a list.
; This different way is similar to unzip. But instead of starting from a list of pair into a pair of list, we start from a list and then return a pair of list such that:
; – The first, third, fifth, … elements are put into the first of the first pair of list.
; – The second, fourth, sixth, … elements are put into the first of the second pair of list.
; HINT: Be careful with odd size list.
; [2 marks]
(define (split lst)
() ; replace this with your code
; Sample Test Cases:
; (display (split `(3 6 1 2 5 4)))
; > ((3 1 5) 6 2 4)
; NOTE: If the result is res, then (car res) is (3 1 5) and (cdr res) is (6 2 4)
; (display (split `(3 6 1 2 5 4 7 0)))
; > ((3 1 5 7) 6 2 4 0)
; NOTE: If the result is res, then (car res) is (3 1 5 7) and (cdr res) is (6 2 4 0).
; e) Combine the split and merge into a single function merge-sort to sort a list.
; [1 marks]
(define (merge-sort lst)
() ; replace this with your code
; Sample Test Cases:
; (display (merge-sort `(3 6 1 2 5 4 7 0)))
; > (0 1 2 3 4 5 6 7)
; (display (merge-sort `(3 6 1 2 5 4)))
; > (1 2 3 4 5 6)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com