Problems, Algorithms, Programs
Problem - a well defined task.Sort a list of numbers.Find a particular item in a list.Find a winning chess move.
A series of precise steps, known to stop eventually, that solve a problem.NOT necessarily tied to computers.There can be many algorithms to solve the same problem.
Characteristics of an Algorithm
Precise steps.Effective steps.Has an output.Terminates eventually.
Computing an average:Sum up all of the values.Divide the sum by the number of values.
Problems vs. Algorithms vs. Programs
There can be many algorithms that solve the same problem.There can be many programs that implement the same algorithm.We are concerned with:Analyzing the difficulty of problems.Finding good algorithms.Analyzing the efficiency of algorithms.
Search through a list of items for a particular value.Example:Search through an array of student records for the student with ID 12345.Search through an array of address records for the address of the person with last name Doe.
If we are searching in alist,start at the beginning and check each element until we find the one we want or reach the end.Bestcase?Worst case?Average case?
If we are searching in a sorted list, welook at the middle item and then choose which half to continue looking in.We continue to cut the area we are searching in half until we find thevalue,or there are no more values to check.Best case?Worstcase?Average case? (A little tricky)
BinarySearch: Worst Case
Let’s say the list has1024 items and the item is the last one we check.Check midpoint of 1024 items.Check midpoint of upper or lower half (512).Check midpoint of a half of that half (128).Successive ranges we are checking have lengths 64, 32, 16, 8, 4, 2, 1.How many checks was that? 10(log 1024 = 10)
Aside: Note that binary search only works if the data in the list aresortedby the field on which we’re searching!
Problems fall into two categories.Computable problems can be solved using an algorithm.Non-computable problems have no algorithm to solve them.Historical note:Hilbert’s questions in 1900: complete? Consistent? Decidable?
Historical note:Hilbert posed the following questions in 1900: Is mathematics complete? Is mathematics consistent? Is every statement in mathematics decidable?In 1930, he thought the all 3 answers would be “yes.”Almost immediately, Gödel showed that no closed system can be both complete & consistent.By the mid-1930’s, Turing showed that the answer to the 3rdquestion is “no.”
Two categories of problems:ComputableNon-computableWouldn’t it be nice to know which category a problem falls into? (Topic for laterin class:this problem itself is non-computable.)
Classifying Computable Problems
TractableThere is an efficient algorithm to solve the problem.IntractableThere is an algorithm to solve the problem but there is no efficient algorithm. (This is difficult to prove.)
Sorting: tractable.The traveling salesperson problem: intractable. (we think…)Halting Problem: non-computable.(More on thisin a minute.)
We are (usually) concerned with the time an algorithm takes to complete.Weoften countthe number oftimes blocks of code are executed,as a function of the size of the input.Why not measure time directly?Why not count the number of instructions executed?
If the array has N elements, this function executes 4 + (2 * N) statements (i.e., 2N + 4).
Example: Computing an Average
The statement inside the for loop gets executedlen(array) times.If the length isn, we say this algorithm is “on the order ofn”, or,O(n).O(n)??? What’s this?
def average(array):sum = 0for x in array:sum += xreturn sum / len(array)
The worst case running time, discounting constants and lower order terms.Example:n3+ 2n is O(n3)
Let’s work out the big O running time…
def exchangeSort(array):for indx1 in range(len(array)):for indx2 in range(indx1, len(array)):if (array[indx1] > array[indx2]):swap(array, indx1, indx2)
Given a list, split it into 2 equal piles.Then split each of these piles in half. Continue to do this until you are left with 1 element in each pile.Now merge piles back together in order.
An example of how the merge works:Suppose the first half and second half of an array are sorted:5 9 10 12 17 1 8 11 20 32Merge these by taking a new element from either the first or second subarray, choosing the smallest of the remaining elements.Big O running time?
Big O Can Be Misleading
Big O analysis is concerned with worst case behavior.Sometimes we know that we are not dealing with the worst case.
Searching an Array
Worst case?Best case?
def search(array, key):for x in array:if x == key:return key
Problem - Finding the Greatest Common Denominator
Examples:gcd(12, 2) = 2gcd(100, 95) = 5gcd(100, 75) = 25gcd(39, 26) = 13gcd(17, 8) = 1
Possible Algorithm #1
Assumption: A > B >= 0If A is a multiple of B, then gcd(A, B) = B.Otherwise, return an error.Works for gcd(12,2) = 2But what about gcd(100, 95)???
Possible Algorithm #2
Start with 1 and go up to B.If a number if a common divisor of both A and B, remember it.When we get to B, stop. The last number we remembered is the gcd.Works, but is there a better way?Think about gcd(100, 95)
Make use of the fact that:gcd(A, B) = gcd(B, A rem B)Note: A rem B refers to theremainderleft when A is divided by B.Examples:12 rem 2 = 0100 rem 95 = 5
If B = 0, then gcd(A, B) = A.Otherwise, gcd(A, B) = gcd (B, A rem B).Note – this algorithm isrecursive.Examples:gcd(12, 2) = gcd(2, 0) = 2gcd(100, 95) = gcd(95, 5) = gcd(5, 0) = 5
Why do we care?
Let’s say we want the gcd of 1,120,020,043,575,432 and 1,111,363,822,624,856Assume we can do 100,000,000 divisions per second.Algorithm #2 will take about three years.Euclid’s Algorithm will take less than a second.
Programs vs. Algorithms
Program: “A set of computer instructions written in a programming language”We writeProgramsthat implementAlgorithms
Algorithm vs. Program
def gcd(A, B):if B == 0:return Aelse:return gcd(B, A % B)
If B = 0, then gcd(A, B) = A.Otherwise, gcd(A, B) = gcd (B, A rem B).
Tractable vs. Intractable Problems
Problems with polynomial time algorithms are considered tractable.Problemswithoutpolynomial time algorithms are considered intractable.Eg. Exponential time algorithms.(More on Friday)