Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-03-20

posted Mar 20, 2017, 6:07 AM by Samuel Konstantinovich   [ updated Mar 20, 2017, 12:05 PM ]
PTC:
Email me with PTC in the subject if you want to volunteer. LMK if you can bring a laptop, I need one laptop per day.

Do Now:
Copy this diagram, then write out the pseudo code for your partition algorithm:

basic partition:
basic partition


Discussion on better partitioning: (Dutch Flag Problem)
partition with clustering of pivots:
partition with clumped pivots
How do we change our original algorithm to make this happen?

Before we wrote partition to return a pivot index, so the other method could use it. Now we need two values to determine where to partition. 
-What is a good way to handle partitioning of the left and right side when the pivots are clustered?







TEST CODE FOR USACO :
public class Test05 {
  public static void main(String[]args) throws Exception{
    USACO u = new USACO();
    String number = args[0];

    if(args.length == 1){
        String file = "makelake."+number;
      int tot = 0;
      if(u.bronze(file+".in")==new Scanner(new File(file+".out")).nextInt()){
        System.out.println("PASS case: "+file+".in +++++++++++++");
      }else{
        System.out.println("Fail case: "+file+".in ------------");
      }
    }else if(args.length ==2){
      String file = "ctravel."+number;
      if(u.silver(file+".in")==new Scanner(new File(file+".out")).nextInt()){
        System.out.println("PASS case: "+file+".in +++++++++++++");
      }else{
        System.out.println("Fail case: "+file+".in ------------");
      }
    }

    }
  }

run like this:
//Bronze is default.
timeout 2 java Test05 1

timeout 2 java Test05 2

timeout 2 java Test05 1 silver

timeout 2 java Test05 2 silver
Comments