text: {[ promptMessage ]}
  
  Bookmark it
  
  {[ promptMessage ]}
  
  # solu2 - This le contains the exercises hints and solutions...
  
  This preview shows pages 1–3. Sign up to view the full content.
  
  This file contains the exercises, hints, and solutions for Chapter 2 of the book ”Introduction to the Design and Analysis of Algorithms,” 2nd edition, by A. Levitin. The problems that might be challenging for at least some students are marked by ; those that might be diﬃcult for a majority of students are marked by . Exercises 2.1 1. For each of the following algorithms, indicate (i) 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: a. computing the sum of n numbers b. computing n ! c. finding the largest element in a list of n numbers d. Euclid’s algorithm e. sieve of Eratosthenes f. pen-and-pencil algorithm for multiplying two n -digit decimal integers 2. a. Consider the definition-based algorithm for adding two n -by- n matri- ces. 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 questions for the definition-based algorithm for matrix multiplication. 3. Consider a variation of sequential search that scans a list to return the number of occurrences of a given search key in the list. Will its eﬃciency differ from the eﬃciency of classic sequential search? 4. a. Glove selection 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. Missing socks Imagine that after washing 5 distinct pairs of socks, you discover that two socks are missing. Of course, you would like to have the largest number of complete 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 probability of disappearance for each 1
  
  This preview has intentionally blurred sections. Sign up to view the full version.
  
  View Full Document
  of the 10 socks is the same, find the probability of the best-case 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 integer. b. What would be the analogous formula for the number of decimal digits? c. Explain why, within the accepted analysis framework, it does not mat- ter 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?
  This is the end of the preview. Sign up to access the rest of the document.
  
  {[ snackBarMessage ]}
  
  ### What students are saying
  
  • As a current student on this bumpy collegiate pathway, I stumbled upon Course Hero, where I can find study resources for nearly all my courses, get online help from tutors 24/7, and even share my old projects, papers, and lecture notes with other students.
  
  Kiran Temple University Fox School of Business ‘17, Course Hero Intern
  
  • I cannot even describe how much Course Hero helped me this summer. It’s truly become something I can always rely on and help me. In the end, I was not only able to survive summer classes, but I was able to thrive thanks to Course Hero.
  
  Dana University of Pennsylvania ‘17, Course Hero Intern
  
  • The ability to access any university’s resources through Course Hero proved invaluable in my case. I was behind on Tulane coursework and actually used UCLA’s materials to help me move forward and get everything together on time.
  
  Jill Tulane University ‘16, Course Hero Intern
explanation: This document is a set of exercises, hints, and solutions from Chapter 2 of a book on the design and analysis of algorithms. It contains multiple questions and no answers are provided within the text.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: {[ promptMessage ]}
  
  Bookmark it
  
  {[ promptMessage ]}
  
  # solu2 - This le contains the exercises hints and solutions...
  
  This preview shows pages 1–3. Sign up to view the full content.
  
  This file contains the exercises, hints, and solutions for Chapter 2 of the book ”Introduction to the Design and Analysis of Algorithms,” 2nd edition, by A. Levitin. The problems that might be challenging for at least some students are marked by ; those that might be diﬃcult for a majority of students are marked by . Exercises 2.1 1. For each of the following algorithms, indicate (i) 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: a. computing the sum of n numbers b. computing n ! c. finding the largest element in a list of n numbers d. Euclid’s algorithm e. sieve of Eratosthenes f. pen-and-pencil algorithm for multiplying two n -digit decimal integers 2. a. Consider the definition-based algorithm for adding two n -by- n matri- ces. 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 questions for the definition-based algorithm for matrix multiplication. 3. Consider a variation of sequential search that scans a list to return the number of occurrences of a given search key in the list. Will its eﬃciency differ from the eﬃciency of classic sequential search? 4. a. Glove selection 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. Missing socks Imagine that after washing 5 distinct pairs of socks, you discover that two socks are missing. Of course, you would like to have the largest number of complete 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 probability of disappearance for each 1
  
  This preview has intentionally blurred sections. Sign up to view the full version.
  
  View Full Document
  of the 10 socks is the same, find the probability of the best-case 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 integer. b. What would be the analogous formula for the number of decimal digits? c. Explain why, within the accepted analysis framework, it does not mat- ter 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?
  This is the end of the preview. Sign up to access the rest of the document.
  
  {[ snackBarMessage ]}
  
  ### What students are saying
  
  • As a current student on this bumpy collegiate pathway, I stumbled upon Course Hero, where I can find study resources for nearly all my courses, get online help from tutors 24/7, and even share my old projects, papers, and lecture notes with other students.
  
  Kiran Temple University Fox School of Business ‘17, Course Hero Intern
  
  • I cannot even describe how much Course Hero helped me this summer. It’s truly become something I can always rely on and help me. In the end, I was not only able to survive summer classes, but I was able to thrive thanks to Course Hero.
  
  Dana University of Pennsylvania ‘17, Course Hero Intern
  
  • The ability to access any university’s resources through Course Hero proved invaluable in my case. I was behind on Tulane coursework and actually used UCLA’s materials to help me move forward and get everything together on time.
  
  Jill Tulane University ‘16, Course Hero Intern
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: This document is a set of exercises, hints, and solutions from Chapter 2 of a book on the design and analysis of algorithms. It contains multiple questions and no answers are provided within the text.
  
  Label: multiple-question