Algorithms

Apple and FBI debate:

• Two sided views
As someone who believes that privacy of data is vital in a day and age where hackers are rather common, I can understand the point of view from Apple, that they want to “protect their customers' privacy” and by making a stand they may be opening this argument for debate, something of which may be of use down the line even if not right now for technology.

I do however understand that, in the situation of the FBI, they have actually made moves to try and protect Apple, such as the ability to make it all happen at their own HQ, and in the case of terrorism it could be argued that it may benefit the world more to know about any other possible plans or terrorists (which could easily pose a threat in the future), than make a stand right now, especially given the potential implications for Apple.

Algorithms:

• Specify what you must accomplish
• Design the algorithm
• Check the correctness (Dry run/ Trace table)
• Analysis of the algorithm
• Implement the algorithm
• Test the resulting program

Basic algorithm:

Input x ---> Algorithm f: ---> output y

Input values = The Domain (For blackjack this would be the cards 1 - 11)
All possible outputted values = The Codomain (For blackjack this would be 21)
The codomain is any whole number 1 or above.

An algorithm will take a set of inputs, process them and give outputs. The input values to an algorithm are called the domain. All the possible values that could be outputted are called the codomain. For blackjack the domain is the value of cards from 1 to 11. The codomain of blackjack is

y = f(x) is a way of writing the algorithm f.

An example in Tax Calculator
The domain would be whole or decimal numbers which are greater than 0 (positive)
The codomain is also whole or decimal numbers


The Tax Calculator:

Basic rate 20%	£0 to £31,785  People with the standard Personal Allowance start paying this rate on income over £10,600
Higher rate 40%	£31,786 to £150,000  People with the standard Personal Allowance start paying this rate on income over £42,385
Additional rate 45%	Over £150,000

Standard Algorithms: 

 

Searching:

• Two of the most common searching algorithms are the linear search and the binary search
• The linear search starts at the beginning of the list and examines every item
• The binary search uses a 'divide and conquer' strategy which halves the search area each time an item is examined
• Only used if the items are in sorted

The Binary search algorithm:

START
         IMPORT list
         imin= 0
         max = (length of list) - 1
         found = false
        WHILE found = false THEN
               middle = int((low + high)/2)
        IF  list(middle) = x THEN
               found = TRUE 
               Output value
        Else IF value> mid THEN
               max = mid - 1
       ELSE
               min = mid +1
       END IF
STOP  


 Time complexity of Algorithms:
Using Big-O notation to describe how long an algorithm will take proportional to the amount of items.

For a linear search: O(n) - time proportional to the amount of numbers
For a binary search: O(log(n)) - time proportional to log on numbers

Therefore a binary search has a better time complexity of O(log(n)) which is smaller than a linear search.
And Linear search time complexity of O(n)

Disadvantages of binary searches:

• When the list is not in order binary searches are not very useful and this is because you can not eliminate halve of the possibilities when an item is not found.
• Binary search algorithms are harder to write than others.
• If the values are completely random the only choice is linear/serial search.
• If the list is really short then discarding halve has no advantages.
• If the list changes often the list would need to be resorted every time which would take a very long time so this may outweigh the advantages of the search
• if the elements you are searching for appear earlier on, a linear search would be more efficient.