# Difference between revisions of "Chapter 1"

Jump to navigation
Jump to search

m (Protected "Chapter 1" ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite))) |
|||

(4 intermediate revisions by the same user not shown) | |||

Line 1: | Line 1: | ||

+ | Below are the exercises at the end of chapter 1 of the third edition of the Algorithm Design Manual by Steven Skiena. Student proposed answers to odd number questions are available by clicking on the question number. | ||

+ | |||

=Introduction to Algorithms= | =Introduction to Algorithms= | ||

Line 4: | Line 6: | ||

:[[1.1]]. Show that <math>a + b</math> can be less than <math>\min(a,b)</math>. | :[[1.1]]. Show that <math>a + b</math> can be less than <math>\min(a,b)</math>. | ||

+ | [[1.1|Solution]] | ||

Line 10: | Line 13: | ||

:[[1.3]]. Design/draw a road network with two points <math>a</math> and <math>b</math> such that the fastest route between <math>a</math> and <math>b</math> is not the shortest route. | :[[1.3]]. Design/draw a road network with two points <math>a</math> and <math>b</math> such that the fastest route between <math>a</math> and <math>b</math> is not the shortest route. | ||

+ | [[1.3|Solution]] | ||

Line 20: | Line 24: | ||

#Put the elements of <math>S</math> in the knapsack from smallest to largest, i.e. the best-fit algorithm. | #Put the elements of <math>S</math> in the knapsack from smallest to largest, i.e. the best-fit algorithm. | ||

#Put the elements of <math>S</math> in the knapsack from largest to smallest. | #Put the elements of <math>S</math> in the knapsack from largest to smallest. | ||

+ | [[1.5|Solution]] | ||

Line 28: | Line 33: | ||

:[[1.7]]. The ''maximum clique problem'' in a graph <math>G = (V, E)</math> asks for the largest subset <math>C</math> of vertices <math>V</math> such that there is an edge in <math>E</math> between every pair of vertices in <math>C</math>. Find a counterexample for the following algorithm: Sort the vertices of <math>G</math> from highest to lowest degree. Considering the vertices in order of degree, for each vertex add it to the clique if it is a neighbor of all vertices currently in the clique. Repeat until all vertices have been considered. | :[[1.7]]. The ''maximum clique problem'' in a graph <math>G = (V, E)</math> asks for the largest subset <math>C</math> of vertices <math>V</math> such that there is an edge in <math>E</math> between every pair of vertices in <math>C</math>. Find a counterexample for the following algorithm: Sort the vertices of <math>G</math> from highest to lowest degree. Considering the vertices in order of degree, for each vertex add it to the clique if it is a neighbor of all vertices currently in the clique. Repeat until all vertices have been considered. | ||

+ | [[1.7|Solution]] | ||

+ | |||

===Proofs of Correctness=== | ===Proofs of Correctness=== | ||

Line 45: | Line 52: | ||

<math>p = p*x+A_i</math> | <math>p = p*x+A_i</math> | ||

return <math>p</math> | return <math>p</math> | ||

+ | [[1.9|Solution]] | ||

+ | |||

:1.10. Prove the correctness of the following sorting algorithm. | :1.10. Prove the correctness of the following sorting algorithm. | ||

Line 59: | Line 68: | ||

:Prove that Euclid’s algorithm is correct. | :Prove that Euclid’s algorithm is correct. | ||

+ | [[1.11|Solution]] | ||

+ | |||

===Induction=== | ===Induction=== | ||

Line 66: | Line 77: | ||

:[[1.13]]. Prove that <math>\sum_{i=1}^n i^2</math>=<math>n(n+1)(2n+1)/6</math> for <math>n \geq\ 0</math>, by induction. | :[[1.13]]. Prove that <math>\sum_{i=1}^n i^2</math>=<math>n(n+1)(2n+1)/6</math> for <math>n \geq\ 0</math>, by induction. | ||

+ | [[1.13|Solution]] | ||

Line 72: | Line 84: | ||

:[[1.15]]. Prove that <math> \sum_{i=1}^n i(i+1)(i+2)=n(n+1)(n+2)(n+3)/4 </math> | :[[1.15]]. Prove that <math> \sum_{i=1}^n i(i+1)(i+2)=n(n+1)(n+2)(n+3)/4 </math> | ||

+ | [[1.15|Solution]] | ||

Line 78: | Line 91: | ||

:[[1.17]]. Prove by induction that for <math>n \geq 1</math>, <math> \sum_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1} </math> | :[[1.17]]. Prove by induction that for <math>n \geq 1</math>, <math> \sum_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1} </math> | ||

+ | [[1.17|Solution]] | ||

Line 84: | Line 98: | ||

:[[1.19]]. Prove by induction that a tree with <math>n</math> vertices has exactly <math>n-1</math> edges. | :[[1.19]]. Prove by induction that a tree with <math>n</math> vertices has exactly <math>n-1</math> edges. | ||

+ | [[1.19|Solution]] | ||

Line 89: | Line 104: | ||

::::::::::::<math> \sum_{i=1}^n i^3 = ( \sum_{i=1}^n i )^2 </math> | ::::::::::::<math> \sum_{i=1}^n i^3 = ( \sum_{i=1}^n i )^2 </math> | ||

+ | |||

===Estimation=== | ===Estimation=== | ||

:[[1.21]]. Do all the books you own total at least one million pages? How many total pages are stored in your school library? | :[[1.21]]. Do all the books you own total at least one million pages? How many total pages are stored in your school library? | ||

+ | [[1.21|Solution]] | ||

Line 99: | Line 116: | ||

:[[1.23]]. How many hours are one million seconds? How many days? Answer these questions by doing all arithmetic in your head. | :[[1.23]]. How many hours are one million seconds? How many days? Answer these questions by doing all arithmetic in your head. | ||

+ | [[1.23|Solution]] | ||

Line 105: | Line 123: | ||

:[[1.25]]. Estimate how many cubic miles of water flow out of the mouth of the Mississippi River each day. Do not look up any supplemental facts. Describe all assumptions you made in arriving at your answer. | :[[1.25]]. Estimate how many cubic miles of water flow out of the mouth of the Mississippi River each day. Do not look up any supplemental facts. Describe all assumptions you made in arriving at your answer. | ||

+ | [[1.25|Solution]] | ||

Line 111: | Line 130: | ||

:[[1.27]]. How long would it take to empty a bathtub with a drinking straw? | :[[1.27]]. How long would it take to empty a bathtub with a drinking straw? | ||

+ | [[1.27|Solution]] | ||

Line 119: | Line 139: | ||

::(a) if you believe that the algorithm takes time proportional to n2, and | ::(a) if you believe that the algorithm takes time proportional to n2, and | ||

::(b) if you believe that the algorithm takes time roughly proportional to n log n? | ::(b) if you believe that the algorithm takes time roughly proportional to n log n? | ||

+ | [[1.29|Solution]] | ||

Line 127: | Line 148: | ||

:[[1.31]]. Describe how to test whether a given set of tickets establishes sufficient coverage in the Lotto problem of Section 1.8 (page 22). Write a program to find good ticket sets. | :[[1.31]]. Describe how to test whether a given set of tickets establishes sufficient coverage in the Lotto problem of Section 1.8 (page 22). Write a program to find good ticket sets. | ||

+ | [[1.31|Solution]] | ||

Line 135: | Line 157: | ||

:[[1.33]]. There are twenty-five horses. At most, five horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done. | :[[1.33]]. There are twenty-five horses. At most, five horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done. | ||

+ | [[1.33|Solution]] | ||

Line 141: | Line 164: | ||

:[[1.35]]. How many gas stations are there in the United States? | :[[1.35]]. How many gas stations are there in the United States? | ||

+ | [[1.35|Solution]] | ||

Line 147: | Line 171: | ||

:[[1.37]]. How many miles of road are there in the United States? | :[[1.37]]. How many miles of road are there in the United States? | ||

+ | [[1.37|Solution]] | ||

## Latest revision as of 18:05, 1 October 2020

Below are the exercises at the end of chapter 1 of the third edition of the Algorithm Design Manual by Steven Skiena. Student proposed answers to odd number questions are available by clicking on the question number.

## Contents

# Introduction to Algorithms

### Finding Counter Examples

- 1.1. Show that
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a + b}**can be less than**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \min(a,b)}**.

- 1.2. Show that
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a \times b}**can be less than**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \min(a,b)}**.

- 1.3. Design/draw a road network with two points
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b}**such that the fastest route between**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b}**is not the shortest route.

- 1.4. Design/draw a road network with two points
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b}**such that the shortest route between

- 1.5. The
*knapsack problem*is as follows: given a set of integers**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S = \{s_1, s_2, \ldots, s_n\}}**, and a target number**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T}**, find a subset of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**which adds up exactly to**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T}**. For example, there exists a subset within**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S = \{1, 2, 5, 9, 10\}}**that adds up to**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T=22}**but not**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T=23}**. - Find counterexamples to each of the following algorithms for the knapsack problem. That is, giving an
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T}**such that the subset is selected using the algorithm does not leave the knapsack completely full, even though such a solution exists.

- Put the elements of
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**in the knapsack in left to right order if they fit, i.e. the first-fit algorithm. - Put the elements of
- Put the elements of

- 1.6. The
*set cover problem*is as follows: given a set**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1, ..., S_m}**of the universal set**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle U = \{1,...,n\}}**, find the smallest subset of subsets**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T \subset S}**such that**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \cup_{t_i \in T} t_i = U}**.For example, there are the following subsets,**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1 = \{1, 3, 5\}}**,**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_2 = \{2,4\}}**,**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_3 = \{1,4\}}**, and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_4 = \{2,5\}}**The set cover would then be**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_2}**.

- Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.

- 1.7. The
*maximum clique problem*in a graph**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G = (V, E)}**asks for the largest subset**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C}**of vertices**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle V}**such that there is an edge in**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E}**between every pair of vertices in**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C}**. Find a counterexample for the following algorithm: Sort the vertices of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G}**from highest to lowest degree. Considering the vertices in order of degree, for each vertex add it to the clique if it is a neighbor of all vertices currently in the clique. Repeat until all vertices have been considered.

### Proofs of Correctness

- 1.8. Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c \geq 2}**.

multiply(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y,z}) #Return the productFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle yz}.ifFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z=0}thenreturn(0)elsereturn(multiply(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle cy,\lfloor z/c \rfloor)+y \cdot (z\,\bmod\,c}))

- 1.9. Prove the correctness of the following algorithm for evaluating a polynomial. P(x) =
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0}**

horner(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A,x})Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p = A_n}forFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i}from to return

- 1.10. Prove the correctness of the following sorting algorithm.

bubblesort ( : list[]) for from to for from to if () swap the values of and

- 1.11. The
*greatest common divisor of positive*integers and is the largest integer such that divides and divides . Euclid’s algorithm to compute where reduces the task to a smaller problem:

- Prove that Euclid’s algorithm is correct.

### Induction

- 1.12. Prove that = for , by induction.

- 1.13. Prove that = for , by induction.

- 1.14. Prove that = for , by induction.

- 1.15. Prove that

- 1.16. Prove by induction on that for every ,

- 1.17. Prove by induction that for ,

- 1.18. Prove by induction that is divisible by for all .

- 1.19. Prove by induction that a tree with vertices has exactly edges.

- 1.20. Prove by mathematical induction that the sum of the cubes of the first positive integers is equal to the square of the sum of these integers, i.e.

### Estimation

- 1.21. Do all the books you own total at least one million pages? How many total pages are stored in your school library?

- 1.22. How many words are there in this textbook?

- 1.23. How many hours are one million seconds? How many days? Answer these questions by doing all arithmetic in your head.

- 1.24. Estimate how many cities and towns there are in the United States.

- 1.25. Estimate how many cubic miles of water flow out of the mouth of the Mississippi River each day. Do not look up any supplemental facts. Describe all assumptions you made in arriving at your answer.

- 1.26. How many Starbucks or McDonald’s locations are there in your country?

- 1.27. How long would it take to empty a bathtub with a drinking straw?

- 1.28. Is disk drive access time normally measured in milliseconds (thousandths of a second) or microseconds (millionths of a second)? Does your RAM memory access a word in more or less than a microsecond? How many instructions can your CPU execute in one year if the machine is left running all the time?

- 1.29. A sorting algorithm takes 1 second to sort 1,000 items on your machine. How long will it take to sort 10,000 items. . .
- (a) if you believe that the algorithm takes time proportional to n2, and
- (b) if you believe that the algorithm takes time roughly proportional to n log n?

### Implementation Projects

- 1.30. Implement the two TSP heuristics of Section 1.1 (page 5). Which of them gives better solutions in practice? Can you devise a heuristic that works better than both of them?

- 1.31. Describe how to test whether a given set of tickets establishes sufficient coverage in the Lotto problem of Section 1.8 (page 22). Write a program to find good ticket sets.

### Interview Problems

- 1.32. Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

- 1.33. There are twenty-five horses. At most, five horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done.

- 1.34. How many piano tuners are there in the entire world?

- 1.35. How many gas stations are there in the United States?

- 1.36. How much does the ice in a hockey rink weigh?

- 1.37. How many miles of road are there in the United States?

- 1.38. On average, how many times would you have to flip open the Manhattan phone book at random in order to find a specific name?

Back to Chapter List