Practice Problems for Chapters 7 & 10

  1. Kruskal's algorithm for solving the Minimum Spanning Tree Problem is
    1. an optimal and efficient algorithm
    2. an optimal and inefficient algorithm
    3. an approximate and efficient algorithm
    4. an approximate and inefficient algorithm
    5. None of these

  2. Which of the following algorithm(s) is(are) optimal and efficient?

    1. Cheapest Link algorithm for solving the TSP
    2. The brute force algorithm for solving the TSP
    3. Prim's algorithm for solving the MST problem
    4. a and c
    5. None of the above

  3. Which of the following are true of a tree?

    1. any graph that is connected and has bridges
    2. any graph that is connected and has no bridges
    3. any graph that is connected and has no circuits
    4. any graph that has no circuits
    5. None of the above

  4. If a tree has 98 edges, then the number of its vertices is:

    1. 97
    2. 99
    3. 100
    4. 98
    5. None of these

  5. Suppose a tree T has 9 vertices, then

    1. it has one bridge
    2. it can have any number of bridges
    3. it has 9 bridges
    4. it has no bridges
    5. None of the above

  6. Prim's algorithm applied to in Figure 1, starting at C yields the following sequence of edges:

    1. CD, CB, CA
    2. CD, CA, CB
    3. CA, CD, CB
    4. CA, CB, CD
    5. None of the above

  7. How many spanning trees does the graph below has?:


    8. Figure 1
    1. 6
    2. 8
    3. 10
    4. 4
    5. None of these

  8. For finding minimum spanning trees, Kruskal's algorithm is:

    1. efficient
    2. exact
    3. greedy
    4. a & b
    5. a & c
    6. b & c
    7. all of the above
    8. none of the above

  9. Every graph with N vertices and N - 1 edges is a tree.

    1. True
    2. False

  10. Use Kruskal's algorithm to find a minimum spanning tree of the given graph below. Draw the resulting spanning tree and list the edges in the order they are picked by Kruskal's algorithm.


    Figure 2

     

  11. Use Prim's algorithm, starting at H, to find a minimum spanning tree of the graph given above (Figure 2). Draw the resulting spanning tree and list the edges in the order they are picked by Prim's algorithm.

     

     

     

     

     

  12. What is(are) the major difference(s) between the TSP (travelling salesman Problem) and the MST (minimum spanning tree problems). Make sure to discuss the differences between the algorithms that solve or attempt to solve these two types of problems.

     

     

     

     

     

     

  13. What is the length of the network shown in Figure 3(a)? Note: sqrt stands for "square root of"

    1. 300 + 200 sqrt(2)
    2. 200 + 300 sqrt(3)
    3. 300 + 200 sqrt(3)
    4. 200 + 300 sqrt(2)
    5. None of these

  14. What is the length of the minimum spanning network for the graph shown in Figure 3(b)?

     

     

     

     

     

     

  15. If the Nth Fibonacci number is 46, 368 and the (N+2)th Fibonacci number is 121, 393, what is the (N + 4)th Fibonacci number?

    1. 167, 761
    2. 289,154
    3. 75,025
    4. 317,811
    5. None of these

  16. A trash dumb grows by 31 tons of trash every month. Let PN represent the number of tons of trash at the end of the Nth month. Assuming the dump starts out with 500 tons, find P24.

    1. 1213
    2. 1182
    3. 1244
    4. 744
    5. None of these

  17. Consider a population that grows according to the linear growth model. The starting population is P1 = 11, and the population in the twelfth generation is P12 = 77. What is P37?

    1. 216
    2. 227
    3. 191
    4. 847
    5. None of these

  18. The sum of the first 30 terms of the sequence 3 + 8 + 13 + 18 + …

    1. 4530
    2. 148
    3. 2265
    4. 1480
    5. None of these

  19. An amount of 1000 is deposited in a savings account that pays 8% interest compounded monthly. Assuming no deposits or withdrawals are made, how much money will be in the account after 5 years?:

    1. $101,257.06
    2. $1033.78
    3. $5400.00
    4. $1489.85
    5. None of these

  20. Consider the geometric sequence with the first five terms 4, 12, 36, 108, 432, ; what is the sum of the first 13 terms?

    1. 28,697,812
    2. 318, 8644
    3. 13,817,492
    4. 2,125,764
    5. None of the above

  21. Consider the logistic model given by PN+1 = r(1 - PN)PN. If the growth rate is 3.0 and P1 is 0.15 find P4.

    1. 0.3825
    2. 0.7086
    3. 0.6195
    4. 0.7072
    5. None of the above

  22. A population of guinea pigs grows according to the following transition rule: PN = 2PN-1 + PN-2. The starting population is P1 = 3 and the population in the second generation is P2 = 5. Find P4.

    1. 13
    2. 11
    3. 31
    4. 23
    5. None of the above

  23. Monthly payments on a $100,000 loan at 12% annual interest amortized over 20 years will be close to? (Hint: use the formula p = [B*I(1 + I)N]/[(1 + I)N -1]. Note that B stands for the money borrowed, I for the periodic interest rate, that is I = 1%, N for the number of payments, and p for the monthly payment.

    1. $1201.09
    2. $1101.09
    3. $1001.09
    4. $1301.09
    5. None of the above

  24. In problem # 23, what is the total amount of money paid in interests at the end of the 20 years?

    1. $164,260.67
    2. $188,261.60
    3. $140,000
    4. $140,261.60
    5. None of the above

  25. A population grows according to the linear growth model. The starting population is P1 = 10 and the population grows at a rate of 7 per year.

    1. Find the population at year 20

      2.  

       

       

       

    2. Find the sum of the population at year 20

       

       

       

       

  26. Discuss the differences between linear, exponential and logistic growth models and give typical situation where each might be used.

     

     

     

     

If you want to look at the solutions Click Here