Skip to content

Latest commit

 

History

History
110 lines (91 loc) · 5.31 KB

T311-18122018.md

File metadata and controls

110 lines (91 loc) · 5.31 KB

LESSON 11 - TOPIC 3: Algorithm Efficiency

Accompanying code files:

Jump to Homework

Algorithm Efficiency

So we have a general idea of how to approach programming now, and we always go for the simplest implementation first for the sake of successful implementation and testing. For many methods, this is perfectly fine, and we do not have to revisit them to make improvements. This is because many methods do not have a lot of input to work with. Consider the following for loop:

for (int i = 0, i < n; i++) {
  // do something
}
  • How many times does the loop body execute? What about for the code below:
for (int i = 0, i < n; i++) {
  for (int j = 0, j < n; j++) {
    // do something
  }
}
  • Obviously, the second one will take a lot longer to finish executing; an order of magnitude times longer!
  • For small values of n, this is not a huge problem, but for really, really, large values of n, the processing time might be too long to be feasible or useful.
  • With these cases, it is important to optimize your algorithm. Note that you should only care about optimization once you have a fully-functional basic solution first.

Optimization

When it comes to optimization of algorithms, there are 2 resources that we want to be economical in their use:

  • CPU TIME: This refers to the number of operations required to carry out the algorithm
  • MEMORY: This refers to the number and complexity of the variables used
  • Things that affect run-time efficiency include unnecessary tests, excessive movement of data elements, and redundant computations, especially in loops.
  • Always aim for early detection of output conditions: a sorting algorithm should stop as soon as the list is sorted, and your search algorithm should stop as soon as the key element has been found.
  • When it comes to algorithms that consume a lot of memory, usually algorithms involving recursion will be responsible for this.
// Sequential Search Algorithm
int[] numbers = getNumbers(10);

public Boolean find(int x) {
  for (int i = 0; i < this.length(); i++) {
    if (this[i] == x) {
      return true;
    }
  }
  return false;
}

public Boolean find(int x) {
  int i = 0;
  while (i < this.length()) {
    if (this[i] == x) {
      return true;
    }
    i++;
  }
  return false;
}

public Boolean find(int x, int acc) {
  if (acc == this.length()) {
    return false;
  } else if (x == this[acc]) {
    return true;
  } else {
    find(x, acc + 1);
  }
}
  • But how do we know when it is worth making changes to your algorithm to optimize it?
  • We examine 3 cases: the best case, the worst case, and the average case.
  • BEST CASE: this is the situation where the input data causes the algorithm time to run in the shortest possible time that it can
  • WORSE CASE: this is the situation where the input data causes the algorithm time to run in the longest possible time that it can
  • AVERAGE CASE: this is the typical situation where most input data would fall under, and generally the case that is the most important to consider
  • It is possible for there to be little difference in the best, worse, and average case scenarios.
  • You should be able to identify what would be the best/worst/average cases for algorithms in the AP exam, but you do not need to know any more detail than this.
  • For your interest, this cheatsheet details the time and space complexity for several common algorithms across different data structures.
  • Also for your interest - the following is the no-coding optimization question I mentioned in class that I was once asked during a technical interview:

There are 4 people that need to cross a bridge from one side to the other. The bridge will collapse in exactly 17 minutes, and person A will take exactly 1 minute to cross the bridge, person B will take exactly 2 minutes, person C will take exactly 5 minutes, and person D will take exactly 10 minutes. At most 2 people can cross a bridge at any time and it's also really dark, so there is exactly one torch that at least one person must carry as they cross the bridge. How can you get everyone to cross the bridge safely to the other side before the bridge collapses?

ANSWER:

Left Side Crossing Time to Cross Total Time Elapsed Right Side
ABCD 0
CD A + B to right 2 2
CD A to left 1 3 B
A C + D to right 10 13 B
A B to left 2 15 CD
A + B to right 2 17 CD
17 ABCD

HOMEWORK

Assignments:

  • Complete the Map Assignment: implement the User.java and Map.java classes until all the tests pass in the UnitTestMap.java class - INVITATION
  • From the Program Design & Analysis Question Set, complete: 4, 5, 11.
  • Answers will be posted on the Topic 3 assignment answers issue.

Prep for Next Class:

  • N/A