Courses‎ > ‎AP Computer Science 2‎ > ‎Platek‎ > ‎

Homework

37. Due Thurs. 5/25
    1 - Exam #5 : 5/26
           - Priority Queues and Hash Tables
     2 - Review Labs/HashTables/HashTable.java
          UPDATE: Assume the entries (keys) in the Hash Table are unique.
          Complete the remove(int) method.


36. Due Wed. 5/24
     - Exam #5 : 5/26
     1. UPDATE ON THE HOMEWORK ASSIGMENT
        Write a program to implements a hash table of integers which resolves
        collisions with linear probing. Use Integer objects.

      Have the user determine the size of the table(array).
       HashTable ht = new HashTable(M);
       // stores N integers (N < M)
    
      Use the hash function: hash(key) = key % M      
 
       Implement: 
                           // Assume there is room for the new key.    
                   (A)    public void add(key) 
                              // hashes the key to a position i in the array.
                              // if position i is unoccupied, then key is placed at the position i
                             //  otherwise keep checking adjacent positions (i+1, i+2, ...), wrapping around if necessary.
                             
     (B)   public int  find(key) 
                            // returns the position of key  or -1 if not found .
                            // Use this algorithm: hash the key to position i, if the key is found return i
                            // otherwise, search adjacent positions until you find the key or an empty cell.
                            // if you encounter an empty cell return -1.

     

35. Due Thurs. 5/18
      1. Write the removeMin() method that removes the minimum value from 
         a list that has heap property. Test it in Demo_II.java.

          // O(log N)
          // precondition: the minimum value is at index 0.
          public static Integer removeMin(ArrayList<Integer> heap){   }

      2. Write the Comparator StringLengthComparator to order strings by their lengths.
         The shortest string will be the least element and thus have the highest priority
         in the priority queue. Test your work in DemoComparator.java

Here's  the desired output:

output:
======

add: apple      pq: [apple]
add: banana     pq: [apple, banana]
add: watermelon pq: [apple, banana, watermelon]
add: pear       pq: [pear, apple, watermelon, banana]
add: grapes     pq: [pear, apple, watermelon, banana, grapes]
add: cantalope  pq: [pear, apple, cantalope, banana, grapes, watermelon]
add: orange     pq: [pear, apple, orange, banana, grapes, watermelon, cantalope]
add: kiwi       pq: [pear, kiwi, orange, apple, grapes, watermelon, cantalope, banana]

remove: pear    pq : [kiwi, apple, orange, banana, grapes, watermelon, cantalope]
remove: kiwi    pq : [apple, banana, orange, cantalope, grapes, watermelon]
remove: apple   pq : [banana, grapes, orange, cantalope, watermelon]
remove: banana  pq : [grapes, cantalope, orange, watermelon]
remove: grapes  pq : [orange, cantalope, watermelon]
remove: orange  pq : [cantalope, watermelon]
remove: cantalope       pq : [watermelon]
remove: watermelon      pq : []
 


34. Due Wed. 5/17
     - Review : Demo.java and Demo_II.java located in Labs /PriorityQueue/
      - Here is the update removal algorithm.
        Remove Algorithm:    
        =================
        Assume the minimum value is at the root and all removals occur at the root.

          Steps to remove v from the heap:
            1. If the size of the heap is 1 then remove v and Stop.
            2. Remove the rightmost child of the last level, x, then replace v with x.
            3. If x is a leaf or x <= than its children then Stop.
            4. Swap x with its smallest child.
            5. Goto step 3.
     - Draw the tree after removing 3 from the heap

                3
              /   \
            4     7
            / \    / \
       5   10 8   11
      / \
     9   8


33. Due. Wed. 5/10
      - Exam 5/12 (Binary and Binary Search Trees).
      - Review the updated files: TreeNode.java and BST.java
      - Complete question #5 in BST.java.
            - See our ArrayList implementation for guidance.

32. Due. Tues., 5/9
    - Exam 5/12
    - Review BST.java
    - Complete question #4 in BST.java

31. Due. Mon. 5/8
      - Exam 5/12
      - Review the file : /Labs/Trees/BST.java
      - Complete  questions 1 - 3 in BST.java.

30. Due. Thurs 5/4
     - Exam 5/12
     - Implement the BST insertion algorithm within the insertNode(TreeNode<E>) method in BST.java.
      
29. Due. Wed. 5/3
     - complete #3 in Labs/Trees/Lab01.txt
28. Due Thurs. 4/27
     - complete the function :
                  // You must use rowSum(int [ ] [ ]) in your solution.
                  public static boolean isDiverse(int [ ][ ] arr2D) { }

27. Due Wed. 4/26
     - Review LinkedList.java
     - Study for Ap.
26. Due Mon. 4/24
     - Review Labs/Iterators/ArrayList.java
     - Think about implementing the remove method of the ListIterator class.
25. Due Wed. 4/19
         - Complete the StackQ class. (Use 2 queues to implement a stack.)
**************************************************************************************************************************************************************************
     Follow this link https://goo.gl/OVkPBr or this link clyde.stuy.edu/~ygenkina/Pclassic.html to learn about or sign up for PClassic. The form will stop accepting responses on April 17th. Sign up ASAP.
**************************************************************************************************************************************************************************
24. Due Thurs. 4.5
       - Review ArrayQueue.
       - Write the toString method for ArrayQueue.
23. Due Wed. 4/4
       - Review NodeQueue.java
       - Design and Build ArrayQueue.
22. Due Mon., 4/3
      Complete the takeAll(DLinkedList<E> rhs) method. It should be on the order of O(1).
21. Due Fri., 3/31

      Exam #3 : 3/31  - Stack.java, ArrayStack.java, DoublingArrayStack.java, DNode.java, DLinkedList.java

20. Due Thurs. 3/30
       Exam #3 : 3/31  - Stack.java, ArrayStack.java, DoublingArrayStack.java, DNode.java, DLinkedList.java
     Review DLinkedList.java
     Complete the methods:  remove(DNode<E>), removeFirst(), removeLast(), remove(int).
19. Due Wed 3/28
     Exam #3 : 3/31  - Stack.java, ArrayStack.java, DoublingArrayStack.java, DNode.java, DLinkedList.java
     Review DLinkedList.java
     Complete the methods:  addAtrer(DNode<E>, DNode<E>), addFirst(DNode<E>), addFirst(E).
18. Due Mon. 3/27
       *** St. Joseph's Programming competition is on Wed. May 24. 
            Registration is next week.  See Mr. Brooks if you'd like to join
      *****
       Exam Fri. 3/31
       Correct previous exam.
17. Due Fri. 3/24
         Complete the DoublingArrayStack.
         Read Labs/Stack/Infix/InfixCalculator.txt

16. Due: Thurs. 3/23
          Complete questions 1 - 3 in the DoublingArrayStack class.

15.    On Monday, 3/20 at 4pm in room 307, Phillip Compeau, a professor at Carnegie Mellon University will 
       be giving a video talk about 
Computational Biology. The talk should be a primer on Computational Biology, while also
         talking a bit about CMU’s brand new major in that field that they are launching in the fall of 2017. This is going to
         be a good talk and a chance for you to see another potential field in CS.

14. Due. Tues 3/14 - Exam 3/17
                                - Complete the reverse() method from Lab_II.txt.
13. Due Mon. 3/13 - Exam 3/17
                               - Complete the swap(Node, Node) method from Lab_II.txt
12. Due Fri. 3/10 - Review the code  in Labs/LinkedList.
      Write the SLinkedList method append(SLinkedList L) that concatenates two lists in O(n) time.
      Let n be the number of elements in the resulting list.
     Here's an example, 
     S = [ a,b]
     M = [ c,d,e]
     S.append(M) -> [a,b,c,d,e]
     M.append(S) -> [c,d,e,a,b]
     Neither S nor M should be modified (no side effects). 

    public SLinkedList append(SLinkedList L){}



11. Due. Tues. 3/7 - Correct Exams,
                              - Review Labs/Node/LN.java
                              - You will be given time in class tomorrow to work on questions 5 and 6.
10. Due. Mon. 3/6  - Sudy Labs/Node/LN.java
                               - Complete questions 1 - 4 in LN.java
9. Due Thurs 3/2 - Study Labs/Node/Node.java
                            - implement the print() and printReverse() methods of LN.java
8. Due Wed. 3/1 - study Labs/QuickSort/Quick.java 
                           - Answer this question:
                               Under what circumstances would you not use a quick sort? Explain your
                               answer in a written statement.

7. Due Thurs., 2/16 - Exam 2/17 
                                       Topics:  Merge (arrays and lists), MergeSort, SelectionSort, InsertionSort, Partition
                                 - Complete Labs/Partition
6. Due Wed. 2/15 - Exam 2/17
                                  Topics:  Merge (arrays and lists), MergeSort, SelectionSort, InsertionSort, QuickSort.
                               - Review : Labs/Merge/MergeList
                                                Labs/MergeSort/MergeSortArrayR.java
5. Due Tues. 2/14 - Exam 2/17
                             - Review Labs/Merge/Merge.java
                             - Complete Labs/Merge/MergeListLab
4. Due Wed. 2/8 - Exam 2/17
                           - Review the NumToEng,java solution.
                           -  Start the toRoman(int) method of the Roman class.
                               convert the integers from  1 to 20 only.
3. Due Tues 2/7 - Extend NumToEng to include all positive integers. Upto and including Integer.MAX_VALUE.
2. Due Mon. 2/6 - See hw02.txt posted below.
1, Due Thurs. 2/2 - Classwork/HailStone/HailStone.txt (and HailStone.java)
ċ
hw02.txt
(1k)
Rick Platek,
Feb 3, 2017, 11:38 AM
Comments