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

#### 2016-05-13

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

#### 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