Preview

02 - Classification of Algorithms

 1. To quote Google itself, “Algorithms are the computer processes and formulas that take your questions and turn them into answers.” Decide whether the following 'fun fact' is true or false
Fun fact: SEO community Moz states that Google makes between 500-600 changes to its algorithm annually (Image credit: E2M Solutions)
google_search_algorithm_updates.jpg

  TRUE

  FALSE

 2. In terms of the purpose of an algorithm, we can broadly divide algorithms into three categories. Select the most appropriate answer from the options.

  Python algorithms, Java algorithms, C algorithms

  Big O algorithms, Non-Big O algorithms, Big N algorithms

  Searching algorithns, Sorting algorithms, Path-finding algorithms

  Server side algorithms, Client side algorithms, no-side algorithms

 3. That is the amount of (memory) space the algorithm will take up before it terminates with the correct solution

  matriarchal-efficiency

  time-wise efficiency

  spatial-efficiency

  space-wise efficiency

 4. This is the amount of time it takes for the algorithm to terminate with the correct solution.

  spatial-efficiency

  time-wise efficiency

  matriarchal-efficiency

  space-wise efficiency

 5. The following excerpt lists the different types of algorithms by implementation. Can you fill in the blanks for the first?
1 -???????????????or iterative
==============================
A ______________ algorithm is one that calls itself repeatedly until a certain condition matches. 
It is a method common to functional programming. 
Iterative algorithms use repetitive constructs like loops.
Some problems are better suited for one implementation or the other. For example, the 
towers of hanoi problem is well understood in recursive implementation. Every recursive 
version has an iterative equivalent iterative, and vice versa.

2 -Logical or procedural
=========================
An algorithm may be viewed as controlled logical deduction. 
A logic component expresses the axioms which may be used in the computation and a control 
component determines the way in which deduction is applied to the axioms. 
This is the basis of the logic programming. In pure logic programming languages the control 
component is fixed and algorithms are specified by supplying only the logic component.

3 - Serial or parallel
========================
Algorithms are usually discussed with the assumption that computers execute one instruction
 of an algorithm at a time. This is a serial algorithm, as opposed to parallel algorithms, 
which take advantage of computer architectures to process several instructions at once. 
They divide the problem into sub-problems and pass them to several processors. Iterative
 algorithms are generally parallelizable. Sorting algorithms can be parallelized efficiently.

4 - Deterministic or non-deterministic
========================================
Deterministic algorithms solve the problem with a predefined process whereas non-deterministic
 algorithm must perform guesses of best solution at each step through the use of heuristics.

  Recursive

  Mindful

  Cache based

  Big O based

 6. This kind of algorithm repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively), until the instances are small enough to solve easily.

  divide and conquer algorithms

  brute force algorithm

  backtracking algorithms

  recursion algorithm

 7. These algorithms are based on a depth-first recursive search

  backtracking algorithms

  divide and conquer algorithms

  brute force algorithm

  recursion algorithm

 8. These algorithms simply try all possibilities until a satisfactory solution is found

  backtracking algorithms

  brute force algorithm

  divide and conquer algorithms

  recursion algorithm

 9. Often, brute force algorithms require exponential time. Various heuristics and optimizations can be used. A ________ is a rule of thumb that helps you decide which possibilities to look at first

  optimisation

  recursion algorithm

  brute force algorithm

  heuristic

 10. Traditionally, an algorithm is only called “divide and conquer” if it contains at least two recursive calls

  TRUE

  FALSE

 11. Read the following excerpt on 'greedy algorithms' and fill in the blanks
A greedy algorithm works in phases: At each phase:

>>You take the ________________________, without regard for
future consequences

>>You hope that by choosing a local optimum at each step, you
will end up at a global optimum

  input and duplicate it

  best you can get right now

  worst case scenario

  option that provides the lengthiest output

 12. Algorithms can be classified in different ways. Which of the following are not likely to be valid classification methods?
Classification .....

...By purpose
...By implementation
...By design paradigm
...By complexity
...By length of algorithm name
...By exact output

  By design paradigm

  By length of algorithm name, and By exact output

  By implementation and By complexity

  By purpose and By complexity

 13. An expensive algorithm is one that requires the equivalent of _______, that is --> (O(2n)) time.
fibonacci_number_return_sum_of_numbers.png

  exponential

  linear

  finite

  infinite

 14. A ________________ algorithm remembers past results and uses them to find new results

  linear programming

  brute force algorithm

  dynamic programming

  masked programming

 15. A randomized algorithm uses a random number at least once during the computation to make a decision. An example is:

  In Binary Search, setting a random midpoint variable

  None of these options are valid examples of a randomisation algorithm

  In Linear Search, setting a random first index position.

  In Quicksort, using a random number to choose a pivot