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 #19 - Heaps (Priority Queue)

Objective: Create and use a Priority Queue / min-Heapbased on using a Heap Data Structure.

  1. Write a Heap class with the following characteristics:
    • Uses an ArrayList as its storage for the heap.
    • Make sure you maintain all properties of a heap.
    • Write the following methods:
      • boolean add(Comparable)
      • Comparable removeMin()
      • Comparable peekMin()
      • boolean isEmpty()
  2. Write a Driver program to test your Heap class. The driver program should:
    • Instantiate a heap using your Heap class
    • Add the following data (representing size of printer jobs) to your heap:
      • 45, 13, 17, 77, 55, 16, 22, 44, 46, 1, 12, 23
    • Printout the Heap (ArrayList) after each element is added
    • Remove each minimum element one at a time and printout the Heap (ArrayList) after each removal.

To be turned in for grading:

  1. Before programming, show your teacher the handwritten output of the heap in both array form and tree form of the above data given above.
  2. The listing of your program with appropriate commenting
  3. The output of each problem should be sent to a file called "heapOutput.txt" with appropriate headers. This file should be printed out and stapled to the back of your program listing along with your "pre-approved" handwritten output.
Rubric
Points
Hand Drawings & Expected Output (prior to programming)  
(-5 if not done prior to programming)
 

--Tree diagrams (12, one for each number added)

 
3
 

--ArrayList diagrams (12, one for each number added)

 
3
 

--One ArrayList diagram & One Tree diagram after one number (i.e. 1) has been removed.

-- A 2nd ArrayList diagram and a 2nd Tree diagram after a 2nd number (i.e. 12) has been removed.

 
2
Listing of Classes  
 

Heap class -- add(), removeMin(), peekMin(), isEmpty()

 
9
 

Driver Program (write test data to heap instance, verify each method in Heap class, and write data file)

 
3
Output  
 

--ArrayList as a printout for each addition (12)

 
2
 

--ArrayList as a printout after removal of 2 numbers (i.e. 1 and 12)

 
2
 

--Appropriate headers

 
1
TOTAL  
25

 

APCS-A Program Assignment #20 - Model-View-Controller (Individual/Group)

  1. Students will choose a Java application to write by themselves (i.e. no downloading code) as either an individual or group effort and select an appropriate grading criteria as their final program assignment.
  2. Before the appliction program itself is written, a group of students must create a single-page (approximately) write-up for the program including:
    1. Title of Program and name(s) of students participating
    2. Description of program (at most 1 paragraph).
    3. Objectives (this program will accomplish the following...).
    4. Timeline for Meeting Objectives.
    5. Breakdown of student responsibilites/assignments for objectives, including design parameters for:
      • Model
      • View
      • Controller
    6. Grading rubric including the following criteria:
      • Individual grading scores based on timeline and meeting of objectives
      • Group grading scores based on timeline and meeting of objectives Note: group grading must be less then 50% of overall grade.
      • Final score for the full Java application execution and coding printout.
      • Total grade percentage for quarter. Note: total grade cannot exceed 30% of quarter grade.
    7. The single page writeup must be approved by your teacher and signed by all participating students signaling their agreement to the writeup's specifications.
    • Note 1: The more detail that is specified, the less chance for disagreement between group members or grading.
    • Note 2: The specifications agreed upon by the students will be followed as strictly as possible. However, unclear specifications or specifications that are too general will be graded based upon your teacher's judgement, not by student intentions, opinions, or assumptions.
  3. As a design issue (i.e. before programming) a UML Class diagram must be drawn up and approved by your teacher before programming may start. This UML Class diagram will be used as evaluation of final printout and execution of the program. Any deviation from the UML Class diagram must require a "change order" during the project that is approved by your teacher.

APCS-A Exemplar Lab Test

  1. You will be assigned a random computer to demonstrate the following skills:
    1. Default Chatbot running.
    2. Default Elevens Lab running.
    3. Default Picture Lab (beach scene) running.
  2. For Chatbot, modify the code to demonstrate:
    1. a chatbot that responds favorably when it sees the name of a teacher. Be sure to use appropriate pronouns (i.e. Mr = he, Mrs. = she). There are 6 different variations on gender titles and encorporate case-sensitivity.

      • Statement: I llike missus Easley.

      • Response: She sounds like a good teacher.

  3. For Picture Lab, modify the code to demonstrate:
    1. show a picture--besides beach.jpg--as containing only red color components
    2. show the default image "beach.jpg" in gray scale
      • each pixel has a gray scale defined as the average of all the color components: gray = (red+green+blue) / 3
    3. show the default image "beach.jpg" in sepia-like tone by using the following definition:
      • modify each pixel's color using the gray scale defined above and re-defining each color component:
        • red = gray*112/255
        • green = gray*66/255
        • blue = gray*20/255
      • watch for out-of-bounds conditions (i.e. maximum color compenent is 255).
    4. show the default image "beach.jpg" that is mirrored vertically (i.e across vertical axis of symmetry)
    5. show the default image "beach.jpg" that is mirrored diagonally (i.e across y=x line)

To be scored out of 100 pts:

Student Name: _____________________________________ [ Note: Day 1 student must complete a minimum of 60 points]

Demo Chatbot Lab

Demo Elevens Lab

Demo Picture Lab

ChatBot Modification

Picture Modification - non-beach.jpg only Red

Picture Modification - beach.jpg gray scale

Picture Modification - beach.jpg sepia tone

Picture Modification - beach.jgp Mirror Vertically

Picture Modification - beach.jgp Mirror Diagonally

Day 1 Total

Day 2 Total

 

 

 

 

 

 

 

   

 

 

5

10

5

20

10

15

15

10

10

60

40