X


Algorithms







PROPERTIES OF ALGORITHMS



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.



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.





Q. The greedy algorithm given above produces change using the fewest coins possible.



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.




Counting






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?



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?





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?



Q. How many different bit strings of length seven are there?



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)?





Q. How many functions are there from a set with "m" elements to a set with "n" elements?



Q. How many one-to-one functions are there 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?



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?





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?



Q. What is the value of k after the following code, where n1, n2, ... , nm are positive integers, has been executed?


Previous Next