Programming - 7 - Algorithms

Question 1

An algorithm is the process of solving a problem in terms of…

Answer 1

• actions to exectute
• order in which these actions are executed

Question 2

Binary Search code

Answer 2

public int binaryS (int val ) {

int low = 0

int high = data.length-1;

while( high>= low) {

int middle = (low+high)/2;

if (val == data[middle]) return middle;

else if (val < data[middle]) high = mddle - 1;

else

low = middle+1;

}

Question 3

What sorts should you know?

Answer 3

• Selection sort: find the smallest val, swap wit the first, find 2nd smallest, swap with 2nd etc
• Bubble sort: compare adjacent elements, swap them if in wrong order. Repeat until sorted.

Question 4

Selection sort and bubble sort code

Answer 4

Question 5

Complexity: What does Big O notation describe

Answer 5

Describes worst case case run time (function of size n)

Question 6

Different types of complexities in terms of Big O

Answer 6

• O(1)
  
  • constant number of comparisons
• O(n)
  
  • linear run time (of the order n), linear search
• O(log(n))
  
  • logarithmic run time (binary search)
• O(n²)
  
  • quadratic run time (check if any element is duplicated in the array)

Question 7

What is the complexity of Selection Sort?

Answer 7

• Outer “i” loop controls iterations of the inner one over remaining elements
• inner loop does n- comparisons, then n-e,…. total is 1+2+…+(n-1)
  
  • (n²-n/2) = O(n²)

Question 8

Bubble Sort Complexity

Answer 8

• Inner for loop runs until outer while loop is stopped
• inner does n-1 comparisons for n passes → n*(n-1) = n² - n = O(n²)
• works well in “almost-sorted” arrays
  *