Chapter Exercises

True or False. Complexity analysis can provide the exact running time of an algorithm.

True or False. Complexity analysis is performed independent of the hardware and language used.

What does a big-O value represent?

Why is the constant of proportionality not important when specifying the time-complexity of an algorithm.

True or False. All algorithms have a best and worst case time-complexity.

True or False. An algorithm containing a loop whose iterations are based on the input size must have a time-complexity larger than $\text{O}\left(1\right)$.

True or False. The average case time-complexity algorithm will be the same as its amortized cost.

What is the difference between a general matrix and a sparse matrix?

True or False. The list based implementation of the Sparse Matrix ADT provides a better time-complexity for the addition operation than the 2-D array implementation of the general matrix.

True or False. All operations of the list based implementation of the Sparse Matrix ADT have better worst case time-complexities than the 2-D array implementation of the general matrix.

How does a Set differ from a Bag?

What is the difference between the set union and the set intersection operations?

What is a variable-length argument? Give an example of a built-in function that defines a variable-length argument.

Arrange the following expressions from slowest to fastest growth rate.

$$n{\log }_{2}n{4}^{n}k{\log }_{2}n5n^{2}40{\log }_{2}n{\log }_{4}n12n^6$$

Determine the $\text{O}(\cdot )$ for each of the following functions, which represent the number of steps required for some algorithm.

1. $T(n)=n^2+400n+5$
2. $T(n)=67n+3n$
3. $T(n)=2n+5n\log n+100$
4. $T(n)=\log n+2n^2+55$
5. $T(n)=3(2^n)+n^8+1024$
6. $T(n,k)=kn+\log k$
7. $T(n,k)=9n+k\log n+1000$

Evaluate each of the following code segments and determine the $\text{O}(\cdot )$ for the best and worst cases. Assume an input size of $n$.

1. sum = 0
   for i in range( n ) :
     if i % 2 == 0 :
       sum += i
2. sum = 0
   i = n
   while i > 0 :
     sum += i
     i = i // 2
3. for i in range( n ) :
     if i % 3 == 0 :
       for j in range( n // 2 ) :
         sum += j
     elif i % 2 == 0 :
       for j in range( 5 ) :
         sum += j
     else :
       for j in range( n ) :
         sum += j

Determine the $\text{O}(\cdot )$ for the following Set operations:difference, intersect, and remove.

Complete the Set class by implementing the clear, intersect, and difference methods.

Modify the Set constructor to accept an optional variable argument to which a collection of initial values can be passed to initialize the set. The prototype for the new Set constructor should look as follows:

It can then be used as shown here to create a set initialized with the given values:

Add a new operation to the Set ADT to test for a proper subset. Given two sets, $A$ and $B$, $A$ is a proper subset of $B$, if $A$ is a subset of $B$ and $A$ does not equal $B$.

Add the __str__ method to the Set implementation to allow a user to print the contents of the set. The resulting string should look similar to that of a list, except you are to use curly braces to surround the elements.

What is the time-complexity of the proper subset test operation?

Prove or show why the worst case time-complexity for the insert and remove vector operations are $$.

Implement the remaining methods of the SparseMatrix class: __sub__, __mul__, transpose, and __getitem__.

Determine the worst case time-complexities for the SparseMatrix methods implemented in the previous question.

Add Python operator methods to the SparseMatrix class that can be used in place of the named methods for several of the operations: __add__, __sub__, and __mul__.

In this chapter, we implemented the Set ADT using a list. Implement the Set ADT using a bag created from the Bag class. In your opinion, which is the better implementation? Explain your answer.