Courses‎ > ‎AP Computer Science 2‎ > ‎

Konstantinovich

2017-04-27

posted Apr 27, 2017, 6:13 AM by Samuel Konstantinovich   [ updated Apr 27, 2017, 11:21 AM ]

The height of the tree minimally log n. Ideally we can maintain the minmum height.

To add a node the the runtime is O(height) which is between O(log n) O(n).



How do we print these trees? 


Traversals!

Tree Transversals - O(n)

Tree Traversals:   (V=Value, CL=Left Child, CR=Right Child)

VCLCR  (Pre-Order)

CLCRV   (Post-Order)

CLVCR   (In-Order)


a pre-order traversal, of the following tree:
     a
   /   \   
   b     c
    \   /  
     f  e

a b _1 f _2 _3 c e _4 _5 _6   
(where _x signifies no child)
_1 is the left child of b
_2 and _3 are the children of f
_4 and _5 are the children of e
_6 is the right child of c


DO NOW:
Test your expression tree code!

Here is the ExpressionTree class, just drop in your methods from yesterday, compile and run.


public class ExpressionTree{
  
  /*return the value of the specified expression tree*/
  public double evaluate(){
    /*you are to write this method*/
    return 0.0;
  }
  
  /*return the expression as an infix notation string with parenthesis*/
  /* The sample tree would be: "( 3 + (2 * 10))"     */
  public String toString(){
    /*you are to write this method*/
    return "";
  }
  
  /*return the expression as a postfix notation string without parenthesis*/
  /* The sample tree would be: "3 2 10 * +"     */
  public String toStringPostfix(){
    /*you are to write this method*/
    return "";
  }
  
  /*return the expression as a prefix notation string without parenthesis*/
  /* The sample tree would be: "+ 3 * 2 10"     */
  
  public String toStringPrefix(){
    /*you are to write this method*/
    return "";
  }
  
  
  
  
  
  
  private char op;
  private double value;
  private ExpressionTree left,right;
  
  /*TreeNodes are immutable, so no issues with linking them across multiple
  *  expressions. The can be constructed with a value, or operator and 2
  * sub-ExpressionTrees*/
  public ExpressionTree(double value){
    this.value = value;
    op = '~';
  }
  public ExpressionTree(char op,ExpressionTree l, ExpressionTree r){
    this.op = op;
    left = l;
    right = r;
  }
  
  
  
  public char getOp(){
    return op;
  }
  
  /* accessor method for Value, precondition is that isValue() is true.*/
  private double getValue(){
    return value;
  }
  /* accessor method for left, precondition is that isOp() is true.*/
  private ExpressionTree getLeft(){
    return left;
  }
  /* accessor method for right, precondition is that isOp() is true.*/
  private ExpressionTree getRight(){
    return right;
  }
  
  private boolean isOp(){
    return hasChildren();
  }
  private boolean isValue(){
    return !hasChildren();
  }
  
  private boolean hasChildren(){
    return left != null && right != null;
  }
  
  
  public static void main(String[] args){
    //ugly main sorry!
    ExpressionTree a = new ExpressionTree(4.0);
    ExpressionTree b = new ExpressionTree(2.0);

    ExpressionTree c = new ExpressionTree('+',a,b);
    System.out.println(c);
    System.out.println(c.toStringPostfix());
    System.out.println(c.toStringPrefix());
    System.out.println(c.evaluate());

    ExpressionTree d = new ExpressionTree('*',c,new ExpressionTree(3.5));
    System.out.println(d);
    System.out.println(d.toStringPostfix());
    System.out.println(d.toStringPrefix());
    System.out.println(d.evaluate());

    ExpressionTree ex = new ExpressionTree('-',d,new ExpressionTree(1.0));
    System.out.println(ex);
    System.out.println(ex.toStringPostfix());
    System.out.println(ex.toStringPrefix());
    System.out.println(ex.evaluate());

    ex = new ExpressionTree('+',new ExpressionTree(1.0),ex);
    System.out.println(ex);
    System.out.println(ex.toStringPostfix());
    System.out.println(ex.toStringPrefix());
    System.out.println(ex.evaluate());

    ex = new ExpressionTree('/',ex,new ExpressionTree(2.0));
    System.out.println(ex);
    System.out.println(ex.toStringPostfix());
    System.out.println(ex.toStringPrefix());
    System.out.println(ex.evaluate());
    
    
  }
  
}

2017-04-26 Expression Tree

posted Apr 26, 2017, 6:09 AM by Samuel Konstantinovich   [ updated Apr 26, 2017, 6:19 AM ]

Solution to eval: (without the isOp, or perform methods)

public static double eval(String s){
    String[] tokens = s.split(" ");
    Stack<Double> values = new Stack<Double>();
    
    for(String token : tokens){
      if(isOp(token)){
       	 values.push(perform(token,values.pop(),values.pop()));
      }
      else{
        values.push(Double.parseDouble(token));
      }
    }
    
    return values.pop();
}


Equivalent infix, postfix, and prefix expressions:
(((5.0 + 2.0) * 3.33) - 1.0)
5.0 2.0 + 3.33 * 1.0 -
- * + 5.0 2.0 3.33 1.0



/*This expression tree is a binary tree that represents
an arithmetic expression. The results are always doubles,
no int operations nor booleans/strings etc.
-Example:
  +
 / \
3   *
  /  \
 2   10
- Any node with children is treated like an operator.
- Any node without children is treated like a value.

Assumptions that can be made:
- A TreeNode has 0 or 2 children.
- A TreeNode with children must have an operator.
- For now all operators are binary and are one of these: '+', '-', '*', '/'.
*/

public class ExpressionTree{
  /*instance variables, constructors, and some methods not shown*/
  
  /*accessor method for the value, precondition is that isValue() is true.*/
  private double getValue(){    /*implementation not shown*/ }
  /*accessor method for the operation, precondition is that isOp() is true.*/
  private char getOp(){    /*implementation not shown*/  }    
  /* accessor method for left, precondition is that isOp() is true.*/
  private ExpressionTree getLeft(){    /*implementation not shown*/  }
  /* accessor method for right, precondition is that isOp() is true.*/
  private ExpressionTree getRight(){    /*implementation not shown*/  }

  private boolean isOp(){    /*implementation not shown*/  }
  private boolean isValue(){    /*implementation not shown*/  }


  /* you write these four methods, hint: think recursively */

  /*return the expression as an infix notation string with parenthesis*/
  /* The sample tree at the top would be: "( 3 + (2 * 10))"     */
  public String toString(){    /*you are to write this method*/  }

  /*return the expression as a postfix notation string without parenthesis*/
  /* The sample tree would be: "3 2 10 * +"     */
  public String toStringPostfix(){    /*you are to write this method*/  }

  /*return the expression as a prefix notation string without parenthesis*/
  /* The sample tree would be: "+ 3 * 2 10"     */
  public String toStringPrefix(){    /*you are to write this method*/  }

  /*return the value of the expression tree*/
  public double evaluate(){    /*you are to write this method*/  }

}

2017-04-25

posted Apr 25, 2017, 6:21 AM by Samuel Konstantinovich   [ updated Apr 25, 2017, 6:21 AM ]

Classwork: Go over AP materials.

Tomorrow: Do in class a tree based free response style problem

2017-04-24 Trees + HW11

posted Apr 24, 2017, 5:09 AM by Samuel Konstantinovich   [ updated Apr 26, 2017, 6:21 AM ]

Please make sure you put your stack calculation homework in the correct folder with the proper class name:
11StackCalculations/StackCalc.java

If you make a driver file with the following main, it should work:
public static void main(String[] args)
{
    System.out.println(StackCalc.eval("10 2 +"));//12.0
    System.out.println(StackCalc.eval("10 2 -"));//8.0
    System.out.println(StackCalc.eval("10 2.0 +"));//12.0
    System.out.println(StackCalc.eval("11 3 - 4 + 2.5 *"));//30.0
    System.out.println(StackCalc.eval("8 2 + 99 9 - * 2 + 9 -"));//893.0
    System.out.println(StackCalc.eval("10 2 + 10 * 1 + 1 1 1 + + + 10 10 + -"));//104.0
}


Goal: Trees

Graph: a relational data structure that stores points of interest and the relationships between them (nodes and edges)
The edges are pairs of nodes.
-Some graphs the edges are one way (directed graph) 
-Some graphs the edges have an additional value or weight (weighted graph)
-Directed graphs can have different weights in each direction.

A linked list is a graph
A maze can be represented by a graph. Adjacent spaces have an edge between them.

Tree: an acyclic graph.

Breadth First Search vs. Depth First Search

Depth-First Search

-Tests all possibilities in one path until it needs to backtrack. This is the recursively backtrack you have written for your previous assignments (until now!)

-Does not guarantee shortest path / closest value.

(Visually DFS goes to bottom of a tree, then backtracks, etc.)


Breadth-First Search

BFS checks the first node, then its direct children, then the children of those. Tests all possibilities in order from the closest possibility to the furthest.

This will find the closest matching value or shortest path to a goal.

(Visually BFS will check the next level of the tree, then the next level... etc)

687474703a2f2f7777772e6373652e756e73772e6564752e61752f7e62696c6c772f4a757374736561726368312e676966.gif






Maze example:


# 0 1 2 3 4

0 S _ _ _ _

1 _ # # # _

2 _ _ _ # _

3 _ # _ # _

4 _ _ _ # E

Lets label the spaces we want to go to make our lives easier!

# 0 1 2 3 4

0 S a b c d

1 e # # # f

2 g h i # j

3 k # l # m

4 n o p # q


BFS:
check
a,e on the 1st pass
b,g on the 2nd pass
c,h,k on the 3rd pass
d,i,n on the 4th pass
f,l,o on the 5th
p,j on the 6th
m on the 7th
q on the 8th.


or:

0 1 2 3 4

1 # # # 5

2 3 4 # 6

3 # 5 # 7

4 5 6 # 8

2017-04-20 Post Fix

posted Apr 20, 2017, 7:18 AM by Samuel Konstantinovich   [ updated Apr 20, 2017, 9:21 AM ]

What is/isn't on the AP:

Quick Reference: (1st page only!)


GOAL: Evaluate a post fix expression

Evaluate an arbitrary postfix expression. Assume all results are doubles (do not have to preserve int when you run an operation on two ints)

valid numbers:
any int or double.

valid operators: (all binary)
+
-
*
/
%

All values and operators are separated by a single space:
"10 2.0 +"
"11 3 - 4 + 2.5 *"
"8 2 + 99 9 - * 2 + 9 -"

Write the eval(String) method, that will correctly evaluate a post-fix expression.

eval("10 2.0 +") is 12.0
eval("11 3 - 4 + 2.5 *") is 30.0
eval("8 2 + 99 9 - * 2 + 9 -") is 893.0


1. Convert your string into tokens. (A list of values and operators)
1b. Test this by printing each one!
2. Instead of printing each one, decide what to do with them... using a stack!



2017-04-19 HW

posted Apr 19, 2017, 6:55 AM by Samuel Konstantinovich

AP baron's review book: (an older one for more practice questions!)

In school:

Outside of school:
google this, and it will be the 2nd result:  
ap computer science baron's book pudaloff

Regarding the AP:
We will do some AP review! 
We are not focussing on AP review. If you want to do your best, you must do a significant amount of review on your own.
The AP Exam always has simple solutions to the coding section, keep it simple, don't over-engineer solutions.
Review your AP documentation, what is/isn't on the exam.
I strongly recommend you read through any new-ish baron's book if you haven't done so. The old ones are fine, but may have slightly out of date class definitions.
As always: there is no grid world! Ignore it.


For AP Practice Multiple choice Questions: 
- Time yourself! 
- Write all of your choices, and any scrap work you did on looseleaf. 
- Try to do it in 2 sittings giving yourself the correct amount of time total. 
- Go over the solutions after. Put a STAR next to questions you need to discuss in class. Write a note about why you were confused.

Homework: (Due Tuesday April 25th - Discussion day for any AP questions)
Diagnostic Exam A ( Starts on PDF page 19)
Multiple Choice Questions 1-33  (34-40 are not on the AP and not part of this class)

Homework: (Due next Friday April 28  but you can start working on it if you have time)
Practice Exam 3 (starts on PDF page 627)
Multiple Choice Questions 1-34  (35-40 are not on the AP and not part of this class)

2017-04-07 HW10

posted Apr 6, 2017, 7:48 PM by Samuel Konstantinovich   [ updated Apr 12, 2017, 5:55 AM ]

MODIFICATION!
(I changed my mind to make you do fewer but more meaningful assignments)

The Deque will be the next assignment to save time and because making a stack and queue first would be too easy, especially if you can use the built-in LinkedList. 
We will skip them to save time. Instead, you will work on a Deque of Strings.

10Deque/MyDeque.java
  - Due Monday, April 24th. This is not too bad if you followed the Deque in class. 



You need to know the idea of a stack and a queue but can use one class to act as either of them.
The Deque class is basically a replacement for the Queue and can be used as a Stack as well. 

-This interface extends the Queue interface. When a deque is used as a queue, FIFO (First-In-First-Out) behavior results.
Elements are added at the end of the deque and removed from the beginning.

-Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.
When a deque is used as a stack, elements are pushed and popped from the beginning of the deque. 

-You are making a resizeable deque. There is no maximum capacity. This removes the need for several exceptions.

-You are writing a circular array based representation of this class:
    Keep track of a front and back indices.
    Add to the back, remove from the front.
    When you reach the end of the array, wrap around. The modulus operator is helpful for helping keep your indices in bounds.
    When you fill the entire circular array, double the capacity, and copy the old values over. Don't forget to update the front and back indices.

    Here are some examples of a partially full circular array deque: 


You will be writing an array-based implementation of a Deque of Strings. Use this reference for more specific info about the methods.

Required methods + their exceptions

The add methods:
These will add the element to the specified side. The deque will double capacity if there is no space left.
void addFirst(String)
void addLast(String)
Throws: (this is a subset of the real deque)
NullPointerException - if the specified element is null and this deque does not permit null elements

The remove methods:
These will retrieve and remove the element from the specified side.
String removeFirst()
String removeLast()
Throws:
NoSuchElementException - if this deque is empty

The get methods:
These will retrieve but not remove the element from the specified side.
String getFirst()
String getLast()
Throws:
NoSuchElementException - if this deque is empty

2017-04-06

posted Apr 5, 2017, 6:01 PM by Samuel Konstantinovich   [ updated Apr 6, 2017, 7:46 PM ]

To learn about or sign up for PClassic: 

You can also try some of the problems here:


Goal: How to make Fat Stacks

New topics: Stacks and Queues
The class notes and diagrams were on Stacks + Queues

also:
-Java will automatically convert Integer to int and vice versa.
-Wrapper classes such as Integer are immutable.

2017-04-05

posted Apr 5, 2017, 7:12 AM by Samuel Konstantinovich   [ updated Apr 5, 2017, 11:22 AM ]


Both  LinkedLists and ArrayLists can be used with the for each loop:

//SomeList can be any type that implements iterable<T>
SomeList<Integer> listThing = new SomeList<Integer>();
for( Integer i : listThing ){
  //do something with i
}

We need to make our MyLinkedLists implement Iterable.
This means we need to make our MyLinkedList have an Iterator function that returns an Iterator<Integer>


Our iterator should use the properties of a linked list to iterate in linear time. DO NOT use index based iteration, or you will get O(n^2) time to iterate through the linked list.

Final requirements for 09LinkedLists:
-Doubly Linked
-Iterable
-All the public methods posted yesterday
-Due Thurs after break

2017-04-04

posted Apr 4, 2017, 11:25 AM by Samuel Konstantinovich   [ updated Apr 4, 2017, 11:25 AM ]

import java.util.*;
public class MyLinkedList{

  private class LNode{
    LNode next,prev;
    int value;
    public LNode(int value){
      this.value=value;
    }
    public String toString(){
      return value+"";
    }
  }

  LNode head,tail;
  int size;

  public MyLinkedList(){
  }

  public int size(){
    return size;
  }

    
  private LNode getNthNode(int n){/*complete this*/}

  private void addAfter(LNode location, LNode toBeAdded){/*complete this*/  }
private void remove(LNode target){/*complete this*/}

  public String toString(){ /*complete this*/  }

  public boolean add(int value){  /*complete this*/ }
public int get(int index){/*complete this*/}

  public int set(int index, int value){/*complete this*/}

  public int indexOf(int value){/*complete this*/}
public int remove(int index){/*complete this*/}
public void add(int index,int value){/*complete this*/}

}

1-10 of 33