### announcements

#### 2016-06-16 - CS Dojo poll

posted Jun 16, 2016, 10:31 AM by Samuel Konstantinovich   [ updated Jun 16, 2016, 10:31 AM ]

#### 2016-06-10

posted Jun 10, 2016, 9:06 AM by Samuel Konstantinovich   [ updated Jun 10, 2016, 9:15 AM ]

 Rank your final projects: (leave yours blank)http://goo.gl/forms/pqjXlzcmS2cAJMkQ2Final Project Exit Survey:http://goo.gl/forms/NQtVnB6RvGs7TSL92

#### 2016-05-20

posted May 20, 2016, 8:41 AM by Samuel Konstantinovich   [ updated May 20, 2016, 9:17 AM ]

 If I were to give a quiz on Monday on Hash Tables... It would Look like this:381. Which of the following scenarios leads to linear running time for a random search hit in a linear-probing hash table?a) All keys hash to same indexb) All keys hash to different indicesc) All keys hash to an even-numbered indexd) All keys hash to different even-numbered indicese) None of these.583. What is the best definition of a collision in a hash table?A. Two entries are identical except for their keys.B. Two entries with different data have the exact same key.C. Two entries with different keys have the same exact hash value.D. Two entries with the exact same key have different hash values.207. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?A. 256B. 511C. 512D. 1024E. There is no maximum.402. An open addressed hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?A. 256B. 511C. 512D. 1024E. There is no maximum.481. Draw a hash table with open addressing and linear probing with a size of 9. Use the hash function k%9. Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that order). The values can all be null, they do not matter.999. Draw a hash table with chaining and a size of 9. Use the hash function k%9. Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that order). The values can all be null, they do not matter.4810. You are writing code for the remove member function of a chained hash table. Fill in the blanks in this pseudocode with the two missing statements. You may use pseudocode yourself!public class HashTable{  public void remove(int key)  {        Node cursor;//a double linked node with set/get Key/Value/Prev/Next        int i;        i = hash(key);        //Make cursor point to the node that contains an item with the given key        //(or set it to NULL if there is no such node).        if (cursor != NULL){         }   }}

#### 2016-05-16

posted May 16, 2016, 9:03 AM by Samuel Konstantinovich   [ updated May 17, 2016, 7:40 AM ]

 Sample code: What if you want to save your world in a file? Notes: The first time it runs, it makes a file with all 0's If you change the size, delete your text file so it loads the proper dimensions```int per; int [][]grid; void setup() { size(800, 640); per = 80; int rows = height/per; int cols = width/per; grid = new int[height/per][width/per]; String[] vals = new String[rows*cols]; try { BufferedReader reader = createReader("level.txt"); String line = reader.readLine(); vals = line.split(" "); println("Read a file"); for (int i = 0; i < rows*cols; i++) { if (vals[i] != null) { int n =Integer.parseInt(vals[i]); grid[i/cols][i%cols] = n; } } } catch(Exception e) { e.printStackTrace(); println("No file, or other error in setup"); for (int i = 0; i < vals.length; i++) { vals[i]="0"; } } } void draw() { background(0); textSize(24); for (int r = 0; r < height/per; r+=1) { for (int c = 0; c < width/per; c+=1) { //for each grid element //3 means green if (grid[r][c] == 3) { noStroke(); fill(0, 255, 0); rect(c*per, r*per, per, per); } //2 means red if (grid[r][c] == 2) { noStroke(); fill(255, 0, 0); rect(c*per, r*per, per, per); } //draw text in the middle of the cell fill(255); text(grid[r][c]+"", c*per+per/2, r*per+per/2); } } } void mouseClicked() { inc(mouseX, mouseY); } //increase a box to the next value void inc(int x, int y) { x = x / per; y = y / per; grid[y][x] += 1; grid[y][x] %= 10; } void exit() { print("Write a file"); PrintWriter output = createWriter("level.txt"); for (int r = 0; r < height/per; r+=1) { for (int c = 0; c < width/per; c+=1) { output.print(grid[r][c]+" "); } } output.close(); }```Fill this out: (Log into your STUY.EDU email first)https://docs.google.com/a/stuycs.org/forms/d/1fblWpXVpnmMnNbKxxqSCSFMRM0zppxRKAxzyZx4Klro/viewform

#### 2016-05-13

posted May 13, 2016, 8:49 AM by Samuel Konstantinovich   [ updated May 13, 2016, 9:15 AM ]

 To install processing run this script on a terminal:/home/support/konstans/public_html/processing/copy.shFriday The 13th The Game:```/////////////////////////////////////////////////////////////////////////// //Positionable /////////////////////////////////////////////////////////////////////////// public interface Positionable { public float getX(); public float getY(); public void setState(String newState); public String getState(); } /////////////////////////////////////////////////////////////////////////// //Displayable /////////////////////////////////////////////////////////////////////////// public interface Displayable extends Positionable{ public void display(); } /////////////////////////////////////////////////////////////////////////// //Moveable /////////////////////////////////////////////////////////////////////////// public interface Moveable extends Positionable { public void move(); public void collide(ArrayList others); } /////////////////////////////////////////////////////////////////////////// //Main Program /////////////////////////////////////////////////////////////////////////// //(instance variables) ArrayList thingsToMove = new ArrayList(); ArrayList thingsToDisplay = new ArrayList(); ArrayList thingsThatExist = new ArrayList(); EvilCamper player = new EvilCamper(); String lastKey = ""; boolean keyUsed = false; public void setup() { size(600, 400); for (int i = 0; i < 10; i++) { Camper c = new Camper(); thingsToMove.add(c); thingsToDisplay.add(c); thingsThatExist.add(c); } thingsToMove.add(player); thingsToDisplay.add(player); thingsThatExist.add(player); } public void keyPressed() { print(keyCode+","); keyUsed = true; //WASD if (keyCode == 65) { //A lastKey = "A"; } if (keyCode == 68) { //D lastKey = "D"; } if (keyCode == 87) { //W lastKey = "W"; } if (keyCode == 83) { //S lastKey = "S"; } } public void mouseClicked() { delete(mouseX, mouseY); } public void delete(float x, float y) { for (int i = thingsThatExist.size() - 1; i>=0; i-- ) { Positionable p = thingsThatExist.get(i); if ( dist(x, y, p.getX(), p.getY())<20) { p.setState("REMOVE"); } } } public void draw() { /*********************************************** get user input */ handleUserInput(); /************************************************ *change object states */ for ( Moveable m : thingsToMove) { //move objects m.move(); //check for collisions/events m.collide(thingsThatExist); } /************************************************ *draw objects */ //clear the world background(255); //draw things for ( Displayable d : thingsToDisplay) { d.display(); } //draw overlay drawOverlay(); /*********************************************** *remove objects from the game if they need to be */ /* for (int i = thingsToMove.size() - 1; i >= 0; i--) { String state = thingsToMove.get(i).getState(); if (state.equals("DEAD") || state.equals("REMOVE")) { thingsToMove.remove(i); } } */ /* for (int i = thingsToDisplay.size() - 1; i >= 0; i--) { String state = thingsToDisplay.get(i).getState(); if ( state.equals("REMOVE")) { thingsToDisplay.remove(i); } } */ /* for (int i = thingsThatExist.size() - 1; i >= 0; i--) { String state = thingsThatExist.get(i).getState(); if ( state.equals("REMOVE")) { thingsThatExist.remove(i); } } */ } public void handleUserInput() { if (keyUsed) { if (lastKey.equals("W")) { } if (lastKey.equals("A")) { } if (lastKey.equals("S")) { } if (lastKey.equals("D")) { } //only allow one thing per key press keyUsed = false; } } public void drawOverlay() { text("Things that exist: "+thingsThatExist.size(), 20, 20); text("Things to display: "+thingsToDisplay.size(), 20, 40); text("Things to move: "+thingsToMove.size(), 20, 60); } /////////////////////////////////////////////////////////////////////////// //Camper /////////////////////////////////////////////////////////////////////////// public class Camper implements Moveable, Displayable { private float x, y, heading, speed; private String state; public float getX() { return x; } public float getY() { return y; } public float getHeading() { return heading; } public float getSpeed() { return speed; } public String getState() { return state; } public void setState(String newState) { state = newState; } public Camper() { state = "MOVING"; x = width/2; y = height/2; heading = (int)random(6)*60; speed = (1+random(10))/10.0; } public void move() { if (state.equals("MOVING")) { x += speed * cos(radians(heading)); y += speed * sin(radians(heading)); }else if (state.equals("PATTERN")) { //DO SOEMTHING ELSE HERE //SOMETIMES CHANGE THE STATE } } public void collide(ArrayList others) { if (x > width - 50 || x < 50) { heading = (360 + 180 - heading ) % 360; } if (y > height - 50 || y < 50) { heading = (360 - heading); } } public void display() { fill(255); if (getState().equals("DEAD")) { fill(255, 0, 0); } ellipse(getX(), getY(), 30, 30); ellipse( getX() + 15 * cos(radians(getHeading())), getY() + 15 * sin(radians(getHeading())), 10, 10); fill(0); text("heading:"+getHeading()+"\nState:"+getState(), getX(), getY()); } } /////////////////////////////////////////////////////////////////////////// //Evil Camper /////////////////////////////////////////////////////////////////////////// public class EvilCamper extends Camper { public void display() { fill(100, 200, 100); ellipse(getX(), getY(), 30, 30); fill(255, 0, 0); ellipse( getX() + 15 * cos(radians(getHeading())), getY() + 15 * sin(radians(getHeading())), 10, 10); fill(0); text("heading:"+getHeading(), getX(), getY()); } public void collide(ArrayList others) { super.collide(others); //kill the campers here! for (Positionable c : others) { if ( c != this ) { if (c.getState().equals("MOVING") && dist(this.getX(),this.getY(),c.getX(),c.getY()) < 20.0) { c.setState("DEAD"); } } } } }```

#### 2016-05-13

posted May 13, 2016, 4:51 AM by Samuel Konstantinovich   [ updated May 13, 2016, 4:51 AM ]

 Friday the 13th the game:Setup:     Initialize everything     Start the gameMain loop:    INPUT:     get user input     get network input    GAME LOGIC/OBJECT CHANGES     change object states     move objects     check for collisions/events    RENDER THE GRAPHICS     draw objects

#### 2016-05-12 Final Project Guidelines

posted May 11, 2016, 8:45 AM by Samuel Konstantinovich   [ updated May 11, 2016, 9:13 AM ]

#### 2016-05-10 Running Medians

posted May 10, 2016, 8:41 AM by Samuel Konstantinovich   [ updated May 10, 2016, 8:41 AM ]

 Senior ElectivesGradespublic RunningMedian()  :    Create an empty running median set.public double getMedian() :    When empty: throws new NoSuchElementException()    Returns the median valuepublic void add(Integer x)    add to the "SmallValue" heap if  x < median,     add to the "BigValue" heap otherwise.     balance the two heaps so that their size differ by no more than 1.

#### 2016-05-05

posted May 5, 2016, 9:15 AM by Samuel Konstantinovich   [ updated May 9, 2016, 9:24 AM ]

 Cinco De Mayoimport java.util.*;@SuppressWarnings("unchecked")public class MyHeap>{   private int size;   private T[] data;   public MyHeap()   public MyHeap(T[] array)   /**pushDown      precondition: datas[k]'s children are valid heaps      postconditions:-the element at index k has been                      shifted to the correct spot.                     -data[k] and is a valid heap   **/   private void pushDown(int k)   /**pushUp      precondition: data is a heap with at most one item      out of place (element at k)      postconditions:-the element at index k has been                      shifted to the correct spot.                     -data is a valid heap   **/   private void pushUp(int k)   public T delete()  /**Throws a no such element exception if size==0 when called**/   public T peek()    /**Throws a no such element exception if size==0 when called**/   public void add(T x)   private void heapify()   private void doubleSize()   /**toString returns an array style string, without any nulls   **/   public String toString()   //do this last   public MyHeap(boolean isMax)   public MyHeap(T[] array, boolean isMax)}

#### 2016-05-04

posted May 4, 2016, 8:22 AM by Samuel Konstantinovich   [ updated May 4, 2016, 8:55 AM ]

 May the 4th be with you.Update: If you submit your BST without remove you will get full credit. If you get remove to work correctly (on time), you will get extra credit.Goal: One heaping helping of data structures. Heaps are binary tree like structureRestrictions when creating heaps:Parent must always be bigger(max heap) / smaller(min heap) than both children.tree must always be full ( the tree should be filled from bottom left to right )Ex: max heap 50 49 40     a           b         c          dit would be filled starting from a to b to c then dget max  = O(1)add/remove root = O(logn)add - 1) put the value in the next open spot          2) push up the valueRemove the root:1) replace the root with the lower right node (bottom row rightmost node)2) push it down into the correct place.Note, the Next position: the lower right most empty spot. Add a value:1)The first add makes the value the root2) puts the new value in the to the next position and checks if the new element is in the correct spot. If not, swap the value with the parent, (repeat) until you have a heap.Using arrays for heapsOur array can store the values of the heap like this: 1(Put the value here into index 1) 2 3(put the value here into index 3)     4      5        6       7 8 9  10 11 12 13  14 15 Notice there is no ‘0’ because doing it this way is much nicer. If we stored int then we could use index 0 as the size variable. 2 * index = left child2 * index + 1 = right childindex / 2 = parent indexindex 0 used for counter of elementsExample: a b cwould become an array:null a b c

1-10 of 38