CS 2110 Midterm: CS 2110 Cornell 2012 Fall Examsp2solcs211sp04

• School: Cornell University
• Department: Computer Science
• Course: CS 2110
• Professor: All

Document Summary

Sample answers: (a) worst-case time for n = k+1-h: o(n*n); Average-case time: o(n log n) (b) public static void quicksort(int[] b, int h, int k) { if (h+1 k < 10) { insertionsort(b, h, k); return; } medianof3(b, h, k); // it is ok to leave this out int j= partition(b, h, k); // { b[hj 1] <= b[j] <= b[j+1k] } if (j h <= k j) { quicksort(b, h, j 1); quicksort(b,j+1, k); else { quicksort(b,j+1, k); quicksort(b, h, j 1); Sorting the larger partition using a tail-recursive call reduces space to. O(log n) if the language imple- ments tail recursion nicely: to save space, we omit the method specs public dlist(){ sentinel= new dnode(null, null, null); sentinel. next= sentinel; sentinel. prev= sentinel; current= sentinel; public void insert(object i){