Algorithms • Definition ○ An algorithm is a finite set of precise instructions for performing a computation or for solving a problem. • Example: Describe an algorithm for finding the maximum value in a finite sequence of integers. ○ Perform the following steps: ○ Set the temporary maximum equal to the first integer in the sequence. ○ Compare the next integer in the sequence to the temporary maximum. § If it is larger than the temporary maximum, § set the temporary maximum equal to this integer. ○ Repeat the previous step if there are more integers. If not, stop. ○ When the algorithm terminates, the temporary maximum is the largest integer in the sequence. Specifying Algorithms • Algorithms can be specified in different ways. • Their steps can be described in English or in pseudocode. • Pseudocode is an intermediate step between an English language description of the steps and a coding of these steps using a programming language. • The form of pseudocode we use is specified in Appendix 3. • It uses some of the structures found in popular languages such as C++ and Java. • Programmers can use the description of an algorithm in pseudocode to construct a program in a particular language. • Pseudocode helps us analyze the time required to solve a problem using an algorithm, independent of the actual programming language used to implement algorithm. Properties of Algorithms • Input ○ An algorithm has input values from a specified set. • Output ○ From the input values, the algorithm produces the output values from a specified set. ○ The output values are the solution. • Correctness ○ An algorithm should produce the correct output values for each set of input values. • Finiteness ○ An algorithm should produce the output after a finite number of steps for any input. • Effectiveness ○ It must be possible to perform each step of the algorithm correctly and in a finite amount of time. • Generality ○ The algorithm should work for all problems of the desired form. Finding the Maximum Element in a Finite Sequence • The algorithm in pseudocode: • Does this algorithm have all the properties listed on the previous slide? Some Example Algorithm Problems • Three classes of problems will be studied in this section. • Searching Problems ○ finding the position of a particular element in a list. • Sorting problems ○ putting the elements of a list into increasing order. • Optimization Problems ○ determining the optimal value of a particular quantity over all possible inputs. Searching Problems • The general searching problem is to locate an element x in the list of distinct elements a_1,a_2,…,a_n, or determine that it is not in the list. • The solution to a searching problem is the location of the term in the list that equals x (that is, i is the solution if x=a_i) or 0 if x is not in the list. • For example, a library might want to check to see if a patron is on a list of those with overdue books before allowing him/her to checkout another book. • We will study two different searching algorithms; linear search and binary search. Linear Search Algorithm • The linear search algorithm locates an item in a list by examining elements in the sequence one at a time, starting at the beginning. • First compare x with a1. If they are equal, return the position 1. • If not, try a_2. If x=a_2, return the position 2. • Keep going, and if no match is found when the entire list is scanned, return 0. Binary Search • Assume the input is a list of items in increasing order. • The algorithm begins by comparing the element to be found with the middle element. ○ If the middle element is lower, the search proceeds with the upper half of the list. ○ If it is not lower, the search proceeds with the lower half of the list ○ Repeat this process until we have a list of size 1. ○ If the element we are looking for is equal to the element in the list, the position is returned. ○ Otherwise, 0 is returned to indicate that the element was not found. • In Section 3.3, we show that the binary search algorithm is much more efficient than linear search. • Here is a description of the binary search algorithm in pseudocode. Sorting • To sort the elements of a list is to put them in increasing order (numerical order, alphabetic, and so on). • Sorting is an important problem because: ○ A nontrivial percentage of all computing resources are devoted to sorting different kinds of lists, especially applications involving large databases of information that need to be presented in a particular order (e.g., by customer, part number etc.). ○ An amazing number of fundamentally different algorithms have been invented for sorting. Their relative advantages and disadvantages have been studied extensively. ○ Sorting algorithms are useful to illustrate the basic notions of computer science. • A variety of sorting algorithms are studied in this book; binary, insertion, bubble, selection, merge, quick, and tournament. • In Section 3.3, we’ll study the amount of time required to sort a list using the sorting algorithms covered in this section. Bubble Sort • Bubble sort makes multiple passes through a list. • Every pair of elements that are found to be out of order are interchanged. Insertion Sort • Insertion sort begins with the 2nd element. • It compares the 2nd element with the 1st and puts it before the first if it is not larger. • Next the 3rd element is put into the correct position among the first 3 elements. • In each subsequent pass, the (n+1)\th element is put into its correct position among the first n+1 elements. • Linear search is used to find the correct position. Greedy Algorithms • Optimization problems minimize or maximize some parameter over all possible inputs. • Among the many optimization problems we will study are: ○ Finding a route between two cities with the smallest total mileage. ○ Determining how to encode messages using the fewest possible bits. ○ Finding the fiber links between network nodes using the least amount of fiber. • Optimization problems can often be solved using a greedy algorithm, which makes the “best” choice at each step. • Making the “best choice” at each step does not necessarily produce an optimal solution to the overall problem, but in many instances, it does. • After specifying what the “best choice” at each step is, we try to prove that this approach always produces an optimal solution, or find a counterexample to show that it does not. • The greedy approach to solving problems is an example of an algorithmic paradigm, which is a general approach for designing an algorithm. • We return to algorithmic paradigms in Section 3.3. Greedy Algorithms: Making Change • Example ○ Design a greedy algorithm for making change (in U.S. money) of n cents with the following coins § quarters (25 cents) § dimes (10 cents) § nickels (5 cents) § pennies (1 cent) ○ using the least total number of coins. • Idea ○ At each step choose the coin with the largest possible value that does not exceed the amount of change left. ○ If n = 67 cents, first choose a quarter leaving 67−25 = 42 cents. Then choose another quarter leaving 42 −25 = 17 cents ○ Then choose 1 dime, leaving 17 − 10 = 7 cents. ○ Choose 1 nickel, leaving 7 – 5 = 2 cents. ○ Choose a penny, leaving one cent. Choose another penny leaving 0 cents. • Solution ○ G reedy change-making algorithm for n cents. ○ The algorithm works with any coin denominations c_1, c_2, …,c_r. ○ For the example of U.S. currency, we may have quarters, dimes, nickels and pennies, with c_1=25, c_2=10, c_3=5, c_4=1. • Proving Optimality ○ Lemma 1 § If n is a positive integer, then n cents in change using quarters, dimes, nickels, and pennies, using the fewest coins possible has at most 2 dimes, 1 nickel, 4 pennies, and cannot have 2 dimes and a nickel. § The total amount of change in dimes, nickels, and pennies must not exceed 24 cents. ○ Proof § If we had 3 dimes, we could replace them with a quarter and a nickel. § If we had 2 nickels, we could replace them with 1 dime. § If we had 5 pennies, we could replace them with a nickel. § If we had 2 dimes and 1 nickel, we could replace them with a quarter. § The allowable combinations, have a maximum value of 24 cents; 2 dimes and 4 pennies. ○ Theorem § The greedy change-making algorithm for U.S. coins produces change using the fewest coins possible. ○ Proof § Assume there is a positive integer n such that change can be made for n cents using quarters, dimes, nickels, and pennies, with a fewer total number of coins than given by the algorithm. § Then, q̍q where q̍ is the number of quarters used in this optimal way and q is the number of quarters in the greedy algorithm’s solution. § But this is not possible by Lemma 1, since the value of the coins other than quarters cannot be greater than 24 cents. § Similarly, by Lemma 1, the two algorithms must have the same number of dimes, nickels, and quarters. Halting Problem • Can we develop a procedure that takes as input a computer program along with its input and determines whether the program will eventually halt with that input. • Solution: Proof by contradiction. • Assume that there is such a procedure and call it H(P,I). • The procedure H(P,I) takes as input a program P and the input I to P. ○ H outputs “halt” if it is the case that P will stop when run with input I. ○ Otherwise, H outputs “loops forever.” • Since a program is a string of characters, we can call H(P,P). • Construct a procedure K(P), which works as follows. ○ If H(P,P) outputs “loops forever” then K(P) halts. ○ If H(P,P) outputs “halt” then K(P) goes into an infinite loop printing “ha” on each iteration. • Now we call K with K as input, i.e. K(K). ○ If the output of H(K,K) is “loops forever” then K(K) halts. A Contradiction. ○ If the output of H(K,K) is “halts” then K(K) loops forever. A Contradiction. • Therefore, there cannot be a procedure that can decide whether or not an arbitrary program halts. • The halting problem is unsolvable.
