announcements


2016-06-16 - CS Dojo poll

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


The CS Dojo wants feedback. If you ever went to the dojo please thank them by filling this out:

https://docs.google.com/a/stuy.edu/forms/d/1eaDqk26cZ4OMQpjWm9WElVmV9AUgx7YkPV2gq4D5Tfw/viewform

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/pqjXlzcmS2cAJMkQ2

Final Project Exit Survey:

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 index
b) All keys hash to different indices
c) All keys hash to an even-numbered index
d) All keys hash to different even-numbered indices
e) 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. 256
B. 511
C. 512
D. 1024
E. 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. 256
B. 511
C. 512
D. 1024
E. 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.sh


Friday 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<Positionable> others); 

}

///////////////////////////////////////////////////////////////////////////
//Main Program
///////////////////////////////////////////////////////////////////////////

//(instance variables)
ArrayList<Moveable> thingsToMove = new ArrayList<Moveable>();
ArrayList<Displayable> thingsToDisplay = new ArrayList<Displayable>();
ArrayList<Positionable> thingsThatExist = new ArrayList<Positionable>();
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<Positionable> 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<Positionable> 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 game

Main 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 ]

Final Project Guidelines:

June 7th FINAL DEADLINE

You make a new repo for your group.
You need to have in your repository:
1 The readme.md file that I can see when I first go to your repo. The readme should include:
       -Team name, 
       -Project name / description
       -*Development Log (daily progress since y'all never commit with good messages) 
       -*Project plan/outline including your goals prioritized by importance and chronology (things to do + things already done)
       -*Links to the Demo versions, what they show about the state of your project, Directions on how to compile/run each version. (e.g. what to do to clone the right version)

2 Stable "demo" versions, that show off what you did so far. This is part of your anti-procrastination grade!
 -*May 23rd,
 -*June 7th (final version, FINAL DEADLINE)

SUPER IMPORTANT:
3 You now should learn make a branches other than "main". Make a "development" branch for each member. Development branches for each member of the team for when they are modifying the code/adding new features. Use your development branch when you start to mess with things and potentially break them.
*The main branch should always compile and be demo-able. 

If someone finds a nice tutorial that explains "branching and merging for dummies", post it so everyone benefits.

*'ed things will affect your grade.

PROJECT DEMOS:
Every group will give two short presentations. 
Demo1: The Mon/Tues/Wed of the week of the May 23rd. 2-3 minutes each
Demo2: The Mon/Tues/Wed of the the week of June 7th. 3-4 minutes each.  
Unless notified ahead of time, the code is expected to run on the school computers. 

Showing code isn't important, but explaining the algorithms, or how things worked in general is important.
DO NOT SHOW CODE!

2016-05-10 Running Medians

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

Senior Electives
Grades

public RunningMedian()  :
    Create an empty running median set.

public double getMedian() :
    When empty: throws new NoSuchElementException()
    Returns the median value

public 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 Mayo

import java.util.*;
@SuppressWarnings("unchecked")
public class MyHeap<T extends Comparable<T>>
{
   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 structure

Restrictions when creating heaps:

  1. Parent must always be bigger(max heap) / smaller(min heap) than both children.

  2. tree must always be full ( the tree should be filled from bottom left to right )

Ex: max heap

50

49 40

    a           b         c          d

it would be filled starting from a to b to c then d



get max  = O(1)

add/remove root = O(logn)

add - 1) put the value in the next open spot

         2) push up the value




Remove 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 root

2) 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 heaps

Our 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 child

  • 2 * index + 1 = right child

  • index / 2 = parent index

  • index 0 used for counter of elements


Example:

a

b c

would become an array:

null a b c

1-10 of 38