Representative Problems for CSE 214 -- Midterm 2 ------------------------------------------------ The second midterm exam will consist of about 4-5 questions of the following difficulty. My expectation is that the questions will be somewhat harder than the previous exam. I like questions which involve writing a procedure or answering short answer questions. Any topic we discussed in class is fair game. Particularly important topics include: pointers (from first midterm, but important enough that I might include a question) big Oh notation what is it (definition), how do you find the worst-case running time of an algorithm, working with the big Oh. sorting algorithms (algorithms and analysis) insertion / selection sort mergesort / quicksort heapsort and priority queues binary search multidimensional arrays hashing It should help to study the Sedgewick book and the lecture notes on the WWW, however my questions stress applying the concepts we have learned more than memorization. Good luck, Steven Skiena ========================================================================= 1. Write a procedure to rearrange an array of integers so that all the negative numbers precede all of the non-negative numbers. Within each group the numbers do not have to be ordered in any particular way. Your procedure should have $O(n)$ worst-case running time, where $n$ is the size of the array. 2. For each of the following, describe a situation where the first algorithm is better than the second algorithm. You may used a given situation/reason for only one part of this problem. (a) When might insertion sort be better than quicksort? (b) When might quicksort be better than insertion sort? (c) When might sequential search be better than binary search? (d) When might hashing be better than sorting/binary search? (e) When might sorting/binary search be better than hashing? 3. (a) Provide an access formula for element (row, col) of a triangular shaped array where the $i$th row contains $2i$ columns and there are a total of $nrows$ rows. Thus you want to calculate which position in the underlying one-dimensional array represents element (row, col) in the triangular array. Your access formula should return 1 for element (1,1). (b) Do you really need to know the number of rows $nrows$ for the access formula?