Posted by aronl

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 |

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. n^{3} + n^{2} + 3

ii. n^{2} + n log n

iii. n + n log n

iv. 3n

v. 60028+logn

regards

Lazarus Aron

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. n

ii. 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 |

Re: Review August 26, 2008 03:05PM |
Registered: 11 years ago Posts: 79 Rating: 0 |

Re: Review August 28, 2008 09:31AM |
Registered: 14 years ago Posts: 560 Rating: 2 |

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.

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

regards

Lazarus aron

Re: Review September 09, 2008 08:27AM |
Registered: 11 years ago Posts: 423 Rating: 0 |

Re: Review September 09, 2008 09:10AM |
Registered: 14 years ago Posts: 88 Rating: 0 |

Re: Review September 09, 2008 09:13AM |
Registered: 14 years ago Posts: 88 Rating: 0 |

Re: Review September 09, 2008 09:23AM |
Registered: 11 years ago Posts: 423 Rating: 0 |

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) 2^{40} seconds = ~34865 years

-------------------------------------------------------

> 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) 2

Re: Review September 09, 2008 10:57AM |
Registered: 11 years ago Posts: 79 Rating: 0 |

Anonymous User
Re: Review September 09, 2008 12:07PM |
Rating: 0 |

Re: Review September 09, 2008 08:24PM |
Registered: 13 years ago Posts: 98 Rating: 0 |

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(n^{2}), O(n^{3})

Solution to 2nd Question is :

i)T(n) = 5 seconds

ii)T(n) = (1 * 50^{3}) / 10^{3} = 125 seconds

iii)T(n) = (1 * 2^{50} )/ 2 ^{10} = 2 ^{40} seconds

See new thread (Review 2) for more questions

regards

Lazarus Aron

O(log n), O(n), O(n log n) ,O(n

Solution to 2nd Question is :

i)T(n) = 5 seconds

ii)T(n) = (1 * 50

iii)T(n) = (1 * 2

See new thread (Review 2) for more questions

regards

Lazarus Aron

Sorry, only registered users may post in this forum.