# Difference between revisions of "Chapter 1"

Jump to navigation
Jump to search

Line 1: | Line 1: | ||

Problems | 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]] | 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.

- (a) Put the elements of

- (b) Put the elements of
*S*in the knapsack from smallest to largest, that is, the best-fit algorithm.

- (b) Put the elements of

- (c) Put the elements of
*S*in the knapsack from largest to smallest.

- (c) Put the elements of

- 1.6

- 1.8

- 1.10

- 1.12

- 1.14

- 1.16

- 1.18

- 1.20

- 1.22

- 1.24

- 1.26

- 1.28

- 1.30

- 1.32

- 1.34

- 1.36

- 1.38

Back to Problem Solutions