Welcome! Log In Create A New Profile

# Examination Tutorial Letter

Posted by aronl
Announcements Last Post
: Programming Students at UNISA School of Computing 06/19/2019 02:01PM
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Examination Tutorial Letter August 19, 2008 11:14AM Registered: 14 years ago Posts: 88 Rating: 0
Dear Students

The examination tutorial letter(103) is now available for download on myUnisa and Osprey.

regards
Lazarus Aron
 Re: Examination Tutorial Letter October 16, 2008 12:01PM Registered: 12 years ago Posts: 387 Rating: 0
In question 1 - I'm guessing

a) n < n log n < 23n2 - 23 < n2 log n2 < n3 < 2n?

b1) n2: n/2 will halve the list but not exponentially decrease
b2) n3: n2 + n
b3) n: the while loop can never execute since i = j for each loop?

All ideas welcome!
 Re: Examination Tutorial Letter October 16, 2008 12:41PM Registered: 12 years ago Posts: 387 Rating: 0
Question 2b

(i) always returns 0
(ii) It works but its not recursive
(iii) I think this is right
(iv) Will return 5*5 * 2*2 etc - multiply not add
(v) doesn't pick up info? I think it would multiple the value of the links? And I'm not sure it would return anything except the last one? Not sure.
 Re: Examination Tutorial Letter October 16, 2008 03:29PM Registered: 11 years ago Posts: 423 Rating: 0
Q1a
23n+23; nlogn; 23n2-23; n2logn2; n3+2n2+3n; 2n

Q1
b)i O((logn)2)
b)ii O(n3)
b)iii O(n2)
 Re: Examination Tutorial Letter October 16, 2008 03:49PM Registered: 12 years ago Posts: 387 Rating: 0
Question 3a

After the first three numbers are sorted, pivot is the second element. In a random list, it has a good change of being more the mean. "First + 2" means that the third element is swapped with the last, since if the list is random, its likely to be closer to the end.

Before first sort
5 8 0 2 5 3 7 2 6
After first sort â€“ Pivot = 5 (first + 1)
0 5 8 2 5 3 7 2 6
0 5 2 8 5 3 7 2 6
0 5 2 3 5 8 7 2 6
0 5 2 3 2 8 7 5 6
0 2 2 3 5 8 7 5 6

Partition returns 4;
Sneaky stuff: list[index] is < pivot, so the second 5 goes to the second half
 Re: Examination Tutorial Letter October 16, 2008 03:52PM Registered: 12 years ago Posts: 387 Rating: 0
Question 5 - HELP

1) A list of customers - a queue

2) An address book - neither since you don't want them deleted. But if you had to a queue is better than a stack.

3) A word processor - a stack with a second stack remembering deletions.

4) A queue (prioty queue)

5) I would create a temporary queue, do a for loop to the kth item and add it (popping it from the queue), then copy the rest of the items in order. Then copy temp to Q.
 Re: Examination Tutorial Letter October 16, 2008 04:48PM Registered: 12 years ago Posts: 387 Rating: 0
Question 6

b) Preorder traversal: 3,1,2,4,6,5,9,7

c) To delete the root, swap the rightmost value of the left link with root and delete.
Sorry, only registered users may post in this forum.