# PastExamPapersOct2006

Posted by united
Announcements Last Post
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
 PastExamPapersOct2006 October 01, 2007 03:10PM Registered: 14 years ago Posts: 131 Rating: 0
Hi! anyone tried the oct 2006 paper. How do you find it. I need help on question 3-the sentinel search. I don't understand how it works. Any tips on how to implement it.

Thanks.
 Re: PastExamPapersOct2006 October 02, 2007 07:35PM Registered: 12 years ago Posts: 13 Rating: 0
Yeah ... question 3 also has me kinda confused.
This is what I understand from the question:
-Assign the value of item to the last element in (length of) the list
-Initialize i
-Then iteratively search the list for item
-When the item is found, exit loop
-check if i = = the last element (the element you added)
-if it is, return -1
else return i;

This way there is only one comparison in the loop, and you do one extra comparison after the loop

I'm guessing you also have to remove the item from the back of the list before returning, but yeah ...
Hope this helps
 Re: PastExamPapersOct2006 October 03, 2007 09:14AM Registered: 14 years ago Posts: 131 Rating: 0
Thanks Pal.
 Re: PastExamPapersOct2006 October 03, 2007 08:53PM Registered: 13 years ago Posts: 1,501 Rating: 0
What baffle's me a little, is there not only 1 comparison in the Sequential search?
I've simplified my version to get rid of the extra comparison outside the loop as well. This makes it way simpler than the sentinel search.
I'm not sure what the advantage of the sentinel search would be?
 Re: PastExamPapersOct2006 October 03, 2007 10:21PM Registered: 12 years ago Posts: 472 Rating: 0
Hi AndreB,

What is your Big Oh analysis of the Sentinel search algorithm?
I also don't think there is an advantage in the sentinel search algorithm, it only ensures that the element is in the list?
 Re: PastExamPapersOct2006 October 03, 2007 10:38PM Registered: 13 years ago Posts: 1,501 Rating: 0
Sorry Count Zero - I haven't got to the Big Oh analysis yet.
I'm currently going through Sorting.
There is another issue with the sentinel - what happens if the item did already exist, you have now added a duplicate of it to the end of the array - to what advantage?
I'm probably missing the point here - so I'll continue with the sorting.
 Re: PastExamPapersOct2006 October 03, 2007 10:54PM Registered: 12 years ago Posts: 472 Rating: 0
Agreed, I don't get it either.

At least I'm more than half way with revision

 Re: PastExamPapersOct2006 October 04, 2007 02:57AM Registered: 13 years ago Posts: 1,501 Rating: 0
cheers - to you as well.
I quick look at the Big Oh analysis of the sentinal search - it should stay O(n).
I don't get question 4 a, at all. Swap the nodes, not just the values of info???

Any suggestions?
 Re: PastExamPapersOct2006 October 04, 2007 08:14AM Registered: 12 years ago Posts: 35 Rating: 0
Haven't yet reached the sentinel search, but what's your answers for question 1 (b) (ii). How do you do it? I've got O(n power 2). Any tips would be most welcome.

Question 9 (b) I've got this:

vertex Shortest Distance
0 ------ 4
1 ------ 6
2 ------ 0
3 ------ 5
4 ------ 7
5 ------ 5
6 ------ 9
 Re: PastExamPapersOct2006 October 04, 2007 08:50AM Registered: 14 years ago Posts: 131 Rating: 0
I got the same answer for 1(b)(i) and shortest distance is good.
Goodluck.
 Re: PastExamPapersOct2006 October 04, 2007 09:48AM Registered: 13 years ago Posts: 1,501 Rating: 0
Yeah - I also got O(n^2) for q1.b.2
 Re: PastExamPapersOct2006 October 04, 2007 12:49PM Registered: 12 years ago Posts: 13 Rating: 0
AndreB Wrote:
-------------------------------------------------------
> What baffle's me a little, is there not only 1
> comparison in the Sequential search?
> I've simplified my version to get rid of the extra
> comparison outside the loop as well. This makes it
> way simpler than the sentinel search.
> I'm not sure what the advantage of the sentinel
> search would be?

In a sequential/linear search, there are two comparisons every time the loop starts, it checks whether it has found the item, and it checks whether it has reached the last element in the list. In a sentinel search, it only needs to check if it has found the item. Half the work.

AndreB Wrote:
-------------------------------------------------------
> There is another issue with the sentinel - what happens if the item did
> already exist, you have now added a duplicate of it to the end of the array -
> I'm probably missing the point here - so I'll continue with the sorting.

When the search completes (whether the item was in the original list or not) you remove the "sentinel" from the back of the list again. See above comments for the advantage. I'm just giving my opinion. I might be wrong, so don't take my word for everything.
 Re: PastExamPapersOct2006 October 04, 2007 09:39PM Registered: 12 years ago Posts: 472 Rating: 0
Thanks Maggot!

That makes it very clear why the sentinel search is better than the sequential search.
So the Big Oh analysis is O(n)?

 Re: PastExamPapersOct2006 October 05, 2007 01:07AM Registered: 12 years ago Posts: 13 Rating: 0
Yip
 Re: PastExamPapersOct2006 October 05, 2007 02:28AM Registered: 13 years ago Posts: 1,501 Rating: 0
Thanks Maggot,
In the sequential search on array based list, there is no second check to see if the item has been found. i.e. making use of a for loop instead of a while loop.
I do see that with the sentinel search you could use a while loop with a single check.
Sequnetial search = O(n)
Sentinel search = O(n)
I do think that the question simply checks t osee if we actually understand the sequential search, and know how to modify it to a sentinel search.
The merrits of whether or not the sentinel search is a better search algorithm does not really matter, I suppose.
Cheers.
 Re: PastExamPapersOct2006 May 31, 2009 09:16AM Registered: 13 years ago Posts: 5 Rating: 0
Hi there,

I'm really struggling with Cos211-x. Can anyone be kind enough to mail me some past questions paper and/or tuts. Please.

Thanks
Jiby

Email: jiby.mundackal@gmail.com
Sorry, only registered users may post in this forum.