Chapter 2
■
the BasiCs
40
2-6. Show that any polynomial (that is,
Q(
n
k
), for any constant
k > 0) asymptotically dominates any
logarithm (that is,
Q(
lg n)). (Note that the polynomials here include, for example, the square root,
for
k = 0.5.)
2-7. Research or conjecture the asymptotic complexity of various operations on Python lists, such as
indexing,
item assignment, reversing, appending, and inserting (the latter two discussed in the “Black
Box” sidebar on
list). How would these be different in a linked list implementation? What about,
for example,
list.extend?
2-8. Show that the expressions
Q(
f)
+
Q(
g) =
Q(
f +
g) and
Q(
f)
· Q(
g) =
Q(
f ·
g) are correct. Also, try your
hand at max(Q(
f),
Q(
g))
=
Q(max(
f, g)) =
Q(
f +
g).
2-9. In Appendix C, you’ll find a numbered list of statements about trees. Show that they are equivalent.
2-10. Let
T be an arbitrary rooted tree with at least three nodes, where each
internal node has exactly
two children. If
T has
n leaves, how many internal nodes does it have?
2-11. Show that a directed acyclic graph (DAG) can have any underlying structure whatsoever. Put
differently, any undirected graph can be the underlying graph for a DAG, or, given a graph, you can
always orient its edges so that the resulting digraph is a DAG.
2-12. Consider the following graph representation: You use a dictionary and let each key be a pair
(tuple) of two nodes, with the corresponding value set to the edge weight. For example W[u, v] = 42.
What would be the advantages and disadvantages of this representation? Could you supplement it to
mitigate the downsides?
References
Acton, F. S. (2005).
Real Computing Made Real: Preventing Errors in Scientific and Engineering Calculations.
Dover
Publications, Inc.
Bang-Jensen, J. and Gutin, G. (2002).
Digraphs: Theory, Algorithms and Applications. Springer.
Bast, H. and Weber, I. (2005). Don’t compare averages. In Nikoletseas, S. E., editor, WEA, volume 3503 of Lecture Notes
in Computer Science, pages 67–76. Springer.
Bondy, J. A. and Murty, U. S. R. (2008).
Graph Theory. Springer.
Brandstädt, A., Le, V. B., and Spinrad, J. P. (1999). Graph Classes: A Survey.
SIAM Monographs on Discrete
Mathematics and Applications. Society for Industrial and Applied Mathematics.
Citron, D., Hurani, A., and Gnadrey, A. (2006). The harmonic or geometric mean: Does it really matter?
ACM SIGARCH Computer Architecture News, 34(4):18–25.
Diestel, R. (2005).
Graph Theory, third edition. Springer.
Fleming, P. J. and Wallace, J. J. (1986). How not to lie with statistics: The correct way to summarize benchmark results.
Commun. ACM, 29(3):218–221.
Goldberg, D. (1991). What every computer scientist should know about floating-point arithmetic.
ACM Computing
Surveys (CSUR), 23(1):5–48.
http://docs.sun.com/source/806-3568/ncg_goldberg.html
.
Hromkovicˇ, J. (2009).
Algorithmic Adventures: From Knowledge to Magic. Springer.
Knuth, D. E. (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News, 8(2):18–24.
Lewis, H. R. and Papadimitriou, C. H. (1998).
Elements of the Theory of Computation, second edition. Prentice Hall, Inc.
Martelli, A., Ravenscroft, A., and Ascher, D., editors (2005).
Python Cookbook, second edition. O’Reilly & Associates, Inc.
Chapter 2
■
the BasiCs
41
Massart, D. L., Smeyers-Verbeke, J., Capron, X., and Schlesier, K. (2005). Visual presentation
of data by means of box
plots.
LCGC Europe, 18:215–218.
McGeoch, C., Sanders, P., Fleischer, R., Cohen, P. R., and Precup, D. (2002). Using finite experiments to study
asymptotic performance.
Lecture Notes in Computer Science, 2547:94–126.
Moret, B. M. E. (2002). Towards a discipline of experimental algorithmics. In Data Structures, Near Neighbor Searches,
and Methodology: Fifth and Sixth DIMACS Implementation Challenges, volume 59 of DIMACS:
Series in Discrete
Mathematics and Theoretical Computer Science, pages 197–214. Americal American Mathematical Society.
Petzold, C. (2008).
The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and
the Turing Machine. Wiley Publishing, Inc.
Salzberg, S. (1997). On comparing classifiers: Pitfalls to avoid and a recommended approach.
Data Mining and
Knowledge Discovery, 1(3):317–328.
Sanders, P. (2002). Presenting data from experiments in algorithmics.
Lecture Notes in Computer Science, 2547:181–196.
Spinrad, J. P. (2003).
Efficient Graph Representations. Fields Institute Monographs. American Mathematical Society.
Turing, A. M. (1937). On computable numbers, with an application to the Entscheidungsproblem.
Proceedings of the
London Mathematical Society, s2-42(1):230–265.
Vaingast, S. (2009).
Beginning Python Visualization: Crafting Visual Transformation Scripts. Apress.
West, D. B. (2001).
Introduction to Graph Theory, second edition. Prentice Hall, Inc.
