Courses‎ > ‎AP Computer Science 2‎ > ‎

konstantinovich

Instructor email:  
konstans@stuy.edu

Office hours: 
Periods 6+7 in room 301.
It helps to let me know you are coming so I am aware when you plan to come because sometimes I am not free.

CS Dojo: 
A place to hone your skills, and practice with the guidance of caring supportive upperclassmen. 
(Will start soon)  Mon-Thur in 307

Tools and References: 
Java Practice: CodingBat
Java Visualizers: <UPDATED>

2018-05-24

posted May 24, 2018, 12:43 PM by Konstantinovich Samuel

Demo Code from class

ArrayList<Mover> movers;
public void setup() {
  size(600, 300);
  movers = new ArrayList<Mover>();
  for (int i = 0; i < 10; i++) {
    movers.add(new Mover(1));
  }
}
public void draw() {
  background(255);
  fill(0);
  text(frameRate, 20, 20);
  for (Mover m : movers) {
    m.display();
    m.update(movers);
  }
}


public class Mover {
  float x, xspeed, xacc;
  float y, yspeed, yacc;
  float r;
  color c;

  public Mover() {
    x = width/2;
    y = height/2;
    r = 50;
    c = color(0, 255, 0);
    xspeed= -2.5;
    yspeed= -1.5;
  }

  public Mover(int a) {
    x = random(width-2*r)+r;
    y = random(height-2*r)+r;
    r = 20+random(20);
    c = color(0, 255, 0);
    xspeed= random(1)-.5;
    yspeed= -3.5;
    yacc = 0.5;
  }

  public void update(ArrayList<Mover> others) {
    //change the position etc.
    x += xspeed; 
    y += yspeed; 
    yspeed += yacc;
    xspeed += xacc;
    //check the rest of the world for interactions
    checkWalls();
    checkOthers(others);
  }
  
  public void checkOthers(ArrayList<Mover> others){
    c = color(0,255, 0);
    for(Mover other : others){
      if(this != other){
       //check for collide
       if(dist(x,y,other.x,other.y) < r + other.r ){
          c = color(255, 0, 0); 
       }
      }
    }
  }
  
  

  public void checkWalls() {
    if (x < r) {
      println("OW!");
      xspeed *= -1;
      x = r;//prevents 2 true in a row
    }
    if (x > width - r) {
      println("OW!");
      xspeed *= -1;
      x = width - r;//prevents 2 true in a row
    }
    if (y < r) {
      println("OW!");
      yspeed *= -.9;
      y = r;//prevents 2 true in a row
    }
    if (y > height - r) {
      println("OW!");
      yspeed *= -.9;
      y = height - r;//prevents 2 true in a row
    }
  }
  public void display() {
    fill(c);
    ellipse(x, y, r * 2, r * 2);
  }
}

2018-05-23

posted May 22, 2018, 4:37 PM by Konstantinovich Samuel   [ updated May 22, 2018, 6:48 PM ]

For Students interested in the SHIP program this summer (July 5th-24th)
Fill out this application

Reminder Quiz Friday:

Focusing on But Not Limited To:
Hash Tables
Frontier maze solver
A* / DFS / BreadthFirstSearch / BestFirstSearch
Heaps / Heapsort


Come up with some ideas and choose a partner for the final project. 

If you want to make a game in processing, start with:
Try to make a ball that can bounce around the screen.
Try to make a ball bounce with parabolic motion.  
Try to make a ball bounce off of objects by changing the direction of its velocity.
Try making pong. 

Due Friday:
Have a partner
Have a 1-2 paragraph description of your project.

Due Tuesday:
Prototype
 -More detailed description
 -UML Diagram + How it will work 
  (overview of how it works on a broad level, not specific algorithms)
 -Stages of development

2018-05-16 Labs?

posted May 16, 2018, 11:35 AM by Konstantinovich Samuel   [ updated May 18, 2018, 6:10 AM ]

2018-05-14

posted May 14, 2018, 6:19 AM by Konstantinovich Samuel   [ updated May 14, 2018, 11:28 AM ]

You should have 3 modes for your solve:
Depth First 
Breadth First 
Best-First

Adding A* is now very easy:
+Your maze needs a toggle 
   setAStar(boolean)
   -default is false.

+Your maze can calculate the distance by including how many steps have already been taken in addition to the distance to the goal.
Either:
   -add an extra variable to each node (distanceSoFar) which is always 1 larger than the previous node's distanceSoFar.
   -calculate it each time by seeing how many previous nodes you have to visit before you reach the start 
   (caution this is linear counting but based on distance to start, not based on total nodes in most cases)

+When setAStar is true, the maze includes the distanceSoFar when calculating the distance variable for each constructed node. 

Sample maze that tests A* versus Best First:  (best first goes the long way)

#########
#     S##
# ####  #
# ##### #
#   ### #
# #  E# #
#  ## #
##     ##
#########





2018-05-09 PriorityQueue

posted May 9, 2018, 6:16 AM by Konstantinovich Samuel

Priority Queue Class: (estimated work time: 2 days + 1 day to integrate with Maze Solver)

This is a good demo for different pathfinding algorithms:

New Class: Priority Queue.

We will use a heap to store data. The data needs to have a priority associated with it.
Removing by highest/lowest priority will ensure nodes are processed by priority.

Why are we doing this?

By making a frontier that processes nodes by smallest distance, we can make a greedy maze solver!

Best-First Search:
Instead of choosing the 1st node added, or last node added,
Choose the node from the frontier that is closest to the goal.




Lab (extension of the frontier maze solver): 
//Locations need to have an extra field that must be added to the constructor
//This is used in the compareTo() function
public class Location implements Comparable<Location>{
    private double distance;
       
}

public class FrontierPriorityQueue implements Frontier{
    //min heap of Locations.
    private MyHeap<Location> data;
}



2018-05-04

posted May 3, 2018, 9:12 PM by Konstantinovich Samuel



Frontier Maze Solver


The TEXT DESCRIPTION BELOW trumps the image.

Some of the fields are wrong, but the main idea is correct. I will remake the diagram later.
For now remember: The TEXT DESCRIPTION BELOW trumps the image.

To maximize productivity, here is a starting point for your maze solver: Get to work on this, hopefully by Tuesday you have a working super simple solver. 


1. Frontier interface

public interface Frontier{
  public Location next();
  public void add(Location n);
  public boolean hasNext();
}


2. Location (see image) 

public class Location{
    private int x,y;
    private Location previous;

    public Location(int _x, int _y, Location prev){
    }
}
Methods: 
  -accessors as needed

Later:
We can make it implement Comparable<Location>



3. FrontierQueue - implements Frontier
       Store a Queue instance variable (or deque)


4. FrontierStack - implements Frontier
       Store a Stack instance variable (or deque)


5. MazeSolver : For now solve, toString, constructor

public class MazeSolver{
  private Maze maze;
  private Frontier frontier;

  public MazeSolver(String mazeText){
    
  }

  //Default to BFS
  public boolean solve(){ return solve(0); }

  //mode: required to allow for alternate solve modes.
  //0: BFS
  //1: DFS
  public boolean solve(int mode){
    //initialize your frontier
    //while there is stuff in the frontier:
    //  get the next location
    //  process the location to find the locations (use the maze to do this)
    //  check if any locations are the end, if you found the end just return true!
    //  add all the locations to the frontier
    //when there are no more values in the frontier return false
    return false;
  }

  public String toString(){
    return maze.toString();
  }
}


6. Maze : Collaborate on a toStringColor() method!

public class Maze{
  private Location start,end;
  private char[][] board;

  public Maze(String mazeText){
  }

  // '#' - wall 
  // ' ' - open space
  // '?' - frontier space
  // '.' - visited space
  // 'E' - end space (do not replace this)
  // '@' - part of solution
  // 'S' - starting space (do not replace this)
  public String toString(){
  }
   
  // Work on this method as a group! 
  public String toStringColor(){
  }

  //return a list of Locations that are:
  // adjacent to n and  not visited
  // all the Locations in this list should have their previous set to n.
  public Location[] getNeighbors(Location n){
    return null;
  }

  public Location getStart(){
    return null;
  }

  public Location getEnd(){
    return null;
  }



}




LATER: FrontierPriorityQueue - implements Frontier
      This is just your Priority queue that we have yet to write!






Here is a more robust Maze class. You still need to write some methods. Read through it carefully. 

import java.io.*;
import java.io.FileNotFoundException;
import java.util.*;
public class Maze{
  private static final String CLEAR_SCREEN =  "\033[2J";
  private static final String HIDE_CURSOR =  "\033[?25l";
  private static final String SHOW_CURSOR =  "\033[?25h";
  Location start,end;
  private char[][]maze;



  /*
  YOU MUST COMPLETE THIS METHOD!!!
  YOU MUST COMPLETE THIS METHOD!!!
  YOU MUST COMPLETE THIS METHOD!!!
  */
  public Location[] getNeighbors(Location L){
    return null;
  }

  public Location getStart(){
    return start;
  }
  public Location getEnd(){
    return end;
  }


  private static String go(int x,int y){
    return ("\033[" + x + ";" + y + "H");
  }
  private static String color(int foreground,int background){
    return ("\033[0;" + foreground + ";" + background + "m");
  }

  public void clearTerminal(){
    System.out.println(CLEAR_SCREEN+"\033[1;1H");
  }
  public Maze(String filename){
    ArrayList<char[]> lines = new ArrayList<char[]>();
    int startr=-1, startc=-1;
    int endr=-1,endc=-1;
    try{
      Scanner in = new Scanner(new File(filename));
      while(in.hasNext()){
        lines.add(in.nextLine().toCharArray());
      }
    }catch(FileNotFoundException e){
      System.out.println("File not found: "+filename);
      System.exit(1);
    }
    maze = new char[lines.size()][];
    for(int i = 0; i < maze.length; i++){
      maze[i]=lines.get(i);
    }
    for(int r=0; r<maze.length;r++){
      for(int c=0; c<maze[r].length;c++){
        if(maze[r][c]=='S'){
          if(startr == -1){
            startr=r;
            startc=c;
          }else{
            System.out.println("Multiple 'S' found!");
            System.exit(0);
          }
        }

        if(maze[r][c]=='E'){
          //erase E
          //maze[r][c]=' ';
          if(endr == -1){
            endr=r;
            endc=c;
          }else{
            System.out.println("Multiple 'E' found!");
            System.exit(0);
          }
        }
      }
    }
    if(startr == -1 || endr == -1){
      System.out.println("Missing 'S' or 'E' from maze.");
      System.exit(0);

    }

    /*
    THIS IS AN IMPORTANT PART BECAUSE YOU WILL NEED TO CHANGE IT LATER!
    The start/end Locations may need more information later when we add
    other kinds of frontiers!
    */
    end = new Location(endr,endc,null);
    start = new Location(startr,startc,null);
  }

  public String toStringColor(){
    return toStringColor(50);
  }

  public String toStringColor(int delay){
    try{
      Thread.sleep(delay);
    }catch(InterruptedException e){

    }
    return HIDE_CURSOR+CLEAR_SCREEN+go(1,1)+colorize(toString())+SHOW_CURSOR;
  }

  public String toString(){
    int maxr = maze.length;
    int maxc = maze[0].length;
    String ans = "";
    for(int i = 0; i < maxr * maxc; i++){
      int row = i/maxc;
      int col = i%maxc;

      char c =  maze[row][col];
      ans+=c;
      if( col == maxc-1 ){
        ans += "\n";
      }

    }
    return ans + "\n";
  }

  public char get(int row,int col){
    return maze[row][col];
  }
  public void set(int row,int col, char n){
    maze[row][col] = n;
  }
  public static String colorize(String s){
    String ans = "";
    Scanner in = new Scanner(s);
    while(in.hasNext()){
      String line ="";
      for(char c : in.nextLine().toCharArray()){
        if(c == '#'){
          line+= color(37,47)+c;
        }
        else if(c == '@'){
          line+= color(33,40)+c;
        }
        else if(c == '?'){
          line+= color(37,42)+c;
        }
        else if(c == '.'){
          line+= color(36,40)+c;
        }
        else if(c == ' '){
          line+= color(35,40)+c;
        }else{
          line+=color(37,40)+c;
        }

      }
      ans += line+color(37,40)+"\n";
    }
    return ans;
  }
}


2018-05-02 Maze Frontier

posted May 2, 2018, 10:20 AM by Konstantinovich Samuel

Reminder:
Practice Exam 2, bring in on Monday.

Exam next week (Friday):
  multiple choice only
  general java stuff (studied already for the AP)
  Stacks, Queues, Trees, Heaps  

Goal: Frontier Based Maze Solver

Frontier: a list of yet-to-be-explored locations. 
  You can add to the frontier, or get (and remove) the next element. 

Q
How does the frontier grow in the maze solver we wrote before?
What locations are added to this frontier, and what order are they processed?

Example:

s _ _ _ _

_ # # # e

_ _ _ # _

_ # _ # _

_ _ # # _

_ A B C D

E # # # F

G H I # J

K # L # M

N O # # P

Our frontier was treated like a ______.




How does a frontier solver work?

done = false
Initialize your frontier with the starting node
while not done and not empty:
   get next node from the frontier
   if you found the end:
       done = true
   else: 
       process that node (which adds new nodes to the frontier)
if done:
   you solved it
else:
   no solution



Q
How can we change the way the frontier is processed?
Instead of a ____ we can use a ____

What would happen if we did this?
Draw the sample maze:

_ A B C D

E # # # F

G H I # J

K # L # M

N O # # P

Try the alternate form of the frontier. What is the resulting pattern?

Now we must design a data structure to have the ability to process nodes in 2 different ways.
What java construct allows a single set of methods to behave in different ways?

HW: Design the UML diagram for this maze solver.







Preliminary Results up to 8:
Lab 8: less than 8 with no fails means your add end / beginning was non-constant.

OSIS PASS / 46 FAIL / 46 05PASS 05FAIL 05#lin 06PASS 06FAIL 06#lin 07PASS 07FAIL 07#lin 08PASS 08FAIL 08#lin
208652602 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208824680 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208817148 46 0 20 0 23 10 0 11 10 0 11 6 0 7
211521372 46 0 20 0 23 10 0 11 10 0 11 6 0 7
213149834 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209314327 46 0 20 0 23 10 0 11 10 0 11 6 0 7
214700411 46 0 20 0 23 10 0 11 10 0 11 6 0 7
214586992 46 0 20 0 23 10 0 11 10 0 11 6 0 7
214269698 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209062025 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209180272 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208974055 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209563600 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208979344 46 0 20 0 23 10 0 11 10 0 11 6 0 7
236729943 46 0 20 0 23 10 0 11 10 0 11 6 0 7
236929352 46 0 20 0 23 10 0 11 10 0 11 6 0 7
219403144 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209343813 46 0 20 0 23 10 0 11 10 0 11 6 0 7
241802008 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209908870 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209152545 46 0 20 0 23 10 0 11 10 0 11 6 0 7
231851098 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209767730 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208891606 46 0 20 0 23 10 0 11 10 0 11 6 0 7
214521304 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209729425 46 0 20 0 23 10 0 11 10 0 11 6 0 7
215543406 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208313379 44 0 20 0 4077 8 0 9 10 0 11 6 0 7
208393082 44 0 20 0 23 10 0 11 10 0 11 4 0 5
209381243 44 0 20 0 23 8 0 9 10 0 11 6 0 7
209319474 44 0 20 0 23 8 0 9 10 0 11 6 0 7
208544494 43 0 20 0 23 10 0 11 10 0 11 3 0 4
209167725 43 0 19 0 22 8 0 9 10 0 11 6 0 7
207695149 43 1 20 0 23 8 0 9 10 0 11 5 1 7
209489475 42 2 18 2 23 10 0 11 10 0 11 4 0 5
208992594 41 0 15 0 18 10 0 11 10 0 11 6 0 7
233536242 40 2 19 1 23 10 0 11 10 0 11 1 1 4
208709410 40 0 20 0 23 10 0 11 10 0 11 0 0 1
207519570 38 0 20 0 23 8 0 9 10 0 11 0 0 1
209262609 38 6 14 6 23 8 0 9 10 0 11 6 0 7
209725308 36 4 16 4 23 10 0 11 4 0 5 6 0 7
214592685 36 0 20 0 23 10 0 11 0 0 1 6 0 7
209682293 36 0 20 0 33 10 0 11 0 0 1 6 0 7
215062944 33 3 10 0 13 10 0 11 10 0 11 3 3 7
208719062 31 13 10 10 23 8 0 9 10 0 11 3 3 7
209343888 31 4 16 4 23 10 0 11 0 0 1 5 0 6
211671136 30 0 20 0 23 2 0 3 2 0 3 6 0 7
208942532 26 0 0 0 3 10 0 11 10 0 11 6 0 7
209322718 22 22 2 18 23 10 0 11 4 4 9 6 0 7
209180512 19 9 11 9 23 2 0 3 0 0 1 6 0 7
207142159 12 4 0 0 3 4 4 9 2 0 3 6 0 7
214466500 12 17 2 17 22 0 0 316 10 0 11 0 0 1
208356410 10 20 1 19 23 0 0 1 8 0 9 1 1 4
213463227 10 0 0 0 3 10 0 11 0 0 1 0 0 1
208781666 3 0 0 0 3 0 0 1 2 0 3 1 0 2
209028257 3 0 0 0 3 0 0 1 2 0 3 1 0 2
209046838 1 0 0 0 3 0 0 1 0 0 1 1 0 2
206939092 0 0 0 0 3 0 0 1 0 0 1 0 0 1
208791855 0 0 0 0 3 0 0 1 0 0 1 0 0 1
214377137 0 0 0 0 3 0 0 1 0 0 1 0 0 1

2018-05-01

posted May 1, 2018, 9:55 AM by Konstantinovich Samuel

Running median lab!

13Medians/
RunningMedian.java
  -RunningMedian() - makes an empty container for Doubles.
  -void add(Double) - insert a Double into the data structure.
  -Double getMedian() - return the current median, throws NoSuchElementException when size is 0.
  -int size()
  

2018-04-30

posted Apr 29, 2018, 8:07 PM by Konstantinovich Samuel   [ updated May 1, 2018, 9:52 AM ]

Before you fill out the request for a college rec
0. Recognize that I am looking at your performance in my class but need more than just numbers. If you are a silent student that scores well and nothing else, it is difficult to write a rec. 
1. You should be looking to major in CS or closely related field. This is only flexible if you had me for more than 1 year of classes. 
2. You should be comfortable communicating with me - because I will be interviewing a large subset of the people I will write recs for. 
3. Recognize that you will be spending more time writing a much more in-depth response later. (By mid summer!)

College Reccommendation request form:
https://goo.gl/forms/f0L4qmLW40BmF8j03




Given a group of numbers spoken out loud, it is easy to determine the max/min. This is because you only need 1 pass to calculate the max, and you can do this as the numbers are being read. If you don't read the numbers too quickly a person can actually remember both the max and the min, but that is a little tricky.

The median is not an element that you can calculate using this method because you need to keep track of all of the values.

1) What is an algorithm to calculate a median that you can do with almost 0 extra coding time?
2) Now think of a more efficient algorithm to calculate a median. Discuss with neighbors.



2018-04-26

posted Apr 25, 2018, 4:16 PM by Konstantinovich Samuel   [ updated Apr 30, 2018, 9:56 AM ]

Please Vote on the 15 different websites of my intro classes!
Just grade on style not on the actual content (don't read and base your rating on what they like)
(rate each one from 1-5, and give a 6 to whichever you think is the best)
https://goo.gl/forms/VYuOsyutL5iPudeo1

/12/MyHeap.java
You are writing a heap of Strings, you can always change it to a generic later.

 Constructors
 -MyHeap() - construct empty max heap
 -MyHeap(boolean) - true: construct empty max heap, false: construct empty min heap.
 Methods
 -void add(String s)
 -String remove()
 -String peek()
 -int size()

For generic comparables see this demo code: (let me know if there is anything more needed for the conversion to a generic.)



public class test<T extends Comparable<T>>{

        private T[] data;

        @SuppressWarnings("unchecked")
        public test(){
            data = (T[])new Comparable[10];

        }

        public void add(T value){
         data[0] = value;
        }
}

1-10 of 46