Algorithms
Setting up the appropriate mathematical model is only part of the solution. To complete the solution, a method is needed that will solve the general problem using the model.
Ideally, what is required is a procedure that follows a sequence of steps that leads to the desired answer. Such a sequence of steps is called an algorithm.
PROPERTIES OF ALGORITHMS
Input. An algorithm has input values from a specified set.
Output. From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem.
Definiteness. The steps of an algorithm must be defined precisely
Correctness. An algorithm should produce the correct output values for each set of input values.
Finiteness. An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set.
Effectiveness. It must be possible to perform each step of an algorithm exactly and in a finite amount of time.
Generality. The procedure should be applicable for all problems of the desired form, not just for a particular set of input values
Greedy Algorithms
One of the simplest approaches to optimize often leads to a solution of an optimization problem. This approach selects the best choice at each step, instead of considering all sequences of steps that may lead to an optimal solution.
Algorithms that make what seems to be the “best” choice at each step are called greedy algorithms.
Q. Consider the problem of making "n" cents change with quarters (25p), dimes (10p), nickels (5p), and pennies (1p), and using the least total number of coins by devising a greedy algorithm.
ALGORITHM - Greedy Change-Making Algorithm :
c1, c2 ... cr: Values of denominations of coins, where c1 > c2 > ... > cr ; n: a positive integer)
di counts the coins of denomination ci used
di is the number of coins of denomination ci in the change for i = 1, 2,...,r
procedure change(c1, c2 ... cr
for i := 1 to r
di := 0
while n ≥ ci
di := di + 1
n := n - ci
If we have only quarters, dimes, and pennies (and no nickels) to use, the greedy algorithm would make change for 30 cents using six coins — a quarter and five pennies — whereas we could have used three coins, namely, three dimes.
LEMMA :- 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 two dimes, at most one nickel, at most four pennies, and cannot have two dimes and a nickel. The amount of change in dimes, nickels, and pennies cannot exceed 24 cents.
We use a proof by contradiction. We will show that if we had more than the specified number of coins of each type, we could replace them using fewer coins that have the same value.
We note that if we had three dimes we could replace them with a quarter and a nickel, if we had two nickels we could replace them with a dime, if we had five pennies we could replace them with a nickel, and if we had two dimes and a nickel we could replace them with a quarter.
Because we can have at most two dimes, one nickel, and four pennies, but we cannot have two dimes and a nickel, it follows that 24 cents is the most money we can have in dimes, nickels, and pennies when we make change using the fewest number of coins for n cents.
Q. The greedy algorithm given above produces change using the fewest coins possible.
Suppose that there is a positive integer "n" such that there is a way to make change for "n" cents using quarters, dimes, nickels, and pennies that uses fewer coins than the greedy algorithm finds.
Then "q'" , the number of quarters used in this optimal way to make change for "n" cents, must be the same as "q", the number of quarters used by the greedy algorithm.
To show this, first note that the greedy algorithm uses the most quarters possible, so q' ≤ q. However, it is also the case that "q'" cannot be less than "q". If it were, we would need to make up at least 25 cents from dimes, nickels, and pennies in this optimal way to make change. But this is impossible by Lemma given above.
Because there must be the same number of quarters in the two ways to make change, the value of the dimes, nickels, and pennies in these two ways must be the same, and these coins are worth no more than 24 cents.
There must be the same number of dimes, because the greedy algorithm used the most dimes possible and by Lemma 1, when change is made using the fewest coins possible, at most one nickel and at most four pennies are used, so that the most dimes possible are also used in the optimal way to make change. Similarly, we have the same number of nickels and, finally, the same number of pennies.
The Halting Problem - It asks whether there is a procedure that does this: It takes as input a computer program and input to the program and determines whether the program will eventually stop when run with this input.
Assume there is a solution to the halting problem, a procedure called H(P,I). The procedure H(P,I) takes two inputs, one a program P and the other I , an input to the program P.
H(P,I) generates the string “halt” as output if H determines that P stops when given I as input. Otherwise, H(P,I) generates the string “loops forever” as output. We will now derive a contradiction.
When a procedure is coded, it is expressed as a string of characters; this string can be interpreted as a sequence of bits.
This means that a program itself can be used as data. Therefore a program can be thought of as input to another program, or even itself. Hence, H can take a program P as both of its inputs, which are a program and input to this program. H should be able to determine whether P will halt when it is given a copy of itself as input.
To show that no procedure H exists that solves the halting problem, we construct a simple procedure K(P), which works as follows, making use of the output H(P,P).
If the output of H(P,P) is “loops forever,” which means that P loops forever when given a copy of itself as input, then K(P) halts. If the output of H(P,P)is “halt” which means that P halts when given a copy of itself as input, then K(P) loops forever.
That is, K(P) does the opposite of what the output of H(P,P) specifies.
Now suppose we provide K as input to K. We note that if the output of H(K,K) is “loops forever” then by the definition of K we see that K(K) halts. Otherwise, if the output of H(K,K) is “halt,” then by the definition of K we see that K(K) loops forever, in violation of what H tells us. In both cases, we have a contradiction.
Counting
THE PRODUCT RULE: Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1 * n2 ways to do the procedure.
THE SUM RULE: If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways to do the task. 1 ways is the same as any of the set of n2 ways, then there are n1 + n2
Q. A new company with just two employees, Sanchez and Patel, rents a floor of a building with 12 offices. How many ways are there to assign different offices to these two employees?
The procedure of assigning offices to these two employees consists of assigning an office to Sanchez, which can be done in 12 ways, then assigning an office to Patel different from the office assigned to Sanchez, which can be done in 11 ways.
y the product rule, there are 12 · 11 = 132 ways to assign offices to these two employees.
Q. The chairs of an auditorium are to be labeled with an uppercase English letter followed by a positive integer not exceeding 100. What is the largest number of chairs that can be labeled differently?
The procedure of labeling a chair consists of two tasks, namely, assigning to the seat one of the 26 uppercase English letters, and then assigning to it one of the 100 possible integers.
The product rule shows that there are 26 · 100 = 2600 different ways that a chair can be labeled. Therefore, the largest number of chairs that can be labeled differently is 2600.
Q. There are 32 microcomputers in a computer center. Each microcomputer has 24 ports. How many different ports to a microcomputer in the center are there?
The procedure of choosing a port consists of two tasks, first picking a microcomputer and then picking a port on this microcomputer.
Because there are 32 ways to choose the microcomputer and 24 ways to choose the port no matter which microcomputer has been selected, the product rule shows that there are 32 · 24 = 768 ports.
Q. How many different bit strings of length seven are there?
Each of the seven bits can be chosen in two ways, because each bit is either 0 or 1.
Therefore, the product rule shows there are a total of 27 = 128 different bit strings of length seven
Q. How many different license plates can be made if each plate contains a sequence of three uppercase English letters followed by three digits (and no sequences of letters are prohibited, even if they are obscene)?
There are 26 choices for each of the three uppercase English letters and ten choices for each of the three digits.
Hence, by the product rule there are a total of 26 · 26 · 26 · 10 · 10 · 10 = 17,576,000 possible license plates.
Q. How many functions are there from a set with "m" elements to a set with "n" elements?
A function corresponds to a choice of one of the "n" elements in the codomain for each of the "m" elements in the domain.
Hence, by the product rule there are n · n · ··· · n = nm functions from a set with m elements to one with n elements.
For example, there are 53 = 125 different functions from a set with three elements to a set with five elements
Q. How many one-to-one functions are there from a set with "m" elements to one with "n" elements?
When m > n there are no one-to-one functions from a set with "m" elements to a set with "n" elements.
Now let m ≤ n, Suppose the elements in the domain are a1, a2, ... , am. There are "n" ways to choose the value of the function at a1.
Because the function is one-to-one, the value of the function at a2 can be picked in n − 1 ways (because the value used for a1 cannot be used again)
In general, the value of the function at ak can be chosen in n − k + 1 ways. By the product rule, there are n(n − 1)(n − 2) ··· (n − m + 1) one-to-one functions from a set with "m" elements to one with "n" elements.
Q. What is the value of k after the following code, where n1, n2, ... , nm are positive integers, has been executed?
k := 0 for i1 := 1 to n1 for i2 := 1 to n2 . . . for im := 1 to nm k := k + 1The innermost loop has executed n1 * n2 ... nm times.
Hence the value of k is n1 * n2 ... nm.
Q. Suppose that either a member of the mathematics faculty or a student who is a mathematics major is chosen as a representative to a university committee. How many different choices are there for this representative if there are 37 members of the mathematics faculty and 83 mathematics majors and no one is both a faculty member and a student?
There are 37 ways to choose a member of the mathematics faculty and there are 83 ways to choose a student who is a mathematics major.
Choosing a member of the mathematics faculty is never the same as choosing a student who is a mathematics major because no one is both a faculty member and a student. By the sum rule it follows that there are 37 + 83 = 120 possible ways to pick this representative.
Q. A student can choose a computer project from one of three lists. The three lists contain 23, 15, and 19 possible projects, respectively. No project is on more than one list. How many possible projects are there to choose from?
The student can choose a project by selecting a project from the first list, the second list, or the third list. Because no project is on more than one list, by the sum rule there are 23 + 15 + 19 = 57 ways to choose a project.
Q. What is the value of k after the following code, where n1, n2, ... , nm are positive integers, has been executed?
k := 0 for i1 := 1 to n1 k := k + 1 for i2 := 1 to n2 k := k + 1 . . . for im := 1 to nm k := k + 1
The innermost loop has executed n1 + n2 ... + nm times.
Hence the value of k is n1 + n2 + ... + nm.