Mr. Meinzen - Advanced Placement Computer Science - A

"Success is the ability to go from one failure to another with no loss of enthusiasm." Winston Churchill

APCS-A Program Assignment #11 - Intro to Exemplar Lab(s)

  • Download and install/unzip the 3 Exemplar Labs [Magpie, PictureLab, Elevens]
  • Demonstrate the operation of each lab using Eclipse
  • As demonstrated in class, write the UML Class Card (using 3x5 or 4x6 notecards) for each java file in the Lab(s) as specified below.
  • Answer the previous year's Free Response question on the Exemplar Lab(s) (handout from Mr. M)

 

The following UML class diagrams of Mapie Student Activity 5 are to be made:

  • Base class: Magpie5.java

The following UML class diagrams of PictureLab Student Activity are to be made:

  • Base classes: SimplePicture.java; Pixel.java
  • Interfaces & Abstract classes: DigitalPicture.java
  • Testing classes, Implemented Interfaces, GUI, & Realized Abstract classes: PictureTester.java
  • Extended classes: Picture.java

 

The following UML class diagrams of Elevens Student Activity are to be made:

  • Base classes: Card.java; Deck.java

     

NOTE: There are a total of 8 UML class diagrams to be hand-written.

 

APCS-A Program Assignment #12 - Linked List, Stacks, & Queues

 

Based on the Stack and Queue discussed in the lecture notes, write the following classes:

  • Note: "using" could be interpreted as "has a" OR "is a"...clarify with your instructor before programming!
  • Note2: points may be deducted if additional methods are required beyond the list given below.

  1. [5 pts] A ListNode class that takes an Object as its data element
  2. [25 pts] A LinkedList class that uses your ListNode class and has the following methods defined:
    • boolean isEmpty(), Object getFront(), Object getBack(), void addFront(Object), void addBack(Object),
    • String toString() // prints out values of each node consecutively
  3. [2.5 pts] The Stack interfaces that includes:
    • boolean isEmpty(), Object push(Object), Object pop(), Object peek(),
    • int search(Object) // returns position of element on stack, top element = 1 ...return -1 if not found
  4. [2.5 pts] The Queue interfaces that includes:
    • boolean isEmpty(), Object dequeue(), Object enqueue(Object), Object getBack(), Object getFront()
  5. [10 pts] A StackList class that implements the Stack interface using your LinkedList class
  6. [10 pts] A QueueList class the implements the Queue inteface using your LinkedList class
  7. [5 pts] A Driver program that tests both of the StackList and QueueList classes including:
    • public static void main(String a[])
    • an instantiation of each StackList and QueueList classes
    • "add" the following Strings to each list in the following order:
    • "Bill" , "Fred", "Joe" "Henrietta", "Mr. M", "Noman"

    • printout--by using the appropriate method calls to the Lists-- the above names

To be scored out of 60 pts:

ListNode

LinkedList

Interfaces (2)

StackList

QueueList

Driver

Total

 

 

 

 

 

 

 

5

25

5

10

10

5

60

  1. Printout the listing for the above classes and interfaces--use appropriate commenting!
  2. Demonstrate how your driver program works.

APCS-A Program Assignment #13 - Stacks & Queues Problems & Testing

Based on the Stack, Queue, Infix, and Postfix discussed in the lecture notes, answer the following questions:

  1. Evaluate the following Postfix expressions:
    1. 6  4  +  3  *   16  4 / - 
    2. 12  25  5   1 / / * 8  7 + -
    3. 70  14  4  5  15  3 / * - - / 6 + 
    4. 3  5  6 * + 13 - 18  2 / +
  2. Convert the following Infix expressions to Postfix notation:
    1. (A + B) * (C + D) - E
    2. A - (B + C) * D + E / F
    3. ((A + B) /(C - D) + E) * F - G
    4. A + B * (C  + D) - E / F * G + H
  3. Write the equivalent Infix expressions for the following Postfix expressions:
    1. A B * C + 
    2. A B + C D - *
    3. A B - C - D *
  4. Assuming the following expressions are implemented as a Stack, write out the condition of the Stack after each value is "pushed" or operation is "popped" :
    1. 6 4 + 3 * 16  4 / - 
      (Note: 9 different stack diagrams)
    2. 12 25 5 1 / / * 8 7 + - 
      (Note: 11 different stack diagrams)
  5. Write an Expression class that uses a StackList object that pushes any value onto the stack. As well, any operator (*, +, -, /) must pop two values from the stack, compute the result and push the result back onto the stack. Test your Expression class using the two expressions from Question 4. Don't forget to use the toString() method to verify your stack is working correctly.

To be graded:

  1. Handwritten answers to Questions 1-4.
  2. Printout of you Expression class and the results (copy & pasted to bottom) of the toString() method.

APCS-A Program Assignment #14 - Map Assignment

 

Based on the WordFreq program given below, write the following application:

  1. Write your WordFreq.java application and test it in Eclipse.
  2. Use your application on 3 different "inFile.txt" data files as given by your teacher and show the output to your teacher.
  3. Modify the WordFreq.java application to use a TreeMap rather than HashMap and verbally explain how and why the output is different.

 

To be graded:

  1. Printout the listing for the above class--use appropriate commenting!
  2. Printout the output for a TreeMap and HashMap of only ONE of the "inFile".
  3. Demonstrate how your program works and be ready to explain the difference between the output of the HashMap and TreeMap.

 

WordFreq.java Listing

 

public class WordFreq
{
	private Map m;
	public WordFreq()
	{
		m = new HashMap();
		loadMap(m);
		System.out.println(m); // print the values in the map
	}
	public void loadMap(Map m)
	{
		/*code to open the report file called inFile not given*/
		while ( /*there are still words in inFile*/ )
		{
			// readWord() reads one word in...may have to tokenize it
			String work = inFile.readWord();   
			
			// get the value associated with the key word
			Integer i = (Integer) m.get(word); 
			if (i == null) 						// if new word
			{
				// put new word in the map since we�ve seen it once
				m.put(word, new Integer(1)); 	
			}
			else
			{
				// add 1 to the number of times we�ve seen it
				m.put(word, new Integer(i.intValue()+1)); 
			}
		}
	}
} 
 

APCS-A Program Assignment #15 - Binary Search Tree

 

Rubric-Student Name:
Points
Hand Drawings & Expected Output (prior to programming)
(-5 if not done prior to programming)

--tree drawings
/ 2
  --expected output for preOrder toString of original data
/ 2
  --expected output for inOrder toString of original data
/ 2
  --expected output for preOrder toString of swapped data
/ 2
  --expected output for inOrder toString of swapped data
/ 2
Listing of Classes & Interfaces
  TreeNode class
/ 5
  BSTree interface
/ 5


Tree class that implements the BSTree with methods
-- void add(Comparable)
-- boolean search(Comparable)
-- int height()
-- String toStringPreOrder()
-- String toStringInOrder()
-- void remove(Comparable)
/ 10
  TreeDriver class
/ 5
Output
  --toStringPreOrder() output as a printout
/2
  --toStringInOrder() output as a printout
/3
TOTAL
/ 40

 

Based on the TreeNode and Binary Search Tree design given in the lecture, write the following code:

  1. A TreeNode class that takes a Comparable as its data element
  2. The BSTree interface that declares the following methods:
    • void add(Comparable)
    • boolean search(Comparable)
    • int height() // returns the maximum length of any leaf in the tree
    • String toStringPreOrder() // prints the Tree using Pre-Order traversal
    • String toStringInOrder() // prints the Tree elements using In-Order traversal
    • void remove(Comparable)
  3. A Tree class that implements the BSTree interface and uses your TreeNode class
    • NOTE: use a "dummy" remove() method
  4. A driver program that tests your Tree class including:
    • an instantiation of the Tree
    • add the following Strings to the Tree in the following order:
    •   "Bill" , "Fred", "Joe" "Henrietta", "Mr. M", "Noman", "Alfred", "Al", "Fred"
    • printout the Tree using both the toStringPreOrder() and toStringInOrder() methods

To be scored before programming:

  1. Show a drawing of the tree after adding all of the above names.
  2. Show the expected output of the toString...() methods
  3. Show the expected output if "Henrietta" and "Fred" were added to the tree in swapped order (i.e. Bill, Henrietta, Joe, Fred ...)

To be scored after programming the classes:

  1. Printout this scoring rubric and staple to the front of your drawings followed by the next item.
  2. Printout the listing for the above classes and interfaces--use appropriate commenting!
  3. Demonstrate and explain how your driver program works and compares to your expected output

APCS-A Program Assignment #16 - Binary Search Tree Assignment Part 2 (deleting)

 

Rubric - Student Name:
Points
Hand Drawings & Expected Output (prior to programming)
(-5 if not done prior to programming)

--tree drawings for addition (10 diagrams total)
/ 5
  --tree drawings for removal (5 diagrams total)
/ 5
  --expected output for preOrder toString of original data
/ 1
  --expected output for inOrder toString of original data
/ 1
  --expected output for preOrder toString of removed data
/ 1
  --expected output for inOrder toString of removed data
/ 1
  --answer to question
/ 2
Listing of Classes


Tree class with additional method

--void remove(Comparable)

/ 10
  TreeDriver class
/ 5
Output [may be included as a comment at the bottom of your code]
  --output of the height() method as a printout
/ 2
  --output of the search(Comparable) method as a printout
/ 2
  --toStringPreOrder() output as a printout
/ 2
  --toStringInOrder() output as a printout
/ 3
TOTAL
/ 40

 

Using your TreeNode and Binary Search Tree programmed from Program 15, write the following code:

  1. Complete the remove(Comparable) methods for your Tree class.
  2. A driver program that tests Tree class including:
    • an instantiation of the Tree
    • "add" the following Strings to the Tree in the following order:
      • "L" , "D", "A", "F", "B", "R", "M", "U", "T", "V"
    • printout the Tree using both the toStringPreOrder() and toStringInOrder() methods
    • demonstrate the use of the height() and search() methods
    • delete the following Strings from the Tree in the following order:
      • "A", "B", "U", "R", "L"

To be graded before programming:

  1. Show a drawing of the tree after adding all of the above Strings.
  2. Show the expected output of the toString...() methods
  3. Show a drawing of the tree after each consecutive deletion of each String.
  4. How would you delete the full tree in as simple a method as possible?

To be scored after programming the classes:

  1. Printout the listing for the above 2 classes -- use appropriate commenting!
  2. Demonstrate and explain how your driver program works and compares to your expected output.

APCS-A Program Assignment #17 - Sets and Maps Program

 

Rubric - Student Name:
Points
Hand Drawings & Expected Output (prior to programming)
(-5 if not done prior to programming)

--TreeMap diagram
/ 3
  --HashMap diagram
/ 3
  --Set (Tree or Hash) diagram
/ 3
  --expected output for toString of TreeMap
/ 2
  --expected output for toString of HashMap
/ 2
  --expected output for toString of Set (Tree or Hash)
/ 2
Listing of Classes
  Driver Program (read data file & add data to structures)
/ 10
Output
  --toString() output as a printout for TreeMap
/ 1
  --toString() output as a printout for HashMap
/ 1
  --toString() output as a printout for Set (Tree or Hash)
/ 3
TOTAL
/ 30

 

Based upon the Sets & Maps Worksheet given in class, do the following 3 program segments:

  1. Write a driver program to declare and instantiate:
    • one TreeMap, one HashMap and one set (either HashSet or TreeSet) object (3 objects in all)
    • use/populate these 3 objects with appropriate data. Different quantities for each Collection.
    • If you cannot generate your own data to populate the sets and/or maps, you may use or modify from the given examples in the Worksheet.
  2. Prior to programming, create an appropriate Test Case for each data structure with the following specifications:
    1. Determine a least 10 values and/or keys to add to each of your data structures (i.e. 10 for TreeMap, 10 for HashMap, 10 for HashSet or TreeSet)
    2. Draw a diagram to show your teacher the tree diagrams generated from your 10 values and/or keys. For hashes, create a "dummy" hashCode() by writing the comment that explains how the hashCode would work for each value and/or key and a "initial capacity" for the hashTable (actually just an array with a fixed initial size/capacity). Then have Your Teacher Sign Off on the table generated from the HashMap and/or HashSet as well as the tree (TreeMap or TreeSet)
    3. Write the output of the expected toString() methods for each of your data structures
    4. Store these values and/or keys in a text file in any convenient format to be read by your driver program.
  3. Write a driver program to incorporate the 3 data structures then:
    1. Read the test data from your textfile,
    2. Add the data to your data structures, and, finally,
    3. Printout the results of the toString() methods

APCS-A Program Assignment #18 - Small Challenge Programs

 

Write an application that solves the following three problems:

  1. Given the following function definition, find f(1), f(15), f(27), and f(53)
    f(x) = 2*f(x-3) - 4 if x is composite
    f(x) = x^2 + x if x is prime
    f(x) = 1 if x <= 1
  2. How many whole numbers (non-negative int) between x and y have eight "1's" in their binary representation?
    Assume that x < y < 1023
  3. Triangular Targets: Given a set of 3 coordinate pairs representing the vertices of a triangle and a 4th coordinate pair representing a target, determine if the target is inside (or on) the triangle or outside the triangle.
    1. Sample Input:
      0.0 0.0
      9.0 0.1
      0.5 9.0
      2.0 1.9
    2. Sample Output:
      The point (2.0 1.9) is inside the triangle with coordinates (0.0, 0.0), (9.0, 0.1), and (0.5, 9.0)
    3. Test your program with the following triangles and targets [but your program should handle any triangle/target combination]
      i) (2.2, 5.6) (1.1, 2.2) (3.4, 4.7) target: (2.5, 3.0)
      ii) (-4.2, 3.0) (-2.7,3.0) (-9.1, 8.18) target: (-4.4, 3.8)
    4. Note: you may assume that the coordinate pairs will be given to the nearest 1/10 (i.e. 0.1) to avoid representation/roundoff errors.

To be turned in for scoring:

  1. The listing of your program with appropriate commenting.
  2. The output of each problem should be sent to a file called "recursiveBinaryTriangle.txt" with appropriate headers.
    This file should be printed out and stapled to the back of your program listing.