Category Archives: Computer Science

Every thing that deals with computer science

Big O Notation explained simply - image

Big O Notation Simply Explained

Context

A kid has a set of 100 toys. His friend pays him a visit and they want to play a specific toy. With this large number of toys, the search becomes difficult. John knows search algorithm A, while Paul Knows Algorithm B.

john and paul - image

John and paul – image

1. Problem

The kids have at their disposal two algorithms: A & B. How would they compare their algorithms so as to choose the one that helps them find the specific toy as quick as possible? Giving that Paul has only 30 minutes to be with John.

2. Solution

Big O provides a means by which algorithms can be compared in terms of speed of execution.  The kids have to choose between two algorithms: A & B.

Lets consider that A is some sort of sequential search while B is some sort of optimized search. Assuming it takes 1 millisecond to check one toy. With algorithm A, the kids have to to check 100 toys, so the search takes 100ms to run. With algorithm B, an optimized search, the kids have only to check 7 toys and this takes log2100 which gives 7 (don’t worry on the math). 

By increasing the number of toys to 100 000 000 toys. With algorithm A, the kids take 27 hours. By this time, Paul has left John’s house and is very angry. He no longer wishes to speaks to John. On the otherhand, if they use algorithm B, it would only take 27s. This gives enough time for Paul to enjoy the toy.

The run times for A and B don’t grow at the same rate. As the list of items gets bigger, B becomes a lot faster than A.

By knowing the Big O of both algorithms and choosen the algorithm with the lowest big O, the kids would continue to be friends and Paul would keep paying visits to John so that they may enjoy the toy.

2.1 Characteristics of Big O Notation

Big O notation tells you how fast an algorithm is. Big O does not measure speed in seconds but the number of operations.  It is written as follows:

Big O Notation formula

Big O Notation formula

Consider a list of size n. Algorithm A needs to check each element, so it will take n operations. The Big O notation is O(n). Algorithm B needs log n operations to check the same list. Its Big O notation is given as O(log n).

Growth rate - image

Growth rate – image

The graph of O(n) increases faster than O(log n). Thus an algorithm with O(n) would take much time to execute ( slower)  than an algorithm with O(log n).

Big O notation measures the worst case scenario. It identifies how an algorithm behaves when giving large scale inputs (infinity).If we’re using algorithm A to look for a toy. In the worst case, we will have to go through each toy and finally get the required toy at the end i.e O(n).

Big O measures the big picture. In such situations, we are not interested with the “exact” relation between input and run time. Expressions like O(n+3) and O(n2 + 3n + 4) are not accepted as at large scale input the 3 and 3n+4 terms are of negligible importance . Since we just need a gist of the complexity we just talk of O(n) and O(n2) respectively.

3. Conclusion

Here are the main take aways:

  • Algorithm speed isn’t measured in seconds but in growth of the number of operations
  • We measure an algorithm by idenfying how quickly its run time increases as the size of the input increases
  • Run time is expressed in Big O notation
  • O(log n) is faster than O(n) but it gets a lot faster as the list of items you’re searching grows.

Referencees:

How to block an IP address on your ubuntu server

To block an IP on your Linux server you need to use iptables tools. First you need to log into shell as root user. To block an IP address you need to type the iptables command as follows:

iptables -A INPUT -s IP-ADDRESS -j DROP

The option A stands for Add

Replace IP-ADDRESS with your actual IP address. For example, if you wish to block an ip address 46.38.144.17 for whatever reason then type the command as follows:

iptables -A INPUT -s 46.38.144.17 -j DROP

To block a particular port say port 22, use the following command:

iptables -A INPUT -s 46.38.144.17 -p tcp --destination-port 22 -j DROP

HOW TO UNBLOCK AN IP ADDRESS

To unblock an IP address use the option D. It stands for delete:

iptables -D INPUT -s 46.38.144.17 -j DROP

SAVING YOUR FIREWALL RULES

To save the rules so that they remain even after your machine reboots you have to install iptables-persistent.:

sudo apt-get update

sudo apt-get install iptables-persistent

Then run :

sudo invoke-rc.d iptables-persistent save

Elements for this articles have been taken from:

Cameroon GCE O level Computer Science Past Questions and answers

answers to GCE computer science Ordinary level questions

answers to GCE computer science Ordinary level questions

 

Disclaimer:
These are not official marking guides. The answers given here express a personal point of view. Please use with caution. Feel free to contribute or report a problem at gamonana.wordpress.com/contact

  • Cameroon GCE O Level Computer Science Past Paper 1 Questions June 2018

  • Cameroon GCE O Level Computer Science Past Paper 2 Questions and  answers from 2016 to 2018

  • Cameroon GCE O Level Computer Science Past Paper 3 June 2018

Structure of the Cameroon GCE O level Computer science Exam

The GCE Computer Science at the Ordinary level consist of 3 papers namely: Paper 1, 2 and 3.
Paper 2 accounts for 30% of the overall mark. It consists of 7 essay questions of which you are
required to answer 5. Section A of this paper comprises of two compulsory questions while
Section B will require you to answer any three out of five questions. This paper has a duration of 2hrs.

Some tips when writing the Cameroon GCE O level computer science exam

1.To get familiar with the type of questions asked, get to solve as many past questions
as possible;
2. You must not necessarily solve all GCE past questions for you to succeed. A couple of
past questions for 3 to 5 years is enough;
3. Start with the easy questions first, it gives you motivation. Once you are done with
the easy questions you can go tackle the difficult one.
4. When revising for your exam, do not seek to cram but to understand your notes.
Understand in your words would stick better into your brain than trying to memorize
the notes of your teacher, word for word;
5. Pray before you start writing your exam. God always guide his Children.

Sources of question:

  1. http://www.cameroongcerevision.com/category/o-level-past-Papers/
  2. https://www.thebigbrains.org/download-category/gce/