Courses‎ > ‎AP Computer Science 2‎ > ‎

Konstantinovich

2017-03-28 Linked List

posted by Samuel Konstantinovich

java linked lists:
https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html


Phase I:
boolean add(int value) 
    - adds the value to end (try adding to the front first, for testing purposes)
int size() 
    - return the number of elements in the list
toString() 
    - returns a string representation of the list of n elements formatted like: 
        [ v0, v1, v2, v3, ... vn-1, ] 
          An empty list is just []
int get(int index) 
    - return the value of the element at the specified index (0 based)
int set(int index,int newValue)
    - change the value of the element at the specified index to the newValue, return the old value  

Phase II:
int indexOf(int value) 
    - returns the index of the 1st occurrence of the value in the linked list, -1 if not found.
boolean add(int index, int value)    
    - insert a new element at the specified index, 0 at the front, size() at the end. 
int remove(int index) 
    - remove the element at the specified index, returns the value removed

ALSO: 
-Any exceptions that the actual LinkedList contains:  get,set,add,remove

2017-03-27

posted by Samuel Konstantinovich   [ updated ]

Goal:  My Linked List


Git Directory /09*

09MyLinkedList

Should Include:

-MyLinkedList.java

                -LNode (inner class)

Methods That MyLinkedList.java should have:

            variables: (start with these and add more as we need them)

            LNode start;

            int size;

            methods:

        Hint: Start by writing add() to the start of the list, and toString() to see if it is working. Test these methods before writing new ones later!

How to loop through the elements:

Make a temporary reference to the node when you iterate through them (you can call it current)    

    LNode current = start;

In the loop use this piece of code to reference to the next of the temporary LNode or current

    current = current.next; //private access is fine

2017-03-23 Mergesort

posted Mar 23, 2017, 6:30 AM by Samuel Konstantinovich   [ updated Mar 23, 2017, 11:31 AM ]

We discussed the mergesort yesterday:



def mergesort(ary)  
   mergesort the leftHalf
   mergesort the rightHalf
   mergeTheTwoHalvesIntoTheOriginalArray


This can be done in many ways for example copy each half into a new array:

def mergesort(int[]ary)
  if ...base case...
   stop!
  else
   int[]left = copy of the left side;
   int[]right = copy of the right side;
   mergesort(left)
   mergesort(right)
   mergeTheTwoHalvesIntoTheOriginalArray

This will use more space but is still very fast. This is the easiest way and will be all that I require.

One possible way to make the merge method work well in this situation is to merge directly into the array you want to put the values into (DO NOT return a new array and then copy that over

void merge(int[]a,int[]b,int[]destination){...}
Postcondition:
     destination contains all of the elements of a and b, and is sorted. 
Preconditions:
    a is sorted, b is sorted
    destination.length == a.length + b.length


There are more advanced ways that would be better suited for extra credit. You can think of ways to optimize your mergesort if you feel like entering the merge sort competition which will be put up later.

Write the mergesort in your git directory:
./08*/
  Merge.java
      ->public static void mergesort(int[]ary)

2017-03-21 HW07

posted Mar 20, 2017, 9:28 PM by Samuel Konstantinovich   [ updated Mar 23, 2017, 11:26 AM ]

on Github:
Directory: 
07*/   (e.g. 07Quick)  
  -> Quick.java
  ---> public static void quicksort(int[]ary){...}
  ---> public static int quickselect(int[]ary, int k){...}
Both quicksort and quickselect must work with arrays that contain many duplicates. You must use the dutch flag partitioning to accomplish this. 

To check your assignments go here:

Log in : your default password is your osis.

Median on quiz was  18 points.
Median on take home reduxquiz was 14 points (because it should be)

The following was used to determine your letter grade:
01
02
05
06
The Quiz.
EC01

If you were missing more than 1 item other than the Extra Credit, it got a comment on the report card and a warning letter grade.
Much like SING, without point deductions, you have no incentive to follow the rules.  





Regarding your repo, here is a list of what your repo should look like:
01sqrt
02NQueens
03Knights
04Maze
05USACO
06Quiz
07Quick
EC01
otherstuff  <- any non-numbered directories can be used for your other stuff!





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

2016-03-17

posted Mar 17, 2017, 7:15 AM by Samuel Konstantinovich

-NYU:
Professor Perlin offered access to his labs for interested Stuy students. This would be great for any student that would want to do some augmented reality work. Send me an email if this sounds interesting. I misrepresented this offer last time so please send another email if you are still interested!
-Talk:
"On Monday, 3/20 at 4pm in room 307, Phillip Compeau, a professor at Carnegie Mellon University will be giving a video talk about Computational Biology. The talk should be a primer on Computational Biology, while also talking a bit about CMU’s brand new major in that field that they are launching in the fall of 2017. I think this is going to be a good talk and a chance for the juniors to see another potential field in CS. Please advertise it to your AP classes."
-Recs:
If you are looking for a college rec from me here are some requirements and guidelines:
[You can always discuss specifics with me these are not absolute rules]
 -I require that you are applying for a CS (or closely related) major
 -I require that you have some combination of: 
     Outstanding performance, 
     Involvement in the CS community, 
     Work on CS related projects outside of the required classwork.
 -Ask me after the AP, before final projects/finals. That is a much calmer time of the year.

2017-03-15 HW

posted Mar 14, 2017, 9:44 PM by Samuel Konstantinovich   [ updated Mar 14, 2017, 11:56 PM ]

Goal: Quickselect

Array functions that work on an array "in place" will operate on the given array, and not make a copy, or use extra array space. This is often faster than re-copying the data. Sometimes


You should have a partition method. You should have tested it

IMPORTANT: if you did not write this method in place, that is fine, but you will want to fix that after you get the rest of the code working. 

public static int part ( int [] data, int start, int end){
    //-Choose a random element to be a pivot, and partition the array around it. 
    //-Only partition the elements from start to end inclusive.
    //-When done returns the index of the final position of the pivot element.      
    //    (Should be from start to end inclusive)
}

Regarding partition:
What does this function do?
How can you test this so you can easily verify it is working?
NOTE: I tested my code incorrectly and spent 30 minutes fixing a something that wasn't broken. 

hint: Visually easy to look at arrays will be your friend:
{999,999,999,4,1,0,3,2,999,999,999}


NOW HW07 - you should be able to complete this if you tested your partition method. We will expand on it tomorrow.

make a git directory and add a file to it:
/07Quick/Quick.java

We discussed an algorithm last Friday, where we find the Kth smallest element of an array. This is known as the quickselect function.

Use your working and thoroughly tested partition method to write a Kth element selector function: 

public static int quickselect(int []data, int k){
  //return the value that is the kth smallest value of the array. 
  //use your partition method to help you accomplish this.
}



int[]ary = { 2, 10, 15, 23, 0,  5};
select( ary , 0 ) would return 0
select( ary , 1 )  would return 2
select( ary , 2 )  would return 5
select( ary , 3 )  would return 10
select( ary , 4 )  would return 15
select( ary , 5 )  would return 23

Test your method on different sized arrays. 



2017-03-13

posted Mar 13, 2017, 11:29 PM by Samuel Konstantinovich

Quickselect discussion.

Homework: Write a partition method:

int part ( int [] data, int start, int end){}

-Choose a random element to be a pivot, and partition the array around it. 
-Only partition the elements from start to end inclusive.
-When done returns the index of the final position of the pivot element. (Should be from start to end inclusive)


2017-03-10

posted Mar 10, 2017, 7:13 AM by Samuel Konstantinovich

Goal:
1. USACO Silver
2. Partitioning an array.

2017-03-09

posted Mar 8, 2017, 8:46 PM by Samuel Konstantinovich   [ updated Mar 9, 2017, 11:24 AM ]

Goal: Reparations! Complete this method on git under /06/Quiz2Redux.java

Announcements:
1. USACO will be graded Monday. You should try to finish the silver (even a slow version) ASAP, I will give some hints tomorrow for a better version.
2. Today's work will be due Tuesday so that you have at least 1 non-overlapping work day. It was meant to be a quiz, so it should be solveable.
3. A few of the presenters from Friday’s trip agreed to share their presentation slides with us. See the links below if interested:


Recursive backtracking is really good for generating all possibilities. All possible paths, sequence of moves, permutations/combinations/sets of elements.

Consider
boolean checkSum(n,data){
 //does any subset of elements in data add up to n?
}

checkSum( 40,[1,3,5,7,11,13,17]) -> True
How do we determine this on paper?
How do we make a program check this for us?

Consider
boolean checkSum(data1,data2){
 //does any NONZERO subset of elements in data1 add up to
 // any NONZERO subset of elements of data2?
}

checkSum( [1,3,5,7,11,13,17],[1,3,5,7,11,13,17]) -> True (same list)
checkSum( [1,3,5],[8,13,17]) -> True (8) 
checkSum( [1,3,6],[8,13,17]) -> False
checkSum( [1,3,5],[3,13,17]) -> True (3)
checkSum( [1,3,4,5],[19,13,17]) -> True (13)
checkSum( [9,14,18],[8,13,17]) -> False




Now consider:
[a,b,c,d]
How can we generate the powerset of this? (powerset is all subsets including the empty set and original set)
{ {}, {a}}  is the powerset of {a}
{ {}, {a}, {b}, {a,b}} is the powerset of {a,b}
{ {}, {a}, {b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}} is the powerset of {a,b,c}
{ {}, {a}, {b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}, 
  {d}, {a,d}, {b,d}, {a,b,d}, {c,d}, {a,c,d}, {b,c,d}, {a,b,c,d}}  is the powerset of {a,b,c,d}

This is a slightly modified version of the quiz to be completed and placed on github. 

Write an auxiliary method help( ArrayList<String> words,  /*more*/  )

It should create all possible subsets of letters from the String parameter of combinations, and add them to an ArrayListof Strings.
It is to be called inside the combinations method. 
Assume there are no duplicate letters in the string provided to combinations.
The order of the ArrayList is not important, only that all sequences are generated.
The letters that occur in each sequence should be in the same order as the original string.
The result is an ArrayList with:
  -The empty string, 
  -All 1 character strings, 
  -All 2 character strings, 
     ... 
   -Up to and including the string with all the characters.Since the ArrayList is sorted, the order is predictable

e.g.

- combinations("abcd") results in:
[, a, ab, abc, abcd, abd, ac, acd, ad, b, bc, bcd, bd, c, cd, d]

- combinations("kji") results in:
[, i, j, ji, k, ki, kj, kji]

(Note: In all cases: the first string is an empty string!)


import java.util.*;
public class Quiz2Redux{  
  /*Returns an ArrayList<String> that contains all subsets of the
   *characters of String s. Assume s has no duplicate characters.
   *the characters should appear in the same order that they occur 
   *in the original string.
   */
  public static ArrayList<String> combinations(String s){
      ArrayList<String>words = new ArrayList<String>();
      help( words , /*fill this in with more */);
      Collections.sort(words);
      return words;
  }
  
  private static void help( ArrayList<String> words, 
                             /*fill this in with more arguments*/ ){
   /*METHOD TO BE WRITTEN BY YOU.*/ 
  }
}




1-10 of 21