Chapter Exercises

Given an unsorted list of $n$ values, what is the time-complexity to find the $k$^th smallest value in the worst case? What would be the complexity if the sequence were sorted?

What is the $\text{O}(\cdot )$ for the findSortedPosition function in the worst case?

Consider the new implementation of the Set class using a sorted list with the binary search.

1. Prove or show the worst case time for the add method is $\text{O}\left(n\right)$.
2. What is the best case time for the add method?

Determine the worst case time complexity for each method of the Map ADT implemented in Section 2.8.

Modify the binary search algorithm to find the position of the first occurrence of a value that can occur multiple times in the ordered list. Verify your algorithm is still $\text{O}\left(\text{log}n\right)$.

Design and implement a function to find all negative values within a given list. Your function should return a new list containing the negative values. When does the worst case occur and what is the run time for that case?

In this chapter, we used a modified version of the mergeSortedLists function to develop a linear time union operation for our Set ADT implemented using a sorted list. Use a similar approach to implement new linear time versions of the isSubsetOf, intersect, and difference methods.

Given the following list of keys (80, 7, 24, 16, 43, 91, 35, 2, 19, 72), show the contents of the array after each iteration of the outer loop for the indicated algorithm when sorting in ascending order.

1. bubble sort
2. selection sort
3. insertion sort

Given the following list of keys (3, 18, 29, 32, 39, 44, 67, 75), show the contents of the array after each iteration of the outer loop for the

1. bubble sort
2. selection sort
3. insertion sort

Evaluate the insertion sort algorithm to determine the best case and the worst case time complexities.

Implement the Bag ADT from Chapter 2 to use a sorted list and the binary search algorithm. Evaluate the time complexities for each of the operations.

Implement a new version of the Map ADT from Section 2.7 to use a sorted list and the binary search algorithm.

The implementation of the Sparse Matrix ADT from Chapter 5 can be improved by storing the MatrixElement objects in a sorted list and using the binary search to locate a specific element. The matrix elements can be sorted based on the row and column indices using an index function similar to that used with a 2-D array stored in a MultiArray. Implement a new version of the Sparse Matrix ADT using a sorted list and the binary search to locate elements.

Implement a new version of the Sparse Life Grid ADT from Chapter 4 to use a sorted list and the binary search to locate the occupied cells.

A colormap is a lookup table or color palette containing a limited set of colors. Early color graphics cards could only display up to 256 unique colors at one time. Colormaps were used to specify which 256 colors should be used to display color images on such a device. Software applications were responsible for mapping each color in the image that was to be displayed to a color in the limited color set specified by the colormap. We can define a Colormap ADT for storing a limited set of colors and for use in mapping one of the 16.7+ million colors possible in the discrete RGB color space to a color in the colormap. Given the description below of various operations, implement the Colormap ADT using a 1-D array structure.

• Colormap(k)
  Creates a new empty colormap that is capable of storing up to $k$ colors.
• length()
  Returns the number of colors currently stored in the colormap.
• contains(color)
  Determines if the given color is contained in the colormap.
• add(color)
  Adds the given color to the colormap. Only one instance of each color can be added to the colormap. In addition, a color cannot be added to a full colormap.
• remove(color)
  Removes the given color from the colormap. The color must be contained in the colormap in order to be removed.
• map(color)
  Maps the given color to an entry in the colormap and returns that color. A common approach is to map the color to its nearest neighbor in the colormap. The nearest neighbor of a color is the entry in the colormap that has the minimum Euclidean distance squared between the two colors. If there is more than one nearest neighbor in the colormap, only one is returned. In addition, the colormap must contain at least one color in order to perform the mapping operation.
• iterator()
  Creates and returns an iterator object that can be used to iterate over the colors in the colormap.

Evaluate the map method of your implementation of the Colormap ADT from the previous question to determine the worst case time-complexity.

Colormaps are used in color quantization, which is the process of reducing the number of colors in an image while trying to maintain the original appearance as much as possible. Part of the process recolors an original image using a reduced set of colors specified in a colormap.

1. Implement the function recolorImage(image, colormap), which produces a new ColorImage that results from mapping the color of each pixel in the given image to its nearest neighbor in the given colormap.
2. What is the worst case time-complexity for your implementation?