The University of Pennsylvania — Computational Thinking for Problem Solving— Week Two
What a week it was…
The University of Pennsylvania’s Computational Thinking for Problem Solving course had an interesting second week. As with the first, this week provides plenty of information that is useful on many levels, especially as it pertains to programming. This week focuses on algorithms, in particular, the various types of algorithms. It focuses on efficiency and to take the lessons for week 1 and apply them in an even more practical manner.
The topics it focuses on, in particular, include Linear Search, Logarithmic Search, Quadratic Search, Algorithmic Complexity, Binary Search, and Greedy Algorithms.
While I will not discuss each one of them, I will discuss the ones I deemed most important and/or the ones that have personally interested me.
Linear Search
A Linear Search is a search in which someone looks at each item individually in the list until the object that is searched for is found. In essence, it would be like trying to find the number 7 in a list of 10 numbers.
1 2 3 4 5 6 7 8 9 10
First, you investigate the element “1” and compare it to the number you are searching for.
Is “1” = “7”?
No.
Is “2” = “7”?
No.
Is “3” = “7”?
No.
Is “4” = “7”?
No.
Is “5” = “7”?
No.
Is “6” = “7”?
No.
Is “7” = “7”?
Yes.
Then we conclude the search having found 7. What happens if 7 does not appear? For instance, if we used the following list:
1 2 3 4 5 6 8 9 10 11
does “7” appear?
So, we follow the same process as before for each number. We realize that “7” is not in the list.
The handy thing about the Linear Search is it works even if the numbers are not ordered. Though the Linear Search is inefficient with large numbers, even ten seemed tedious.
If the numbers are ordered, we can speed up the process.
Logarithmic Search
Take the list as before.
1 2 3 4 5 6 7 8 9 10
What this search will do is break the list in half.
We are looking for the number “7”.
1 2 3 4 5 6 7 8 9 10
Is “5” = “7”?
No.
5 < 7
Therefore, the number could not come before 5.
Our new list becomes
6 7 8 9 10
Repeating the search, we get:
6 7 8 9 10
is 8 = “7”?
No.
8 > 7
The last two numbers would include:
6 7
Is “7” = “7”?
Yes.
In three searches, we have found our number.
Notice that the number of searches will not increase all that much even if we double the number or quadruple it.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40.
Again, we would look at the middle of the list to check.
Is “20” = “7”?
No.
20 > 7.
Our new list becomes:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
Is “10” = “7”?
No.
10 > 7
1 2 3 4 5 6 7 8 9
Is “5” = “7”?
No.
6 7 8 9
Is “7” = “7”?
Yes.
Even with quadrupling the list, the search total only increased by 1.
This is why it is called a logarithmic search because the total searches increase logarithmically.
Finally,
Greedy Algorithm and Binary Search
A greedy algorithm is an algorithm designed to get the quickest solution, not necessarily the best.
A Binary Search is where you investigate every possible solution to find the best.
A greedy algorithm works best when there are too many options to worry about finding the most efficient one. A greedy algorithm also works best when the time is of the essence.
If you would like to know more either leave a comment below or enroll in the course!
Thank you for reading!
