Difference between pages "Chapter 1" and "2.9"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
(Created page with "=2-8.= For each of the following pairs of functions, either <math>f(n)</math> is in <math>O(g(n))</math>, <math>f(n)</math> is in <math>\Omega(g(n))</math>, or <math>f(n)=\Th...")
 
Line 1: Line 1:
Problems
+
=2-8.=
  
 +
For each of the following pairs of functions, either <math>f(n)</math> is in <math>O(g(n))</math>, <math>f(n)</math> is in <math>\Omega(g(n))</math>, or <math>f(n)=\Theta(g(n))</math>. Determine which relationship is correct and briefly explain why.
  
:[[1.1]]. Show that ''a'' + ''b'' can be less than ''min(a, b)''.
 
  
 +
==<math>f(n)=\log n^2</math>; <math>g(n)=\log n</math> + <math>5</math>==
 +
Answer: <math>\log n^2 = \Theta (\log n + 5)</math>
  
:1.2. Show that ''a'' × ''b'' can be less than ''min(a, b)''.
 
  
 +
Solution:
  
:[[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.
+
<math>\log n^2 = 2 \times \log n</math>
  
 +
<math>2 \times \log n \le 2 \times \log n + 10</math>
  
: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.
+
<math>\log n^2 \le 2 (\log n + 5)</math>
  
 +
<math>\log n^2 \le C (\log n + 5)</math> (where <math>C=2</math>)
  
:[[1.5]]. The ''knapsack problem'' is as follows: given a set of integers ''S'' = {''s1, s2. . . , sn''}, and a target number ''T'', find a subset of ''S'' that 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.
+
<math>\log n^2 = O (\log n + 5)</math>
  
:Find counterexamples to each of the following algorithms for the knapsack problem. That is, give an ''S'' and ''T'' where the algorithm does not find a solution that leaves the knapsack completely full, even though a full-knapsack solution exists.
+
Also:
  
::(a) Put the elements of ''S'' in the knapsack in left to right order if they fit, that is, the first-fit algorithm.
+
<math>\log n + 5 \le \log n + 5 \log n</math>
  
::(b) Put the elements of ''S'' in the knapsack from smallest to largest, that is, the best-fit algorithm.
+
<math>\log n + 5 \le 6 \log n</math>
  
::(c) Put the elements of ''S'' in the knapsack from largest to smallest.
+
<math>\log n + 5 \le 3 \times 2 \log n</math>
  
 +
<math>3 \times \log n^2 \ge \log n + 5 </math>
  
:1.6. The ''set cover problem'' is as follows: given a set ''S'' of subsets ''S1, . . . , Sm'' of the universal set ''U'' = {1, ..., ''n''}, find the smallest subset of subsets ''T ⊆ S'' such that ''∪ti∈T ti'' = ''U''. For example, consider the subsets ''S1'' = {1, 3, 5}, ''S2'' = {2, 4}, ''S3'' = {1, 4}, and ''S4'' = {2, 5}. The set cover of {1, . . . , 5} would then be ''S1'' and ''S2''.
+
<math>\log n^2 \ge C \times (\log n + 5)</math> (Where <math>C =\frac{1}{3}</math>)
: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.
 
  
 +
<math>log n^2 = \Omega (\log n + 5)</math>
  
:[[1.7]]. The ''maximum clique problem'' in a graph ''G'' = (''V'', ''E'') asks for the largest subset ''C'' of vertices ''V'' such that there is an edge in ''E'' between every pair of vertices in ''C''. Find a counterexample for the following algorithm: Sort the vertices of ''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.
+
And therefore:
  
 +
<math>log n^2 = \Theta (\log n + 5)</math>
  
:1.8. Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants c ≥ 2.
 
::Multiply(''y, z'')
 
:::''if z'' = 0 ''then'' return(0) ''else''
 
:::return(Multiply(''cy'', [''z/c'']) + ''y'' · (''z'' mod ''c''))
 
  
 +
==<math>f(n)=\sqrt{n}</math>; <math>g(n)=\log(n^2)</math>==
  
:[[1.9]]. Prove the correctness of the following algorithm for evaluating a polynomial
+
Answer: <math>f(n) = \Omega(g(n))</math>
''anxn + an−1xn−1 + · · · + a1x + a0''.
 
::Horner(''a, x'')
 
:::'p'' = ''an''
 
:::for ''i'' from ''n'' − 1 to 0
 
::::''p'' = ''p · x'' + ''ai''
 
:::return ''p''
 
  
  
:1.10
+
Solution:
  
:[[1.11]]
+
<math>g(n) = \log (n^2) = 2 * \log (n)</math>
  
:1.12
+
<math>\lim_{n \to \infty} \frac{\sqrt{n}}{2 * log(n)} = 2 * \lim_{n \to \infty} \frac{\sqrt{n}}{log(n)} = \infty</math>
  
:[[1.13]]
 
  
:1.14
+
==<math>f(n)=\log^2(n)</math>; <math>g(n)=\log (n)</math>==
  
:[[1.15]]
+
Answer: <math>f(n) = \Omega(g(n))</math>
  
:1.16
 
  
:[[1.17]]
+
Solution:
  
:1.18
+
<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>
  
:[[1.19]]
 
  
:1.20
+
==<math>f(n)=n</math>; <math>g(n)=\log^2(n)</math>==
  
:[[1.21]]
+
Answer: <math>f(n) = \Omega(g(n))</math>
  
:1.22
 
  
:[[1.23]]
+
Solution:
  
:1.24
+
<math>\lim_{n \to \infty} \frac{n}{\log^2(n)} = \lim_{n \to \infty} ((\frac{\sqrt{n}}{\log(n)})^2) = (\lim_{n \to \infty} \frac{\sqrt{n}}{\log(n)})^2 = \infty</math>
  
:[[1.25]]
 
  
:1.26
+
==<math>f(n)=n * \log(n) + n</math>; <math>g(n)=\log (n)</math>==
  
:[[1.27]]
+
Answer: <math>f(n) = \Omega(g(n))</math>
  
:1.28
 
  
:[[1.29]]
+
Solution:
  
:1.30
+
<math>\lim_{n \to \infty} \frac{n * \log(n) + n}{log(n)} = \lim_{n \to \infty} (\frac{n * \log(n)}{log(n)} + \frac{n}{log(n)}) = \lim_{n \to \infty} (n + \frac{n}{log(n)}) = \infty</math>
  
:[[1.31]]
 
  
:1.32
+
==<math>f(n)=10</math>; <math>g(n)=\log (10)</math>==
  
:[[1.33]]
+
Answer: <math>f(n) = \Theta(g(n))</math>
  
:1.34
 
  
:[[1.35]]
+
Solution: Both are constants. Constants are always within a constant factor, <math>c</math>, of each other (as <math>n \rightarrow \infty</math>).
  
:1.36
 
  
:[[1.37]]
+
==<math>f(n)=2^n</math>; <math>g(n)=10n^2</math>==
  
:1.38
+
Answer: <math>f(n) = \Omega(g(n))</math>
  
  
 +
Solution:
  
Back to [[Chapter List]]
+
<math>
 +
\begin{align}
 +
&\lim_{n \to \infty} \frac{2^n}{10n^2} \\
 +
&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2^n}{n^2}\right) \\
 +
&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{\ln(2)\cdot 2^n}{2 \cdot n}\right) \text{L'Hopital's Rule} \\
 +
&\implies  \frac{1}{10} \left(\lim_{n \to \infty} \frac{2\ln(2)\cdot 2^n}{2}\right) \text{L'Hopital's Rule} \\
 +
&\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n \\
 +
&\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n = \infty
 +
\end{align}
 +
</math>
 +
 
 +
==<math>f(n)=2^n</math>; <math>g(n)=3^n</math>==
 +
 
 +
Answer: <math>f(n) = O(g(n))</math>
 +
 
 +
 
 +
Solution:
 +
 
 +
<math>\lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} (\frac{2}{3})^n = 0</math>
 +
 
 +
 
 +
Back to [[Chapter 2]]

Revision as of 18:53, 9 September 2020

2-8.

For each of the following pairs of functions, either [math]\displaystyle{ f(n) }[/math] is in [math]\displaystyle{ O(g(n)) }[/math], [math]\displaystyle{ f(n) }[/math] is in [math]\displaystyle{ \Omega(g(n)) }[/math], or [math]\displaystyle{ f(n)=\Theta(g(n)) }[/math]. Determine which relationship is correct and briefly explain why.


[math]\displaystyle{ f(n)=\log n^2 }[/math]; [math]\displaystyle{ g(n)=\log n }[/math] + [math]\displaystyle{ 5 }[/math]

Answer: [math]\displaystyle{ \log n^2 = \Theta (\log n + 5) }[/math]


Solution:

[math]\displaystyle{ \log n^2 = 2 \times \log n }[/math]

[math]\displaystyle{ 2 \times \log n \le 2 \times \log n + 10 }[/math]

[math]\displaystyle{ \log n^2 \le 2 (\log n + 5) }[/math]

[math]\displaystyle{ \log n^2 \le C (\log n + 5) }[/math] (where [math]\displaystyle{ C=2 }[/math])

[math]\displaystyle{ \log n^2 = O (\log n + 5) }[/math]

Also:

[math]\displaystyle{ \log n + 5 \le \log n + 5 \log n }[/math]

[math]\displaystyle{ \log n + 5 \le 6 \log n }[/math]

[math]\displaystyle{ \log n + 5 \le 3 \times 2 \log n }[/math]

[math]\displaystyle{ 3 \times \log n^2 \ge \log n + 5 }[/math]

[math]\displaystyle{ \log n^2 \ge C \times (\log n + 5) }[/math] (Where [math]\displaystyle{ C =\frac{1}{3} }[/math])

[math]\displaystyle{ log n^2 = \Omega (\log n + 5) }[/math]

And therefore:

[math]\displaystyle{ log n^2 = \Theta (\log n + 5) }[/math]


[math]\displaystyle{ f(n)=\sqrt{n} }[/math]; [math]\displaystyle{ g(n)=\log(n^2) }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]


Solution:

[math]\displaystyle{ g(n) = \log (n^2) = 2 * \log (n) }[/math]

[math]\displaystyle{ \lim_{n \to \infty} \frac{\sqrt{n}}{2 * log(n)} = 2 * \lim_{n \to \infty} \frac{\sqrt{n}}{log(n)} = \infty }[/math]


[math]\displaystyle{ f(n)=\log^2(n) }[/math]; [math]\displaystyle{ g(n)=\log (n) }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]


Solution:

[math]\displaystyle{ \lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty }[/math]


[math]\displaystyle{ f(n)=n }[/math]; [math]\displaystyle{ g(n)=\log^2(n) }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]


Solution:

[math]\displaystyle{ \lim_{n \to \infty} \frac{n}{\log^2(n)} = \lim_{n \to \infty} ((\frac{\sqrt{n}}{\log(n)})^2) = (\lim_{n \to \infty} \frac{\sqrt{n}}{\log(n)})^2 = \infty }[/math]


[math]\displaystyle{ f(n)=n * \log(n) + n }[/math]; [math]\displaystyle{ g(n)=\log (n) }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]


Solution:

[math]\displaystyle{ \lim_{n \to \infty} \frac{n * \log(n) + n}{log(n)} = \lim_{n \to \infty} (\frac{n * \log(n)}{log(n)} + \frac{n}{log(n)}) = \lim_{n \to \infty} (n + \frac{n}{log(n)}) = \infty }[/math]


[math]\displaystyle{ f(n)=10 }[/math]; [math]\displaystyle{ g(n)=\log (10) }[/math]

Answer: [math]\displaystyle{ f(n) = \Theta(g(n)) }[/math]


Solution: Both are constants. Constants are always within a constant factor, [math]\displaystyle{ c }[/math], of each other (as [math]\displaystyle{ n \rightarrow \infty }[/math]).


[math]\displaystyle{ f(n)=2^n }[/math]; [math]\displaystyle{ g(n)=10n^2 }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]


Solution:

[math]\displaystyle{ \begin{align} &\lim_{n \to \infty} \frac{2^n}{10n^2} \\ &\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2^n}{n^2}\right) \\ &\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{\ln(2)\cdot 2^n}{2 \cdot n}\right) \text{L'Hopital's Rule} \\ &\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2\ln(2)\cdot 2^n}{2}\right) \text{L'Hopital's Rule} \\ &\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n \\ &\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n = \infty \end{align} }[/math]

[math]\displaystyle{ f(n)=2^n }[/math]; [math]\displaystyle{ g(n)=3^n }[/math]

Answer: [math]\displaystyle{ f(n) = O(g(n)) }[/math]


Solution:

[math]\displaystyle{ \lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} (\frac{2}{3})^n = 0 }[/math]


Back to Chapter 2