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
PastExamPapersOct2006
October 01, 2007 03:10PM
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
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
Thanks Pal.
Re: PastExamPapersOct2006
October 03, 2007 08:53PM
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?
avatar Re: PastExamPapersOct2006
October 03, 2007 10:21PM
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
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.
avatar Re: PastExamPapersOct2006
October 03, 2007 10:54PM
Agreed, I don't get it either.

O well, I must also start with sorting sad smiley
At least I'm more than half way with revision smiling smiley

Good luck with your studies!
Re: PastExamPapersOct2006
October 04, 2007 02:57AM
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?
avatar Re: PastExamPapersOct2006
October 04, 2007 08:14AM
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
I got the same answer for 1(b)(i) and shortest distance is good.
Goodluck.
Re: PastExamPapersOct2006
October 04, 2007 09:48AM
Yeah - I also got O(n^2) for q1.b.2
Re: PastExamPapersOct2006
October 04, 2007 12:49PM
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 -
> to what advantage?
> 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.
avatar Re: PastExamPapersOct2006
October 04, 2007 09:39PM
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)?

@Lordamp your answers seem to be correct.smile
Re: PastExamPapersOct2006
October 05, 2007 01:07AM
Yip
Re: PastExamPapersOct2006
October 05, 2007 02:28AM
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
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.

Click here to login