CPSC 110 Fall 2011 Quiz 4

  1. Match the following function names to their mathematical expressions:

    1. exponential

    2. linear

    3. logarithmic

    4. quadratic
    		    

    1. y = x

    2. y = x2

    3. y = 2x

    4. y = log2 x
    		    Solution
    exponential: y = 2x
    linear: y = x
    logarithmic: y = log2 x
    quadratic: y = x2

  2. Arrange the following functions in order from low to high in terms of how fast they grow as N increases:



    logarithmic   << linear    << quadratic    << exponential

  3. Can the following problem be solved by a linear algorithm? Explain why or why not.
    Double the value of each number in a list of N numbers. So if the list consisted initially of (1 2 3 4 5 6 7 8), it would consist of (2 4 6 8 10 12 14 16) after the algorithm completed.

    Yes. You need to pass through the list of N numbers exactly once, doubling each number. This takes approximately N operations. If you double the number of numbers to 2N, you will double the number of operations. So this is linear growth.

  4. Can the problem in the previous question be solved by a logarithmic algorithm? Explain why or why not?

    No because you need to double each of the N numbers. So you have to pass through the list exactly once and process each number. Compare this to binary search where you only need to look at a logarithmic number of numbers to guess a number between 1 and N. So the most efficient way to solve this is with a linear algorithm.

     

  5. Suppose you own a patio construction company. And you have to estimate how long in hours its going to take to build a square patio that is 16 feet by 16 feet with square tiles that are each 1 foot square. You know that on average it takes your crew 10 hours to complete a standard 8 foot by 8 foot patio. What should your estimate be for the 16 × 16 patio? Which one of our 4 types of algorithms (functions) does this problem resemble?

    I should have specified here that N is the length of the side of the patio. In that case doubling the side (from 8 to 16) requires 4 times as much time (22). Doubling the side of the patio makes the patio 4 times larger in square feet. So this is quadratic. However, if you take N to be the number of tiles (8 × 8 = 64). Then to do a 16 × 16 patio, you are increasing the number of tiles by 4 and increasing the amount of time by 4. So you could say it was linear in that sense. Either answer is acceptable.

  6. What does it mean to say that the Traveling Salesman problem is intractable?

    The TSP is intractable because for N cities it would require an exponential number of operations (N! >> 2N) to perform a brute force search for the best possible path. It is practically impossible to solve this by brute force for large N. For problems such as this we can sometimes use a heuristic solution -- e.g., the nearest neighbor heuristic -- which gives pretty good solutions and sometimes even the optimal solution, although they are not guaranteed to give the optimal solution.