# Review

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
 Review August 20, 2008 11:41AM Registered: 14 years ago Posts: 88 Rating: 0
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 Registered: 14 years ago Posts: 88 Rating: 0
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 Registered: 11 years ago Posts: 79 Rating: 0
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
 Re: Review August 28, 2008 09:31AM Registered: 14 years ago Posts: 560 Rating: 2
I agree with 'mattiemutare'
 Anonymous User Re: Review September 02, 2008 04:48PM Rating: 0
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 Registered: 14 years ago Posts: 88 Rating: 0
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
 Re: Review September 09, 2008 08:27AM Registered: 11 years ago Posts: 423 Rating: 0
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 Registered: 14 years ago Posts: 88 Rating: 0
Remember the question says ... write in ascending order the Big Oh time complexity...
 Re: Review September 09, 2008 09:13AM Registered: 14 years ago Posts: 88 Rating: 0
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))
 Re: Review September 09, 2008 09:23AM Registered: 11 years ago Posts: 423 Rating: 0
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]
 Re: Review September 09, 2008 09:56AM Registered: 11 years ago Posts: 423 Rating: 0
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 Registered: 11 years ago Posts: 79 Rating: 0
i agree with kiolb
 Anonymous User Re: Review September 09, 2008 12:07PM Rating: 0
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 Registered: 13 years ago Posts: 98 Rating: 0
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 Registered: 14 years ago Posts: 88 Rating: 0
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.