Welcome! Log In Create A New Profile

Advanced

Review

Posted by aronl 
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
Review
August 20, 2008 11:41AM
Dear Students

For the next few weeks I will regularly put up exercises on this forum based on the different Cos211x topics. You can discuss the questions and post your answers on the forum. I will look at your replies. We can also discuss any of the assignment questions you may have had a problem with.

For the next week(until 27/ 08) the questions will based on Algorithm analysis and Complexity.

Question for Today

Write in ascending order the Big-Oh time complexity of the following expressions:
i. n3 + n2 + 3
ii. n2 + n log n
iii. n + n log n
iv. 3n
v. 60028+logn

regards
Lazarus Aron
Re: Review
August 26, 2008 10:56AM
Due to the low(no) reponse, I will try this again when we get closer to the examinations.

regards
Lazarus
Re: Review
August 26, 2008 03:05PM
The review questions should prove useful especially to those like me who never saw the textbook throughout the year. Please continue.

Ascending order time complexity suggested.

v. 60028+logn
iv. 3n
iii. n + n log n
ii. n2 + n log n
i n3 + n2 + 3
avatar Re: Review
August 28, 2008 09:31AM
I agree with 'mattiemutare'
Anonymous User
Re: Review
September 02, 2008 04:48PM
I'd like to know how strictly the coding portion of our exam paper will be marked. I always test my submissions to confirm that they work and where I couldn't find a solution I state so.

However, time and time again the coding is marked very strictly, as if by comparison. I picked this up on a remarked paper that went from a outright rejection of my submission to a good score.

As students we are expected to code with pen and paper and it would help to know what the marking approach is please. Also consider that the problems experienced with the compiler will mean that students will apply modifications to what's in the prescribed book.
Re: Review
September 05, 2008 11:16AM
The assignments are marked by external markers and they sometimes tend to follow the marking guidelines more strictly than they are required to. They are told to look at each solution individually but they don't always do that. The exams will be marked by the lecturers. We understand that coding on paper under pressure is not the easiest thing to do and we are not strict. We use the marking memo just as a guideline and do not follow it strictly.

regards
Lazarus aron
avatar Re: Review
September 09, 2008 08:27AM
I would also say:

i. 60028+logn
ii. 3n
iii. n + n log n
iv. n2 + n log n
v. n3 + n2 + 3

regards
B
Re: Review
September 09, 2008 09:10AM
Remember the question says ... write in ascending order the Big Oh time complexity...
Re: Review
September 09, 2008 09:13AM
Here is another question.....

If an algorithm takes 1 second to run with a problem size of N = 10, what is the approximate time requirement for that same algorithm with a problem size of N = 50 if the time complexity is:

i) Linear
ii) Cubic
iii) Exponential (ie: O(2n))
avatar Re: Review
September 09, 2008 09:23AM
OK

i. O(logn) [60028+logn]
ii. O(n) [3n]
iii. O(n logn) [n + n log n]
iv. O(n2) [n2 + n log n]
v O(n3) [n3 + n2 + 3]
avatar Re: Review
September 09, 2008 09:56AM
aronl Wrote:
-------------------------------------------------------
> Here is another question.....
>
> If an algorithm takes 1 second to run with a
> problem size of N = 10, what is the approximate
> time requirement for that same algorithm with a
> problem size of N = 50 if the time complexity is:
>
> i) Linear
> ii) Cubic
> iii) Exponential (ie: O(2n))


i) 5 seconds
ii) 125 seconds
iii) 240 seconds = ~34865 years
Re: Review
September 09, 2008 10:57AM
i agree with kiolb
Anonymous User
Re: Review
September 09, 2008 12:07PM
I just wanted to say to the lecturer that this is a really great idea in using the forums this way - wish the other modules did the same.

(I've done this module already - but wish my last 3 module's lecturers were doing something similar)
Re: Review
September 09, 2008 08:24PM
i)5 seconds
ii) 12500 seconds
iii) 1.126 * 10^14 seconds or 2^46.678 seconds

Clive
Re: Review
September 10, 2008 09:28AM
Solution to first question is:

O(log n), O(n), O(n log n) ,O(n2), O(n3)

Solution to 2nd Question is :

i)T(n) = 5 seconds
ii)T(n) = (1 * 503) / 103 = 125 seconds
iii)T(n) = (1 * 2 50 )/ 2 10 = 2 40 seconds

See new thread (Review 2) for more questions

regards
Lazarus Aron
Sorry, only registered users may post in this forum.

Click here to login