V22.102:Honors Data Structures
Some exercises on performance and asymptotics.
Due: Monday Feb. 7
1. From text: problem 2.26 (p. 102). The term "instance characteristic"
means the parameter that we use to describe the size of the input.
2. From text: problem 2.28 (p. 103). Note that program 2.26 uses
the following trick to simplify the code: assume that array we are searching
has a spare location at the end. If the array has size n, we want to know
whether value x appears in the first (n-1) locations of the array. To simplify
the search, we place the value of x in the n'th location, so that the search
always succeeds. Finally we check whether what we found is in the array itself,
or whether it is the added element (often called the guard).
3. From text: problem 3.19 (p.132). Use a calculator or plot a few points
of each function if you cannot find an exact solution.