|
|
| Line 1: |
Line 1: |
| − | Problems
| + | (1) Do a binary search within the range of <math>1-n</math>. You guess the right number within O(log n) questions. |
| | | | |
| − | :[[1.1]]. Show that <math>a + b</math> can be less than <math>\min(a,b)</math>.
| + | (2) If you don't know n start with a random number <math>2^i</math> and if it is larger than the number you are looking for do a binary search within <math>1-2^i</math> as in (1). If <math>2^i</math> is less then guess <math>2^{i+1}</math> and repeat. |
| | | | |
| | | | |
| − | :1.2. Show that <math>a \times b</math> can be less than <math>\min(a,b)</math>.
| + | Back to [[Chapter 5]] |
| − | | |
| − | | |
| − | :[[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.4. Design/draw a road network with two points <math>a</math> and <math>b</math> such that the
| |
| − | shortest route between <math>a</math> and <math>b</math> is not the route with the fewest turns.
| |
| − | | |
| − | | |
| − | :[[1.5]].The ''knapsack problem''
| |
| − | is as follows: given a set of integers <math>S = \{s_1, s_2, \ldots, s_n\}</math>, and
| |
| − | a target number <math>T</math>, find a subset of <math>S</math> which adds up
| |
| − | exactly to <math>T</math>.
| |
| − | For example, there exists a subset within <math>S = \{1, 2, 5, 9, 10\}</math> that
| |
| − | adds up to <math>T=22</math> but not <math>T=23</math>.
| |
| − | Find counterexamples to each of the following algorithms for the knapsack
| |
| − | problem.
| |
| − | 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,
| |
| − | even though such a solution exists.
| |
| − | #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 <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.
| |
| − | | |
| − | | |
| − | :1.6. The ''set cover problem''
| |
| − | is as follows: given a set of subsets <math> S_1, ..., S_m</math>
| |
| − | of the universal set <math>U = \{1,...,n\}</math>,
| |
| − | find the smallest subset of subsets <math>T \subset S</math>
| |
| − | such that <math>\cup_{t_i \in T} t_i = U</math>.
| |
| − | 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 <math>S_1</math> and <math>S_2</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.
| |
| − | | |
| − | | |
| − | :[[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.
| |
| − | | |
| − | | |
| − | :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''))
| |
| − | | |
| − | | |
| − | :[[1.9]]. Prove the correctness of the following algorithm for evaluating a polynomial ''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
| |
| − | | |
| − | :[[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 [[Chapter List]] | |
