## Desain dan Analisis Algoritma

Pake bukunya Anany Levitin yang berjudul : Introduction to The Design and Analysis of Algorithms

DOsen Pengajar : Esther H, Arunanto

Tugas ke I :

Exercise 2.1 nomor 1-10 halaman 51-53

1. For each of the following algorithms, indicate
(1)a natural size metric for its inputs;
(ii) its basic operation;
(iii) whether the basic operation count can be different for inputs of the same size.

• Computing the sum of a numbers
• Computing n
• Finding the largest element in a list of a numbers
• Euclid’s algorithm
• Sieve of Eratosthenes
• Pen-and-Pencil algorithm for multiplying two n-digit decimal integers
2. a. Consider the definition-based algorithm for adding two n-by-n matrices. What is its basic operation? How many times is it performed as a function of the matrix order n?As a function of the total number of elements in the input matrices?
b. Answer the same question for the definition-based algorithm for matrix multiplication.
3. Consider a variation of sequential search that scans list to return the number of occurrences of a given search key in the list. Will its effeciency differ from the efficiency of classic sequential search?
4. a. There are 22 gloves in a drawer: 5 pairs of red gloves, 4 pairs of yellow, and 2 pairs of green. You select the gloves in the dark and can check them only after a selection has been made. What is the smallest number of gloves you need to select to have at least one matching pair in the best case? In the worst case? ( After Mos01), 18).
b. Imagine that after washing 5 distinct pairs of socks you dscover that two socks are missing. Ofcourse, you would like to have the largest number of computer pairs remaining. Thus, you are left with 4 complete pairs in the best-case scenario and with 3 complete pairs in the worst case. Assuming that the disappearance of each of the 10 asocks is the same, find the probability of the best caase scenario, the probability of the worst-case scenario; the number of pairs you should expect in the average case (after [ Mos01], 48).
5. a .Prove formula (2.1) for the number of bits in the binary representation of a positive decimal integer.
b. What would be the analogus formula for the number of decimal digits?
c. Explain why, within the accepted analysis framework, it does not matter whether we use binary or decimal digits in measuring n’s size.
6. Suggest how any sorting algorithm can be augmented in a way to make the best-case count of its key comparisons equal to just n – 1 ( n is a list’s size, of course). Do you think it would be a worthwhile addition to any sorting algorithm

Jawaban :

http://rapidshare.com/files/144662223/TUGAS_1_-_Hal_51-53_-_Introduction_to_the_Design_and_Analysis_of_Algorithms.rar

Advertisements