This is an assessment exercise. You may not seek any assistance from others while expecting to receive credit.
This assignment targets two programming paradigms:
1) Functional Programming with Lisp,
2) Procedural Programming with C.
You are allowed to work on a team of 4 students at most (including yourself). Each team should designate a leader who will submit the assignment electronically. See Submission Notes for the details.
ONLY one copy of the assignment is to be submitted by the team leader. Upon submission, you must book an appointment with the marker team and demo the assignment. All members of the team must be present during the demo to receive the credit. Failure to do so may result in zero credit.
This is an assessment exercise. You may not seek any assistance from others while expecting to receive credit. You must work strictly within your team). Failure to do so will result in penalties or no credit.
Your assignment is given in two parts, as follows.
1) Functional Programming with Lisp,
2) Procedural Programming with C
For the following questions, implement the function in lisp. Some examples are provided to illustrate the behaviour of each function. Note that Your implementation must work for all form of possible inputs.
Q 1. Write a lisp function that takes a list and two indexes from and to, and returns sub- list whose elements are the elements within from and to indexes.
e.g.:
> (sub-list '(1 6 12) 2 3) (6 12) > (sub-list '(1 6 12) 4 2) NILIn case the indexes are out of bound, the function simply returns NIL.
NOTE: You may NOT use any built-in functions other than car, cdr, or list construction functions: cons, list, and append.
Q 2. Modify the above function as in the following:
1.:add default parameters for from and to: in case the from is missing, it would be 1; in case the to is missing, the length of the list may be considered as the default value. You may use the list-length built-in function for that.
2.:in case from is greater that to, the function must return the sublist in reverse order.
> (sub-list
(6 12) |
‘(1 | 6 | 12) | 2) |
> (sub-list (12 6 1) |
‘(1 |
6 |
12) |
3 1) |
> (sub-list (1) |
‘(1 |
6 |
12) |
nil 1) |
Q 3. Write a lisp function that receives a list as the input argument (the list is mixed up integers, decimals, characters and nested lists) and returns a attened list containing all the atomic elements that are numbers, without any duplication. Sample function output is shown below:
(flatten-numbers '(1 2 (3 1) (a 2.5) (2 4.5) ((1 2)))) (1 2 3 2.5 4.5)Q 4. Write a lisp program to check whether a binary tree is a Binary Search Tree. A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:
? The left sub-tree of a node has a key less than or equal to its parent node’s key.
? The right sub-tree of a node has a key greater than to its parent node’s key. The list representing the structure of a sample binary tree is given in the following:
'(8 (3 (1 () ()) (6 (4 () ())(7 () ()))) (10 () (14 (13 () ()) ())))
Q 5. Write a lisp function called split that receives a list and returns a new list whose elements are the rst and the second halves of the original list. Sample function outputs are given below:
(split '(1 2 3 4)) ((1 2) (3 4}} (split '(1 2 3 4 5)) ((1 2 3) (4 5)) (split '(1 (2 3) 4 5 6)) ((1 (2 3) 4) (5 6))
Q 6. Write a lisp function make-cbtree that receives a list, and returns a complete binary tree whose nodes are populated from the elements of the list in the same order. An example is given in the following:
(make-cbtree '(8 3 10 1)) (8 (3 (1 () ()) ()) (10 () ())) (make-cbtree '(8 3 10 1 6)) (8 (3 (1 () ()) (6 () ())) (10 () ()))
You may use auxiliary functions to processed the list, including the split function in above.
Note: In a complete binary tree every level, except possibly the last, is completely lled, and all nodes in the last level are as far left as possible. See 2.
Q 7. Write a lisp function triangle that takes an integer as the argument and prints a triangle of stars as shown in the following gure. If the input is 0, decimal or string, it should print an appropriate error message. positive integers print left-justi ed triangles, whereas for the negative numbers the printed triangles are right-justi ed.
Example:
> (triangle 2.5) invalid number; please enter a positive or a negative integer > (triangle 0) invalid number; please enter a positive or a negative integer
Q 8. In previous assignment, you wrote a Prolog query to generate the rst n numbers of the Lucas sequence. In this assignment, rewrite the code as a lisp function that generates the sequence and returns it as a list.
In this section you implement some short programs in C.
Q 9. Write a function in C that receives an array of integers and returns a pointer to its smallest element. The signature of the function as well as a short code on its usage are given in the following:
int* findmin(int* arr, int size); int arr[ ] = {1, 4, 5, 6, -1}; int * m = findmin(arr, 5); printf("%d", *m); // -1Q 10. You want to write a C library that implements the selection sort to sort an array of integers. The selection sort (5) algorithm is outlined below:
The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by nding the smallest element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.