## Three More Homework Problems

### September 22, 2015

For the first problem, adjoin each element of the list to a set to eliminate duplicates from the list. This is easy in languages that provides sets as a native data type and not much harder in languages that don’t. We’ll represent the list as a set. `Adjoin`

adds *x* to the list *xs* if it is not already present, and the loop adjoins each element in turn:

`(define (adjoin x xs)`

(if (member x xs) xs (cons x xs)))

```
```(define (problem1 xs)

(let loop ((xs xs) (zs (list)))

(if (null? xs) zs

(loop (cdr xs) (adjoin (car xs) zs)))))

`> (problem1 '(3 2 4 2 7 3 5 1 3))`

(1 5 7 4 2 3)

The second problem is easy because the two lists are sorted; all we have to do is iterate through the list, advancing whichever list has the lesser head, and outputting any integers common to both:

`(define (problem2 xs ys)`

(let loop ((xs xs) (ys ys) (zs (list)))

(cond ((or (null? xs) (null? ys))

(reverse zs))

((< (car xs) (car ys))

(loop (cdr xs) ys zs))

((< (car ys) (car xs))

(loop xs (cdr ys) zs))

(else (loop (cdr xs) (cdr ys)

(cons (car xs) zs))))))

```
```

`> (problem2 '(2 3 5 5 6 7 8 9) '(1 2 4 5 5 7))`

(2 5 5 7)

The third problem uses Newton’s method to compute the largest integer with cube not exceeding the input, then cubes it to see if it equals the input. We have an `iroot`

function from a previous exercise, which we repeat below:

`(define (iroot k n)`

(let ((k-1 (- k 1)))

(let loop ((u n) (s (+ n 1)))

(if (<= s u) s

(loop (quotient (+ (* k-1 u) (quotient n (expt u k-1))) k) u)))))

```
```(define (problem3 n)

(let ((n3 (iroot 3 n)))

(= (* n3 n3 n3) n)))

`> (problem3 125)`

#t

> (problem3 121)

#f

You can run the program at http://ideone.com/wG5Dt5.

Ex1 :

Ex2:

Ex3 :

;; 1) Given a list of integers, return a list in which all the duplicates

;; have been removed. For instance, given the input list [3, 2, 4, 2,

;; 7, 3, 5, 1, 3] return the output list [3, 2, 4, 7, 5, 1].

This exercise is a good example of what is wrong with specifications,

when you have one. The specification is to return a list with the

duplicates removed, but it doesn’t specify in what order the remaining

elements shall be placed in the resulting list, and which duplicates

shall be removed (the first occurence? the last? any?). Such a weak

specification can be a good thing, because it allows the programmer to

implement usually very simple and efficient programs. For example, we

could just write in Common Lisp:

(defun remove-duplicate-integers/badass1 (list-of-integers)

(remove-duplicates list-of-integers ))

Unfortunately, the example given along with the specification, are

often to be understood as part of the specification, and as such, over

specify greatly. In this case, the example implies an order of the

elements in the result list (same as the original list), and the

duplicates that must be deleted (the last ones). Are those

constraints really needed? And in TDD, those “examples” will often be

used in tests, thus, hardwiring possibly an overspecification.

Happily, Common Lisp expected those requirements, and there’s an

option to the REMOVE-DUPLICATES function to process the duplicates

from the end and therefore returning what the example expects:

(defun remove-duplicate-integers/badass (list-of-integers)

(remove-duplicates list-of-integers :from-end t))

Of course, as a student exercise, such a solution might be rejected

(again, the problem statement lacks in formality, and probably relies

on a lot of assumptions). So as indicated, you might want to write a

simple recursive solution such as:

(defun remove-duplicate-integers/On^2/out-of-specs (list-of-integers)

(cond ((null list-of-integers)

‘())

((member (first list-of-integers) (rest list-of-integers))

(remove-duplicate-integers/On^2 (rest list-of-integers)))

(t (cons (first list-of-integers)

(remove-duplicate-integers/On^2 (rest list-of-integers))))))

Unfortunately this simple solution fails on three counts:

– it keeps the last duplicate instead of the first one,

– using member on the rest of the list, it is O(n²) in time;

– using a non-tail recursive call, it uses O(n) stack space.

To transform the recursivity into a tail recursion, we can instead use

an accumulator, an additionnal parameter that will collect the

result. When using an accumulator to process a list, we obtain the

resulting list in the reverse order, and since the specification seems

to be unfortunately that the result must be in the same order as the

original list, we have to reverse the result. Happily, this is only

O(n), so it won’t be catastrophic. On the other hand, we still use

member on the accumulated unique values, so this is still O(n²) in

time, even if the constants are less than previously, since we search

only the list of unique elements.

(defun remove-duplicate-integers/On^2 (list-of-integers)

(labels ((remdup (uniques list)

(cond ((null list)

(nreverse uniques))

((member (first list) uniques)

(remdup uniques (rest list)))

(t

(remdup (cons (first list) uniques) (rest list))))))

(remdup ‘() list-of-integers)))

Finally, here is a solution that is O(n), uses O(1) stack space, and

O(n) temporary space, and returns the exact results specified by the

example: we use a hash-table to remember the unique elements.

(defun remove-duplicate-integers/On (list-of-integers)

(let ((uniques (make-hash-table)))

(dolist (element list-of-integers)

(setf (gethash element uniques) 1))

(mapcan (lambda (element)

(unless (minusp (decf (gethash element uniques)))

(list element)))

list-of-integers)))

(mapc (lambda (rem) (assert (equal (funcall rem ‘(3 2 4 2 7 3 5 1 3))

‘(3 2 4 7 5 1))))

‘(remove-duplicate-integers/badass

remove-duplicate-integers/On^2

remove-duplicate-integers/On))

A O(n) remove duplicates that wouldn’t have to keep the order of the

original list or select a precise duplicate to keep would be:

(defun remove-duplicate-integers/On/relaxed (list-of-integers)

(let ((uniques (make-hash-table)))

(dolist (element list-of-integers)

(setf (gethash element uniques) 1))

(let ((results ‘()))

(maphash (lambda (element present)

(declare (ignore present))

(push element results))

uniques)

results)))

(remove-duplicate-integers/On/relaxed ‘(3 2 4 2 7 3 5 1 3))

;; –> (7 2 1 3 5 4)

;; 2) Given two lists of integers, each sorted in ascending order, return

;; a list of the integers common to the two lists; the output list

;; must also be in ascending order. For instance, give the input lists

;; [2, 3, 5, 5, 6, 7, 8, 9] and [1, 2, 4, 5, 5, 7] return the output

;; list [2, 5, 5, 7].

(defun common-integers (lista listb)

(loop

:for a := (first lista)

:for b := (first listb)

:while (and lista listb)

:when (< a b)

:do (pop lista)

:when (> a b)

:do (pop listb)

:when (= a b)

:collect (progn (pop lista) (pop listb))))

(common-integers ‘(2 3 5 5 6 7 8 9) ‘(1 2 4 5 5 7))

;; –> (2 5 5 7)

;; 3) Given a positive integer, determine if it is a perfect cube. For

;; instance, the integer 125 is a perfect cube, 5*5*5, but the integer

;; 121 is not.

(defun perfect-cube-p (n)

(assert (plusp n))

(= n (expt (truncate (expt n 1/3)) 3)))

(perfect-cube-p 125) ; –> t

(perfect-cube-p 121) ; –> nil

In Python.

Scala:

In Python.

My Python 3.4 solutions. (Your teacher would probably be suspicious if you turned these in for an intro level class.)

The OrderedDict and OrderedCounter classes remember the order the keys are first encountered.

The ‘&’ on the OrderedCounter class returns an OrderedCounter in which the count for each key is the minimum of the two operands.

iscube() first finds ‘lo’, a power of 2 that is less than or equal to the cube root of n. Bisect_left(), from the standard library, then performs a binary search of Cube() to find where abs(n) would go between list indices lo and 2*lo. The Cube class provides a __getitem__() method, so an instance looks like a list (i.e., duck-typing) in which each element in the list is the cube of its index. It works for n up to about 5e55; above that, bisect_left fails, complaining that n won’t fit in the data-type (ssize_t) used for a list index.

EX1.

#include

int main()

{

int n,arr[20],i,j,l=0;

printf(“Enter the Number of elements\n”);

scanf(“%d\n”,&n);

for(i=0;i<n;i++)

scanf("%d",&arr[i]);

for(i=0;i<n;i++)

{

for(j=0;j<i;j++)

if(arr[i]==arr[j])

break;

if(j==i)

arr[l++] = arr[i];

}

printf("new numbers\n");

for(i=0;i<l;i++)

printf("%d\n",arr[i]);

}

EX2.

#include

int main()

{

int i,j,n,num1,num2,arr1[10],arr2[10],l1=0,l2=0,arr3[10],l3=0;

printf(“Enter num1 and num2\n”);

scanf(“%d%d”,&num1,&num2);

printf(“Array 1\n”);

for(i=0;i<num1;i++)

scanf("%d",&arr1[i]);

printf("Array 2\n");

for(i=0;i<num2;i++)

scanf("%d",&arr2[i]);

for(i=0;i<num1;i++)

{

for(j=0;j<i;j++)

if(arr1[i]==arr1[j])

break;

if(j==i)

arr1[l1++] = arr1[i];

}

for(i=0;i<num2;i++)

{

for(j=0;j<i;j++)

if(arr2[i]==arr2[j])

break;

if(j==i)

arr2[l2++] = arr2[i];

}

for(i=0;i<l1;i++)

{

for(j=0;j<l2;j++)

if(arr1[i]==arr2[j])

arr3[l3++]=arr1[i];

}

printf("Result\n");

for(i=0;i<l3;i++)

printf("%d\n",arr3[i]);

}

1,1 Top

#include

int main()

{

int num,i=1,j=0;

printf(“Enter the number\n”);

scanf(“%d”,&num);

while(j<num)

{

j=i*i*i;

i++;

}

if(j==num)

printf("%d is perfect Cube\n",num);

else

printf("%d Not a perfect Cube\n",num);

}

O/P:

Enter the number

123

123 Not a perfect Cube

mayur@Embedded:~/Desktop/C/Logic$ ./a.out

Enter the number

1000

1000 is perfect Cube