Difference between revisions of "Chapter 1"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 1: Line 1:
 
Problems
 
Problems
  
*[[1.1]]
+
:[[1.1]]. Show that ''a'' + ''b'' can be less than ''min(a, b)''.
  
*[[1.2]]
 
  
*[[1.3]]
+
:1.2. Show that ''a'' × ''b'' can be less than ''min(a, b)''.
  
*[[1.4]]
 
  
*[[1.5]]
+
:[[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.6]]
 
  
*[[1.7]]
+
: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.8]]
 
  
*[[1.9]]
+
:[[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.
  
*[[1.10]]
+
: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.
  
*[[1.11]]
+
::(a) Put the elements of ''S'' in the knapsack in left to right order if they fit, that is, the first-fit algorithm.
  
*[[1.12]]
+
::(b) Put the elements of ''S'' in the knapsack from smallest to largest, that is, the best-fit algorithm.
  
*[[1.13]]
+
::(c) Put the elements of ''S'' in the knapsack from largest to smallest.
  
*[[1.14]]
 
  
*[[1.15]]
+
:1.6
  
*[[1.16]]
+
:[[1.7]]
  
*[[1.17]]
+
:1.8
  
*[[1.18]]
+
:[[1.9]]
  
*[[1.19]]
+
:1.10
  
*[[1.20]]
+
:[[1.11]]
  
*[[1.21]]
+
:1.12
  
*[[1.22]]
+
:[[1.13]]
  
*[[1.23]]
+
:1.14
  
*[[1.24]]
+
:[[1.15]]
  
*[[1.25]]
+
:1.16
  
*[[1.26]]
+
:[[1.17]]
  
*[[1.27]]
+
:1.18
  
*[[1.28]]
+
:[[1.19]]
  
*[[1.29]]
+
:1.20
  
*[[1.30]]
+
:[[1.21]]
  
*[[1.31]]
+
:1.22
  
*[[1.32]]
+
:[[1.23]]
  
*[[1.33]]
+
:1.24
  
*[[1.34]]
+
:[[1.25]]
  
*[[1.35]]
+
:1.26
  
*[[1.36]]
+
:[[1.27]]
  
*[[1.37]]
+
:1.28
  
*[[1.38]]
+
:[[1.29]]
 +
 
 +
:1.30
 +
 
 +
:[[1.31]]
 +
 
 +
:1.32
 +
 
 +
:[[1.33]]
 +
 
 +
:1.34
 +
 
 +
:[[1.35]]
 +
 
 +
:1.36
 +
 
 +
:[[1.37]]
 +
 
 +
:1.38
  
  
  
 
Back to [[Problem Solutions]]
 
Back to [[Problem Solutions]]

Revision as of 19:20, 23 August 2020

Problems

1.1. Show that a + b can be less than min(a, b).


1.2. Show that a × 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 = {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.
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.
(a) Put the elements of S in the knapsack in left to right order if they fit, that is, the first-fit algorithm.
(b) Put the elements of S in the knapsack from smallest to largest, that is, the best-fit algorithm.
(c) Put the elements of S in the knapsack from largest to smallest.


1.6
1.7
1.8
1.9
1.10
1.11
1.12
1.13
1.14
1.15
1.16
1.17
1.18
1.19
1.20
1.21
1.22
1.23
1.24
1.25
1.26
1.27
1.28
1.29
1.30
1.31
1.32
1.33
1.34
1.35
1.36
1.37
1.38


Back to Problem Solutions