Concordia University
Department of Computer Science and Software Engineering COMP 348: Principles of Programming Languages Winter 2021
Assignment 2
Evaluation: 100 pts
Due date and time: Before Sunday March 14, 2021 at 23:59
Note: For this assignment, you can make use of all the in-built predicate functions like oddp, evenp, atom, etc. However, you can’t use any other utility functions such as length of list. You may need to use the “member” function in Question 3, description is available at: http://clhs.lisp.se/Body/f_mem_m.htm
Question 1 (15 pts)
Write a lisp function triangle that takes an argument (n) and shows a triangle of printed numbers as
shown in the following samples. If the input is decimal or string, it should print an appropriate message.
(triangle 4) (triangle 5)
(triangle 2.5) decimal numbers are not valid input, please enter an integer
Question 2 (15 pts)
Write a Lisp program that calculates the distance between two arbitrary points P1:(x1 y1) and
P2:(x2 y2) based on the following formula.
(1, 2)= (1 − 2) + (1 − 2) Implement your program in two different ways:
1- Using anonymous function (lambda)
2- Without applying the anonymous function.
Which method is more efficient in terms of memory allocation?
Comp 348_Winter 2020 – Assignment 2
1
12 123 1234
1
12
123 1234 12345
Page 1
Question 3 (15 pts)
Write a lisp function that accepts a list as the input argument (the list is mixed up integers, decimals, characters and nested lists) and creates a list including all the characters in the original list without any duplication. Sample program output is shown below:
1. ‘((zf)(ba53.5)6(7)(a)c) (zfbac)
2. ‘((n)2(6h7.8)(wf)(n)(c)n)->(hwfcn)
Question 4 (10 pts)
Write a Lisp function f-l-swap that swaps the first and last elements of a list.
Sample Output:
(f-l-swap‘((ad)f10wh))(hf10w(ad)) (f-l-swap‘(g6p10m))(m6p10g)
Question 5 (15 pts)
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.
Example of a binary search tree
A list can be used to represent the structure of a binary tree as follow:
‘(8 (3 (1 () ()) (6 (4 () ())( 7 () ()))) (10 (()) (14 (13) ())))
Comp 348_Winter 2021 – Assignment 2
Page 2
Question 6 (20 pts)
Write a lisp program to compute the series for the sin(x) and cos(x) depending on the value of n. The function takes 2 arguments (x and n) and based on the value of n calculates one of the following functions:
sin-cos-comp (x, n) =
You are not allowed to use any inbuilt functions except predicate functions to check value type. Your program should print an appropriate message for string and decimal values for n. Additionally, there is a limit for x when n is an odd number.
Question 7 (20 pts)
In mathematics, the Pell numbers are an infinite sequence of integers, that comprises the denominators of
the closest rational approximation to the square root of 2. The sequence of approximations begins with
So the sequence of Pell numbers begin with 1, 2, 5, 12, 29,…. . The Pell numbers are defines as follow:
=
Writ a lisp program that computes the Pell numbers for an input argument n using:
a) An iterative approach
b) A recursive approach
For example pellnumbers (6) should return a list (0 1 2 5 12 29 70) Write at least 2 test cases for each version (a and b).
()=− + − +⋯+ -10