# Difference between revisions of "Introduction-TADM2E"

(Recovering wiki) |
(Recovering wiki) |
||

Line 4: | Line 4: | ||

'''Finding Counterexamples''' | '''Finding Counterexamples''' | ||

− | + | <br>1-1. | |

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

[[TADM2E 1.1|(Solution 1.1)]] | [[TADM2E 1.1|(Solution 1.1)]] | ||

− | + | <br>1-2. | |

− | Show that | + | Show that <math>a \times b</math> can be less than <math>\min(a,b)</math>. |

[[TADM2E 1.2|(Solution 1.2)]] | [[TADM2E 1.2|(Solution 1.2)]] | ||

− | + | <br>1-3. | |

− | Design/draw a road network with two points | + | Design/draw a road network with two points <math>a</math> and <math>b</math> such that the |

− | fastest route between | + | fastest route between <math>a</math> and <math>b</math> is not the shortest route. |

[[TADM2E 1.3|(Solution 1.3)]] | [[TADM2E 1.3|(Solution 1.3)]] | ||

− | + | <br>1-4. | |

− | Design/draw a road network with two points | + | Design/draw a road network with two points <math>a</math> and <math>b</math> such that the |

− | shortest route between | + | shortest route between <math>a</math> and <math>b</math> is not the route with the fewest turns. |

− | + | <br>1-5. | |

The ''knapsack problem'' | The ''knapsack problem'' | ||

− | is as follows: given a set of integers | + | is as follows: given a set of integers <math>S = \{s_1, s_2, \ldots, s_n\}</math>, and |

− | a target number | + | a target number <math>T</math>, find a subset of <math>S</math> which adds up |

− | exactly to | + | exactly to <math>T</math>. |

− | For example, there exists a subset within | + | For example, there exists a subset within <math>S = \{1, 2, 5, 9, 10\}</math> that |

− | adds up to | + | adds up to <math>T=22</math> but not <math>T=23</math>. |

Find counterexamples to each of the following algorithms for the knapsack | Find counterexamples to each of the following algorithms for the knapsack | ||

problem. | problem. | ||

− | That is, giving an | + | That is, giving an <math>S</math> and <math>T</math> such that the subset is |

selected using the algorithm does not leave the knapsack completely full, | selected using the algorithm does not leave the knapsack completely full, | ||

even though such a solution exists. | even though such a solution exists. | ||

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

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

[[TADM2E 1.5|(Solution 1.5)]] | [[TADM2E 1.5|(Solution 1.5)]] | ||

− | + | <br>1-6. | |

The ''set cover problem'' | The ''set cover problem'' | ||

− | is as follows: given a set of subsets | + | is as follows: given a set of subsets <math> S_1, ..., S_m</math> |

− | of the universal set | + | of the universal set <math>U = \{1,...,n\}</math>, |

− | find the smallest subset of subsets | + | find the smallest subset of subsets <math>T \subset S</math> |

− | such that | + | such that <math>\cup_{t_i \in T} t_i = U</math>. |

− | For example, there are the following subsets, | + | For example, there are the following subsets, <math>S_1 = \{1, 3, 5\}</math>, |

− | + | <math>S_2 = \{2,4\}</math>, <math>S_3 = \{1,4\}</math>, and <math>S_4 = \{2,5\}</math> | |

− | The set cover would then be | + | The set cover would then be <math>S_1</math> and <math>S_2</math>. |

Find a counterexample for the following algorithm: | Find a counterexample for the following algorithm: | ||

Select the largest subset for the cover, | Select the largest subset for the cover, | ||

Line 62: | Line 62: | ||

'''Proofs of Correctness''' | '''Proofs of Correctness''' | ||

− | + | <br>1-7. | |

Prove the correctness of the following recursive algorithm | Prove the correctness of the following recursive algorithm | ||

to multiply two natural numbers, for all | to multiply two natural numbers, for all | ||

− | integer constants | + | integer constants <math>c \geq 2</math>. |

− | ''function'' multiply( | + | ''function'' multiply(<math>y,z</math>) |

− | ''comment'' Return the product | + | ''comment'' Return the product <math>yz</math>. |

− | 1. ''if'' | + | 1. ''if'' <math>z=0</math> ''then'' return(0) ''else'' |

− | 2. return(multiply( | + | 2. return(multiply(<math>cy,\lfloor z/c \rfloor)+y \cdot (z\,\bmod\,c</math>)) |

[[TADM2E 1.7|(Solution 1.7)]] | [[TADM2E 1.7|(Solution 1.7)]] | ||

− | + | <br>1-8. | |

Prove the correctness of the following algorithm for evaluating a | Prove the correctness of the following algorithm for evaluating a | ||

− | polynomial. P(x) = | + | polynomial. P(x) = <math>a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0</math> |

− | ''function'' horner( | + | ''function'' horner(<math>A,x</math>) |

− | + | <math>p = A_n</math> | |

− | for | + | for <math>i</math> from <math>n-1</math> to <math>0</math> |

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

− | return | + | return <math>p</math> |

− | + | <br>1-9. | |

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

− | ''function'' bubblesort ( | + | ''function'' bubblesort (<math>A</math> : list[<math>1 \dots n</math>]) |

− | var int | + | var int <math>i, j</math> |

− | for | + | for <math>i</math> from <math>n</math> to <math>1</math> |

− | for | + | for <math>j</math> from <math>1</math> to <math>i-1</math> |

− | if ( | + | if (<math>A[j] > A[j+1]</math>) |

− | swap the values of | + | swap the values of <math>A[j]</math> and <math>A[j+1]</math> |

[[TADM2E 1.9|(Solution 1.9)]] | [[TADM2E 1.9|(Solution 1.9)]] | ||

Line 96: | Line 96: | ||

'''Induction''' | '''Induction''' | ||

− | + | <br>1-10. | |

− | Prove that | + | Prove that <math>\sum_{i=1}^n i</math>=<math>n(n+1)/2</math> for <math>n \geq 0</math>, |

by induction. | by induction. | ||

− | + | <br>1-11. | |

Prove that | 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. | by induction. | ||

[[TADM2E 1.11|(Solution 1.11)]] | [[TADM2E 1.11|(Solution 1.11)]] | ||

− | + | <br>1-12. | |

Prove | Prove | ||

− | that | + | that <math>\sum_{i=1}^n i^3</math>=<math>n^2(n+1)^2/4</math> |

− | for | + | for <math>n \geq 0</math>, |

by induction. | by induction. | ||

− | + | <br>1-13. | |

Prove that | Prove that | ||

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

[[TADM2E 1.13|(Solution 1.13)]] | [[TADM2E 1.13|(Solution 1.13)]] | ||

− | + | <br>1-14. | |

− | Prove by induction on | + | Prove by induction on <math>n \geq 1</math> that for every <math>a \neq 1</math>, |

− | + | <math> \sum_{i=0}^n a^i =\frac{a^{n+1}-1}{a-1}</math> | |

} | } | ||

− | + | <br>1-15. | |

− | Prove by induction that for | + | 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> | |

[[TADM2E 1.15|(Solution 1.15)]] | [[TADM2E 1.15|(Solution 1.15)]] | ||

− | + | <br>1-16. | |

− | Prove by induction that | + | Prove by induction that <math>n^3+2n</math> is divisible by <math>3</math> for all <math>n \geq 0</math>. |

}{ | }{ | ||

[[TADM2E 1.16|(Solution 1.16)]] | [[TADM2E 1.16|(Solution 1.16)]] | ||

− | + | <br>1-17. | |

− | Prove by induction that a tree with | + | Prove by induction that a tree with <math>n</math> vertices has exactly <math>n-1</math> edges. |

[[TADM2E 1.17|(Solution 1.17)]] | [[TADM2E 1.17|(Solution 1.17)]] | ||

− | + | <br>1-18. | |

− | Prove by mathematical induction that the sum of the cubes of the first | + | Prove by mathematical induction that the sum of the cubes of the first <math>n</math> |

positive integers is equal to the square of the sum of these integers, i.e. | positive integers is equal to the square of the sum of these integers, i.e. | ||

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

[[TADME2E 1.18|(Solution 1.18)]] | [[TADME2E 1.18|(Solution 1.18)]] | ||

Line 151: | Line 151: | ||

'''Estimation''' | '''Estimation''' | ||

− | + | <br>1-19. | |

Do all the books you own total at least one million pages? | Do all the books you own total at least one million pages? | ||

How many total pages are stored in your school library? | How many total pages are stored in your school library? | ||

Line 157: | Line 157: | ||

− | + | <br>1-20. | |

How many words are there in this textbook? | How many words are there in this textbook? | ||

− | + | <br>1-21. | |

How many hours are one million seconds? | How many hours are one million seconds? | ||

How many days? | How many days? | ||

Line 167: | Line 167: | ||

[[TADM2E 1.21|(Solution 1.21)]] | [[TADM2E 1.21|(Solution 1.21)]] | ||

− | + | <br>1-22. | |

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

− | + | <br>1-23. | |

Estimate how many cubic miles of water flow out of the mouth of | Estimate how many cubic miles of water flow out of the mouth of | ||

the Mississippi River each day. | the Mississippi River each day. | ||

Line 178: | Line 178: | ||

[[TADM2E 1.23|(Solution 1.23)]] | [[TADM2E 1.23|(Solution 1.23)]] | ||

− | + | <br>1-24. | |

Is disk drive access time normally measured in | Is disk drive access time normally measured in | ||

milliseconds (thousandths of a second) or | milliseconds (thousandths of a second) or | ||

Line 187: | Line 187: | ||

machine is left running all the time? | machine is left running all the time? | ||

− | + | <br>1-25. | |

A sorting algorithm takes 1 second to sort 1,000 items on your local | A sorting algorithm takes 1 second to sort 1,000 items on your local | ||

machine. | machine. | ||

How long will it take to sort 10,000 items ... | How long will it take to sort 10,000 items ... | ||

− | #if you believe that the algorithm takes time proportional to | + | #if you believe that the algorithm takes time proportional to <math>n^2</math>, and |

− | #if you believe that the algorithm takes time roughly proportional to | + | #if you believe that the algorithm takes time roughly proportional to <math>n\log n</math>? |

[[TADM2E 1.25|(Solution 1.25)]] | [[TADM2E 1.25|(Solution 1.25)]] | ||

Line 199: | Line 199: | ||

'''Implementation Projects''' | '''Implementation Projects''' | ||

− | + | <br>1-26. | |

Implement the two TSP heuristics of '''tsp-robot'''. | Implement the two TSP heuristics of '''tsp-robot'''. | ||

Which of them gives better-quality solutions in practice? | Which of them gives better-quality solutions in practice? | ||

Can you devise a heuristic that works better than both of them? | Can you devise a heuristic that works better than both of them? | ||

− | + | <br>1-27. | |

Describe how to test whether a given set of tickets establishes | Describe how to test whether a given set of tickets establishes | ||

sufficient coverage in the Lotto problem | sufficient coverage in the Lotto problem | ||

Line 214: | Line 214: | ||

'''Interview Problems''' | '''Interview Problems''' | ||

− | + | <br>1-28. | |

Write a function to perform integer division without using either the | Write a function to perform integer division without using either the | ||

− | + | <tt>/</tt> or <tt>*</tt> operators. | |

Find a fast way to do it. | Find a fast way to do it. | ||

[[TADM2E 1.28|(Solution 1.28)]] | [[TADM2E 1.28|(Solution 1.28)]] | ||

− | + | <br>1-29. | |

There are 25 horses. At most, 5 horses can race | There are 25 horses. At most, 5 horses can race | ||

together at a time. You must determine the fastest, second fastest, and third | together at a time. You must determine the fastest, second fastest, and third | ||

Line 229: | Line 229: | ||

[[TADM2E 1.29|(Solution 1.29)]] | [[TADM2E 1.29|(Solution 1.29)]] | ||

− | + | <br>1-30. | |

How many piano tuners are there in the entire world? | How many piano tuners are there in the entire world? | ||

− | + | <br>1-31. | |

How many gas stations are there in the United States? | How many gas stations are there in the United States? | ||

[[TADM2E 1.31|(Solution 1.31)]] | [[TADM2E 1.31|(Solution 1.31)]] | ||

− | + | <br>1-32. | |

How much does the ice in a hockey rink weigh? | How much does the ice in a hockey rink weigh? | ||

− | + | <br>1-33. | |

How many miles of road are there in the United States? | How many miles of road are there in the United States? | ||

[[TADM2E 1.33|(Solution 1.33)]] | [[TADM2E 1.33|(Solution 1.33)]] | ||

− | + | <br>1-34. | |

On average, how many times would you have to flip open the | On average, how many times would you have to flip open the | ||

Manhattan phone book at random in order to find a specific name? | Manhattan phone book at random in order to find a specific name? |

## Revision as of 18:22, 11 September 2014

# Introduction to Algorithm Design

**Finding Counterexamples**

1-1.
Show that $ a + b $ can be less than $ \min(a,b) $.

1-2.
Show that $ a \times b $ can be less than $ \min(a,b) $.

1-3.
Design/draw a road network with two points $ a $ and $ b $ such that the
fastest route between $ a $ and $ b $ is not the shortest route.

1-4.
Design/draw a road network with two points $ a $ and $ b $ such that the
shortest route between $ a $ and $ b $ is not the route with the fewest turns.

1-5.
The *knapsack problem*
is as follows: given a set of integers $ S = \{s_1, s_2, \ldots, s_n\} $, and
a target number $ T $, find a subset of $ S $ which adds up
exactly to $ T $.
For example, there exists a subset within $ S = \{1, 2, 5, 9, 10\} $ that
adds up to $ T=22 $ but not $ T=23 $.
Find counterexamples to each of the following algorithms for the knapsack
problem.
That is, giving an $ S $ and $ 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 $ S $ in the knapsack in left to right order if they fit, i.e. the first-fit algorithm.
- Put the elements of $ S $ in the knapsack from smallest to largest, i.e. the best-fit algorithm.
- Put the elements of $ S $ in the knapsack from largest to smallest.

1-6.
The *set cover problem*
is as follows: given a set of subsets $ S_1, ..., S_m $
of the universal set $ U = \{1,...,n\} $,
find the smallest subset of subsets $ T \subset S $
such that $ \cup_{t_i \in T} t_i = U $.
For example, there are the following subsets, $ S_1 = \{1, 3, 5\} $,
$ S_2 = \{2,4\} $, $ S_3 = \{1,4\} $, and $ S_4 = \{2,5\} $
The set cover would then be $ S_1 $ and $ 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.

**Proofs of Correctness**

1-7.
Prove the correctness of the following recursive algorithm
to multiply two natural numbers, for all
integer constants $ c \geq 2 $.

functionmultiply($ y,z $)commentReturn the product $ yz $. 1.if$ z=0 $thenreturn(0)else2. return(multiply($ cy,\lfloor z/c \rfloor)+y \cdot (z\,\bmod\,c $))

1-8.
Prove the correctness of the following algorithm for evaluating a
polynomial. P(x) = $ a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 $

functionhorner($ A,x $) $ p = A_n $ for $ i $ from $ n-1 $ to $ 0 $ $ p = p*x+A_i $ return $ p $

1-9.
Prove the correctness of the following sorting algorithm.

functionbubblesort ($ A $ : list[$ 1 \dots n $]) var int $ i, j $ for $ i $ from $ n $ to $ 1 $ for $ j $ from $ 1 $ to $ i-1 $ if ($ A[j] > A[j+1] $) swap the values of $ A[j] $ and $ A[j+1] $

**Induction**

1-10.
Prove that $ \sum_{i=1}^n i $=$ n(n+1)/2 $ for $ n \geq 0 $,
by induction.

1-11.
Prove that
$ \sum_{i=1}^n i^2 $=$ n(n+1)(2n+1)/6 $ for $ n \geq\ 0 $,
by induction.

1-12.
Prove
that $ \sum_{i=1}^n i^3 $=$ n^2(n+1)^2/4 $
for $ n \geq 0 $,
by induction.

1-13.
Prove that
$ \sum_{i=1}^n i(i+1)(i+2)=n(n+1)(n+2)(n+3)/4 $

1-14.
Prove by induction on $ n \geq 1 $ that for every $ a \neq 1 $,
$ \sum_{i=0}^n a^i =\frac{a^{n+1}-1}{a-1} $
}

1-15.
Prove by induction that for $ n \geq 1 $,
$ \sum_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1} $

1-16.
Prove by induction that $ n^3+2n $ is divisible by $ 3 $ for all $ n \geq 0 $.
}{

1-17.
Prove by induction that a tree with $ n $ vertices has exactly $ n-1 $ edges.

1-18.
Prove by mathematical induction that the sum of the cubes of the first $ n $
positive integers is equal to the square of the sum of these integers, i.e.
$ \sum_{i=1}^n i^3 = ( \sum_{i=1}^n i )^2 $

**Estimation**

1-19.
Do all the books you own total at least one million pages?
How many total pages are stored in your school library?
Schaffer, chapter 2 problem 2.21

1-20.
How many words are there in this textbook?

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

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

1-23.
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-24.
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-25.
A sorting algorithm takes 1 second to sort 1,000 items on your local
machine.
How long will it take to sort 10,000 items ...

- if you believe that the algorithm takes time proportional to $ n^2 $, and
- if you believe that the algorithm takes time roughly proportional to $ n\log n $?

**Implementation Projects**

1-26.
Implement the two TSP heuristics of **tsp-robot**.
Which of them gives better-quality solutions in practice?
Can you devise a heuristic that works better than both of them?

1-27.
Describe how to test whether a given set of tickets establishes
sufficient coverage in the Lotto problem
of **lotto**.
Write a program to find good ticket sets.

**Interview Problems**

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

1-29.
There are 25 horses. At most, 5 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-30.
How many piano tuners are there in the entire world?

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

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

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

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