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 speciﬁed set.**Output.**From each set of input values an algorithm produces output values from a speciﬁed set. The output values are the solution to the problem.**Deﬁniteness.**The steps of an algorithm must be deﬁned 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 ﬁnite (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 ﬁnite 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 :****c**Values of denominations of coins, where c_{1}, c_{2}... c_{r}:_{1}> c_{2}> ... > c_{r}; n: a positive integer)d

_{i}counts the coins of denomination c_{i}usedd

_{i}is the number of coins of denomination c_{i}in the change for i = 1, 2,...,rprocedure change(c

_{1}, c_{2}... c_{r}for i := 1 to r

d

_{i}:= 0while n ≥ c

_{i}d

_{i}:= d_{i}+ 1n := n - c

_{i}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 ﬁve 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 speciﬁed 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 ﬁve 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 ﬁnds.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, ﬁrst 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, ﬁnally, 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)**speciﬁes.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 deﬁnition of**K**we see that**K(K)**halts. Otherwise, if the output of**H(K,K)**is “halt,” then by the deﬁnition of**K**we see that**K(K)**loops forever, in violation of what**H**tells us. In both cases, we have a**contradiction**.

**THE PRODUCT RULE:**Suppose that a procedure can be broken down into a sequence of two tasks. If there are**n**ways to do the ﬁrst task and for each of these ways of doing the ﬁrst task, there are_{1}**n**ways to do the second task, then there are_{2}**n**ways to do the procedure._{1}* n_{2}**THE SUM RULE:**If a task can be done either in one of**n**ways or in one of_{1}**n**ways, where none of the set of_{2}**n**ways to do the task. 1 ways is the same as any of the set of_{1}**n**ways, then there are_{2}**n**_{1}+ n_{2}

**Q. A new company with just two employees, Sanchez and Patel, rents a ﬂoor of a building with
12 ofﬁces. How many ways are there to assign different ofﬁces to these two employees?**

The procedure of assigning ofﬁces to these two employees consists of assigning an ofﬁce to Sanchez, which can be done in

**12 ways**, then assigning an ofﬁce to Patel different from the ofﬁce assigned to Sanchez, which can be done in**11 ways**.y the product rule, there are

**12 · 11 = 132 ways**to assign ofﬁces 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, ﬁrst 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

**2**different bit strings of length seven^{7}= 128

**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 =

**n**functions from a set with m elements to one with n elements.^{m}For example, there are

**5**= 125 different functions from a set with three elements to a set with ﬁve elements^{3}

**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**a**. There are "n" ways to choose the value of the function at a_{1}, a_{2}, ... , a_{m}_{1}.Because the function is one-to-one, the value of the function at

**a**can be picked in_{2}**n − 1**ways (because the value used for**a**cannot be used again)_{1}In general, the value of the function at

**a**can be chosen in_{k}**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 n _{1}, n_{2}, ... , n_{m}
are positive integers, has
been executed?**

k := 0 for i

_{1}:= 1 to n_{1}for i_{2}:= 1 to n_{2}. . . for i_{m}:= 1 to n_{m}k := k + 1The innermost loop has executed n

_{1}* n_{2}... n_{m}times.Hence the value of k is

**n**._{1}* n_{2}... n_{m}

**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 ﬁrst 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 n _{1}, n_{2}, ... , n_{m}
are positive integers, has
been executed?**

k := 0 for i

_{1}:= 1 to n_{1}k := k + 1 for i_{2}:= 1 to n_{2}k := k + 1 . . . for i_{m}:= 1 to n_{m}k := k + 1The innermost loop has executed

**n**times._{1}+ n_{2}... + n_{m}Hence the value of k is

**n**._{1}+ n_{2}+ ... + n_{m}

Previous | Next |