Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Examination Tutorial Letter
August 19, 2008 11:14AM
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
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
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.
avatar Re: Examination Tutorial Letter
October 16, 2008 03:29PM
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
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
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
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.

Click here to login