Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-03-12

posted Mar 12, 2018, 10:16 AM by Konstantinovich Samuel   [ updated Mar 12, 2018, 3:42 PM ]
Good News Everyone!

Parent-Teacher conferences are upon us. As such, I once again need goons to help me keep the parents in line. If you are available 3/15, Thursday, evening (5:15 - 8), or 3/16, Friday afternoon (12:45 - 3) and are interested, please:

Email me with 

Subject line:
  PTC 2018 Spring Volunteer
Body:
-State which day you would like to help. 
-State if you can bring a laptop (not everyone needs one!)

In fitting with tradition, the payment for services rendered shall be baked goods and gratitude.


Quickselect discussion.

How can we quickly find the k'th smallest element from a list of n values?
-This can be of any comparable type so there is a set order.

e.g. 
4th smallest of:  [17, 61, 67, 47, 93,12, 20, 4, 44, 68] 

Think of several methods to do this, starting with naive and slow, then try to be more creative!

/*Choose a random pivot element, and modify the array such that:
 *1. Only the indices from start to end inclusive are considered in range
 *2. A random index from start to end inclusive is chosen, the corresponding 
 *   element is designated the pivot element. 
 *3. all elements in range that are smaller than the pivot element are placed before the pivot element.
 *4. all elements in range that are larger than the pivot element are placed after the pivot element.
 *@return the index of the final position of the pivot element.
 */

int partition ( int [] data, int start, int end){


}




Comments