Data Structures and Algorithms with Object-Oriented Design Patterns in Python
next up previous index

Exercises

  1. Consider the function tex2html_wrap_inline60231. Using Definition gif show that tex2html_wrap_inline58535.
  2. Consider the function tex2html_wrap_inline60231. Using Definition gif show that tex2html_wrap_inline59395.
  3. Consider the functions tex2html_wrap_inline60231 and tex2html_wrap_inline60241. Using Theorem gif show that tex2html_wrap_inline60243.
  4. Consider the functions tex2html_wrap_inline60245 and tex2html_wrap_inline60247. Using Theorem gif show that tex2html_wrap_inline60249.
  5. For each pair of functions, f(n) and g(n), in the following table, indicate if f(n)=O(g(n)) and if g(n)=O(f(n)).

    f(n) g(n)
    10n tex2html_wrap_inline60265
    tex2html_wrap_inline60267 tex2html_wrap_inline60269
    tex2html_wrap_inline60271 tex2html_wrap_inline60273
    tex2html_wrap_inline59015 tex2html_wrap_inline60277
    tex2html_wrap_inline57989 tex2html_wrap_inline59015
    tex2html_wrap_inline60283 tex2html_wrap_inline59015
    tex2html_wrap_inline60287 tex2html_wrap_inline59015
    tex2html_wrap_inline60291 tex2html_wrap_inline60293
    tex2html_wrap_inline59477 tex2html_wrap_inline60297
    tex2html_wrap_inline60299 tex2html_wrap_inline60301
    tex2html_wrap_inline60303 tex2html_wrap_inline60305

  6.   Show that the Fibonacci numbers (see Equation gif) satisfy the identities

    gather2420

    for tex2html_wrap_inline58983.

  7. Prove each of the following formulas:
    1. tex2html_wrap_inline60309
    2. tex2html_wrap_inline60311
    3. tex2html_wrap_inline60313
  8. Show that tex2html_wrap_inline60315, where tex2html_wrap_inline58403 and tex2html_wrap_inline58503.
  9. Show that tex2html_wrap_inline60321.
  10. Solve each of the following recurrences:
    1. tex2html_wrap_inline60323
    2. tex2html_wrap_inline60325
    3. tex2html_wrap_inline60327
    4. tex2html_wrap_inline60329
  11. Derive tight, big oh expressions for the running times of example-a,example-b,example-c,example-d,example-f,example-g,example-h,example-i.
  12. Consider the Python program fragments given below. Assume that n, m, and k are non-negative integers and that the methods e, f, g, and h have the following characteristics: Determine a tight, big oh expression for the worst-case running time of each of the following program fragments: 
    1. f(n, 10, 0);
g(n, m, k);
h(n, m, 1000000);
    2. for i in range(n):
    f(n, m, k);
    3. for i in range (e(n, 10, 100)):
    f(n, 10, 0);
    4. for i in range (e(n, m, k)):
    f(n, 10, 0);
    5. for i in range(n):
    for j in range(i, n):
        f(n, m, k);
      
	
  13.   
	Consider the following Python program fragment.
	What value does f compute?
	(Express your answer as a function of n).
	Give a tight, big oh expression for the worst-case
	running time of the method f.

    def f(n):
    sum = 0
    for i in range(1, n + 1):
	sum = sum + i
    return sum
  14.   
	Consider the following Python program fragment.
	(The method f is given in Exercise gif).
	What value does g compute?
	(Express your answer as a function of n).
	Give a tight, big oh expression for the worst-case
	running time of the method g.

    def g(n):
    sum = 0
    for i in range(1, n + 1):
	sum = sum + i + f(i)
    return sum
  15. 
	Consider the following Python program fragment.
	(The method f is given in Exercise gif
	and the method g is given in Exercise gif).
	What value does h compute?
	(Express your answer as a function of n).
	Give a tight, big oh expression for the worst-case
	running time of the method h.

    def h(n):
    return f(n) + g(n)
    

next up previous  index 

Bruno
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng.  All rights reserved.