Sample Discussion questions

Week of Jan 22nd

Consider the task of searching a matrix (two-dimensional array) of values. Assume that the data is represented as an N x M array, and that the array contains no duplicates.

1. First assume that the data is not sorted in any particular order. What is the worst-case number of cells you have to search to find a particular value x? What is the average-case number? What is the asymptotic complexity?
2. Suppose you know which row x is in. What is the search complexity? Now suppose you do not know what the number of the row is, but you know the row has a particular value y in the first column. What is the search complexity?
3. Next suppose the elements of each row are sorted, but the rows are unsorted. What is the complexity of finding an arbitrary value x?
4. What is the search complexity if not only the elements of the rows are sorted, but the rows themselves are also sorted (by minimum value)?
5. What is the search complexity if the elements of the rows are not sorted, but the rows themselves are still sorted by minimum value?

Now suppose you have an algorithm that performs a number of steps which is theta of f(n), for some function f.

1. If the amount of time taken by each step varies according to theta of g(n) for some function g, what can you say about the asymptotic complexity of the algorithm?
2. If the amount of time taken by each step varies randomly with the size of the input, what can you say about the asymptotic complexity of the algorithm?
3. If the amount of time taken by each step varies randomly with the size of the input but is never more than 10 seconds, what can you say about the asymptotic complexity of the algorithm?