CSI3120 - A1
Kevin Le, 300053306
Question 1
The scopes of the variables are as follows: x,y, and z are global variables. Where xs, ys, and
zs are also global as x y and z are passed into them. Temp should only be local to the
function calls as it gets initialised only in the function during the recursive calls. Res is
evidently global as well.
The function takes as three inputs, x, y, and z. The x input being the list to swap and y and z
being two empty lists.
The base case, if length of x is 0, returns a dictionary of y_list and z_list.
The function call appends to y the first element of x, and duplicates y into an initialised
variable temp. Then y gets assigned new elements, those being the list z and the same
happens to z from temp. The function then calls itself with list x from [2…n] and y and z.
Here is the recursive trace, please note that this represents each variable right before the
recursive call in terms of vectors.
Call 0:
x: 1,2,3,4
y:
z:
temp:
Call 1:
x: 2,3,4
y:
z: 1
temp: 1
Call 2:
x: 3,4
y: 1
z: 2
Call 3:
x: 4
y: 2
z: 3,1
temp: 3,1
Call 4:
x:
y: 3,1
z: 4,2
temp: 4,2
This should be the output as tested that results from the variable “res” being printed.
y_list1 y_list2 z_list1 z_list2
3 1 4 2
Question 2
The mergelist function is a recursive function that takes 3 list, notably x y and z parameters
and returns a single merged list recursively.
The runtime for my code should be O(n).
The base case of the recursive function revolves around the input type and length of arrays x
and y.
The first case being if the length of x is 0, append all of y to z and return z. The second being
the same as the first except if the length of y is 0. The last base case is if the lengths of both
y and z are 0, return z.
If the parameters are empty at the start, it should return NULL. Otherwise, it should return
whatever elements are present in x and y in z.
The recursive case is executed in an if else clause, being that it will recurse on the element
of x and y that is smaller.
The scope of all parameters are global.
Example,
x <- c(1,2)
y <- (0)
It will call mergelists(x,y[-1],z) and vice versa for x if the element of x is smaller.
Here is an example of the recursive calls:
x <- c(1,2,3)
y <- c(4,5,6)
z <- c()
Call 0:
x: 1,2,3
y: 4,5,6
z:
Call 1:
x: 2,3
y: 4,5,6
z: 1
Call 2:
x: 3
y: 4,5,6
z: 2,3
Call 3:
x:
y: 4,5,6
z: 1,2,3
Call 4:
x:
y: 4,5,6
z: 1,2,3,4,5,6
Here are the test cases for the code:
# Empty Set
es1 <- c()
es2 <- c()
es3 <- c()
print("Empty Set")
print(mergelists(es1,es2,es3))
# List of Length 1
ll1 <- c(1)
ll2 <- c()
ll3 <- c()
print("List of Length 1")
print(mergelists(ll1,ll2,ll3))
# Even Length List
ell1 <- c(1,2,3,4)
ell2 <- c(5,6,7,8)
ell3 <- c()
print("Even Length List")
print(mergelists(ell1,ell1,ell3))
# Odd Length List
oll1 <- c(1,2,3)
oll2 <- c(-1,-2)
oll3 <- c()
print("Odd Length List")
print(mergelists(oll1,oll2,oll3))
Using Sys.time(), I conducted run time tests. Here are 3 runs with correct parameters.
Run 1:
[1] "Empty Set"
NULL
[1] "List of Length 1"
[1] 1
[1] "Even Length List"
[1] 1 2 3 4 5 6 7 8
[1] "Odd Length List"
[1] -1 -2 1 2 3
Time difference of 0.01878595 secs
Run 2:
[1] "Empty Set"
NULL
[1] "List of Length 1"
[1] 1
[1] "Even Length List"
[1] 1 2 3 4 5 6 7 8
[1] "Odd Length List"
[1] -1 -2 1 2 3
Time difference of 0.02683401 secs
Run 3:
[1] "Empty Set"
NULL
[1] "List of Length 1"
[1] 1
[1] "Even Length List"
[1] 1 2 3 4 5 6 7 8
[1] "Odd Length List"
[1] -1 -2 1 2 3
Time difference of 0.01853991 secs
Here are 3 runtimes with incorrect parameters.
Run 1:
[1] "Incorrect Input Test"
[1] "a" "b" "c" "d"
Time difference of 0.002384901 secs
Run 2:
[1] "Incorrect Input Test"
[1] "a" "b" "c" "d"
Time difference of 0.002573967 sec
Run 3:
[1] "Incorrect Input Test"
[1] "a" "b" "c" "d"
Time difference of 0.002184153 secs
