Algorithms As Practical Tools for Solving Problems Pt. 1

An algorithm is just a set of instructions that tell a computer how to solve a problem. Our job as programmers is to write algorithms that solve problems efficiently.

Part one discusses the relationship between time, memory, input, and output in the context of designing algorithms.

Computer problems often take the form of:

Given x, solve y.

Here's an example: If given a word and a dictionary, can we find the definition?

Word and dictionary are inputs, and the answer to the question (either true or false) is the output.

Here is one way we might construct an algorithm:

1. Start on page 1.
2. Check if word exists on page.
3. If step 2 is true, then output "Booya! I found it!".
4. If step 2 is false and there is a next page, turn to it and repeat step 2.
5. If step 2 is false and there is no next page, output "Bummer, it's not there".

How efficient is this algorithm?

Asked another way, as the size of the input increases, by how much does the time and memory required to find the word increase? Assume the worst case scenario: the word you need is on the last page.

Since we're searching every page, the duration of our search would equal the speed at which we scan an individual page multiplied by how many pages there are. Therefor, time is spent linearly in relation to the size of the dictionary. In bigO notation we would denote this as O(n) runtime, because as the input size grows at rate n, the runtime also increases at rate n.

And since we need to store the dictionary while we search through it, the amount of memory needed is equal to the size of the dictionary itself. Again, as the number of pages increases, the amount of storage capacity needed increases at the same rate. In bigO we use the term space complexity to express this relationship. In the case of linear space complexity, like linear runtime, it is denoted as O(n).

It turns out that our algorithm may not be very efficient if for some reason our dictionary is billions of pages long! That would mean billions of page turns and billions of slots in memory to hold each page!

In Part 2 we will explore faster runtimes and improve our algorithm design using what is called binary search.

Exercises:

1. What would be an example of an algorithm with a runtime of O(1)?

2. What would be an example of an algorithm with a runtime of O(n^2) (hint: as the size of the input increases linearly, the runtime increases exponentially)?

3. In javascript, write a function that emulates the algorithm we wrote earlier. It should take two parameters: 1) an array containing any number of words as strings in alphabetical order (modeling a real dictionary), and 2) a single word in the form of a string.

The function should return true or false based on whether the word is contained in the array.

4. Copy this code into your text editor and use the array it produces as an argument in your function. Time how long it takes to search for the number 9999999:

let largeArray = []; 
for(let i = 0; i < 10000000; i++){
largeArray.push(i);
};