Each month students may tackle a set of computing problems requiring the design and implementation of algorithms in a computing contest. The contest will run over the weekend from Friday afternoon until Tuesday morning. The computing problems will be drawn from monthly USACO [USA Computing Olympiad] contests and the single CCC [Canadian Computing Competition] which occurs near the end of February.

A really super reference (really an entire university course) for this course is Data Structures and Algorithms by John Morris at the University of Western Australia! The course includes great coloured diagrams and algorithmic animations of sorting and searching algorithms. This is an invaluable resource for learning the computer programming knowledge covered by this course.

This course is about data structures. An excellent article is Java Data Structures (2nd Edition) which explains what Java data structures are all about. This is the perfect time to read it.

An interesting source of examples is the source code from Mark Allen Weiss' textbook Data Structures & Problem Solving using Java.

• Review and increase your Java knowledge by perusing the 692 slides from Jackie Barker's book, Beginning Objects:  From concepts To Code.

  Begin Java Objs pdf               Begin Java Objs ppt

Yakov Fain writes an online series for the Java Development Journal [JDJ] on learning to program with Java for the Java Development Journal. Review his two excellent columns on Java GUI

• Lesson 12: An Introduction to GUI with Swing [JDJ 18 August 2005]

• Lesson 13: Processing GUI Events [JDJ 22 September 2005]

BIG
JAVA
12

Horstmann Chap 12

Sedgewick Chap 3.0

Horstmann 12

King 12

Study Horstmann's Event Handling: Chapter 12.

Programming Exercises To Be Graded (pp 512-514): P12.2, P12.4, P12.6, P12.8, P12.10, P12.12, P12.14, P12.16, P12.18, P12.20.

BIG
JAVA
14

Horstmann Chap 14

Sedgewick Chap 3.0

Horstmann 14

King 12

Study Horstmann's Graphical User Interfaces: Chapter 14.

Programming Exercises To Be Graded (pp 514-514): P14.2, P14.4, P14.6, P14.8, P14.10, P14.12.

Kjell
Tutorials

Assignments

1. Overview the Chapter 12 PowerPoint Slideshow. This just gives you the "lay of the land" for now. Later, after you read the chapter, this slide show will be a very meaningful review.

2. Read the chapter actively! Execute and tinker with the code. Draw diagrams of concepts.

3. Implement and run the Chapter 12 source code.

4. Mentally review the "Self-Review Exercises" (715-716) (The section containing the answers to these questions follow in the book itself.) This may easily alert you to potential holes in your knowledge and skills.

5. Study the following practice exercises on the left to get a good feel for how to solve problems in this chapter. Clicking on their links will present you with the publisher's solutions. Then solve and submit solutions to exercises on the right that will be reviewed for grading purposes.

   WARNING: Work through some or all of the practice exercises before attempting exercises to be submitted. Use the syntax and organization of the practice exercises as models. Failure to first study the practise exercises will probably result in significant frustration!

   Programming Exercises For Practice

   Programming Exercises For Grades

   12.08:     Create the following GUI. You do not have to provide any functionality. 12.09:     Create the following GUI. You do not have to provide any functionality. 12.13:     Write a conversion program that allows conversions between any two of the Fahrenheit, Celsius and Kelvin temperature scales. 12.15:     Allow the user to draw different shapes by dragging the mouse on the application window. 12.23:     Allow the user to paint a picture by choosing the shape, colour, font and font size. 12.27:     Use methods from MouseListener to draw a rectangle.

   12.14:     Draw a rectangle by dragging the mouse. 12.16:     Draw shapes determined by a KeyEvent. 12.17:     Choose shape and colour using JComboBoxeses, JRadioButtons and JCheckBoxes. 12.19:     Draw and repaint a square using a mouse. 12.21:     Write a program that plays "guess the number". 12.24:     Select and draw a shape 20 times in method paint. 12.25:     Modify 12.24 to draw in a selected colour. 12.26:     Modify 12.26 to select the colour from a JColorChooser dialog.

6. Include the following documentation for each exercise that is submitted to be graded.

   1. List the specifications of the program. These may be deduced in the statement of the exercise.

   2. Source Code of all new files: html file for applets, class file(s), driver program(s).

      Print the source code and screen dump in a Word Processor, two pages per side, double sided. Simultaneously pressing [Alt][PrtScn] will copy the GUI output to the clipboard from whence you can paste it just below your source code. Use a non-proportional font (example: Courier New) to maintain the vertical alignment of the stucture of your source code.

   3. Screen Shots of Input and Output dialog boxes.

      Where I/O (Input/Output) inlcudes multiple GUI (Graphical User Interface) dialog boxes, include at least one screen shot for each input and output dialog box. Where there are various types of dialog boxes and/or messages and/or types of data, include a "reasonable" number of screen shots.

      Typically there will be 1-2 screen shots showing input and 1-2 screen shots showing output. In extraordinary cases, there could conceivably be a dozen or more screen shots. What is "reasonable" is the product of using reason (thought) and reasons (related information). BE REASONABLE!

   4. Trace Table of Changes in Values of the Variables During Execution.

7. There will be a multiple choice test at the end of this chapter.

Assignments

1. Overview the Chapter 13 PowerPoint Slideshow. This just gives you the "lay of the land" for now. Later, after you read the chapter, this slide show will be a very meaningful review.

2. Read the chapter actively! Execute and tinker with the code. Draw diagrams of concepts.

3. Implement and run the Chapter 13 source code.

4. Mentally review the "Self-Review Exercises" (800-801) (The section containing the answers to these questions follow in the book itself.) This may easily alert you to potential holes in your knowledge and skills.

5. Study the following practice exercises on the left to get a good feel for how to solve problems in this chapter. Clicking on their links will present you with the publisher's solutions. Then solve and submit solutions to exercises on the right that will be reviewed for grading purposes.

   WARNING: Work through some or all of the practice exercises before attempting exercises to be submitted. Use the syntax and organization of the practice exercises as models. Failure to first study the practise exercises will probably result in significant frustration!

   WARNING!! THIS CHAPTER IS UNDER CONSTRUCTION. CHAPTER 12 ABOVE IS BEING USED AS A TEMPLATE. THUS REFERENCES TO CHAPTER 13 MAY BE THE SAME AS CHAPTER 12 UNTIL THIS MESSAGE IS REMOVED!!

   Programming Exercises For Practice

   Programming Exercises For Grades

   13.07:     Display a circle and calculated parameters in a subclass of JPanel and JTextArea. 13.10:     Use paintComponent, JTextField, setValue, and getValue. 13.11:     Use a JComboBox instead of four separate JButtons. 13.13:     Define a class MyColorChooser so it can be used in other applications or applets.

   13.04:     Fill in blanks. 13.05:     Fill in blanks. 13.06:     Find errors and explain how to correct them. 13.14:     Modify the MyColorChooser class of Exercise 13.13. 13.18:     Write a program that plays "guess the number". 12.24:     Select and draw a shape 20 times in method paint. 12.25:     Modify 12.24 to draw in a selected colour. 12.26:     Modify 12.26 to select the colour from a JColorChooser dialog.

6. Include the following documentation for each exercise that is submitted to be graded.

   1. List the specifications of the program. These may be deduced in the statement of the exercise.

   2. Source Code of all new files: html file for applets, class file(s), driver program(s).

      Print the source code and screen dump in a Word Processor, two pages per side, double sided. Simultaneously pressing [Alt][PrtScn] will copy the GUI output to the clipboard from whence you can paste it just below your source code. Use a non-proportional font (example: Courier New) to maintain the vertical alignment of the stucture of your source code.

   3. Screen Shots of Input and Output dialog boxes.

      Where I/O (Input/Output) inlcudes multiple GUI (Graphical User Interface) dialog boxes, include at least one screen shot for each input and output dialog box. Where there are various types of dialog boxes and/or messages and/or types of data, include a "reasonable" number of screen shots.

      Typically there will be 1-2 screen shots showing input and 1-2 screen shots showing output. In extraordinary cases, there could conceivably be a dozen or more screen shots. What is "reasonable" is the product of using reason (thought) and reasons (related information). BE REASONABLE!

   4. Trace Table of Changes in Values of the Variables During Execution.

7. There will be a multiple choice test at the end of this chapter.

BIG
JAVA
15

Horstmann Chap 15

Sedgewick Chap 3.0

Horstmann 15

King 10

Study Horstmann's Event Handling: Chapter 15.

Programming Exercises To Be Graded (pp 515-514): P15.2, P15.4, P15.6, P15.8.

Read this Java World article subtitled Exception handling in Java from top to bottom as an introduction to and later summary of Exception Handling in Java.

Here's a short commentary on exception handling worth reading by Wilson Mar: Exception Handling.

Back in 1998 Bill Venners wrote a couple of very informative companion articles for Java World:

• Exceptions in Java explains what exceptions are and how they work.

• Designing with exceptions looks at design principles that concern error reporting and exceptions.

Kjell gives an excellent introduction to exception handling and advanced IO streams. For that reason we cover his material before returning to Deitel. We want to do all of the related Kjell exercises corresponding to chapters 80-87. Some of them are very challenging.

Special Note Re Chapter 84, Exercise 3: After creating a GUI copy program, Kjell suggests that you should "look in your documentation for the FileDialog class. Include it in the GUI so the user can choose the source file graphically." The AWT FileDialog class has been replaced by the Swing FileChooser class. FileDialog is a deprecated API. FileDialog is an AWT component that asks the user to select a file or directory. Use Swing's JFileChooser class instead.

Deitel covers the FileChooser class in chapter 16, but there are many other sources on the Internet. Search for "java FileChooser". Sources are:

1. http://mindprod.com/jgloss/jfilechooser.html

   A Swing component to ask the user to select a file or directory. By default it lets use user select files only, but you can setFileSelectionMode( JFileChooser.DIRECTORIES_ONLY ) or setFileSelectionMode( JFileChooser.FILES_AND_DIRECTORIES ) When you do a jFileChooser.showOpenDialog it pops up a modal dialog box and returns JFileChooser.APPROVE_OPTION if all went ok. Then you can retrieve the selected file with jFileChooser.getSelectedFile().

   Watch out. When you a feed a filter to JFileChoser, it wants as javax.swing.filechooser. FileFilter not a java.io. FilenameFilter;

   It lets the user create new directories as he navigates. It is embarrassingly slow code.

2. http://www.javaworld.com/javatips/jw-javatip85_p.html

   A great article entitled "Java Tip 85: Fun and games with JFileChooser" which is summarized as:

   JFileChooser is a class supplied with Swing that lets users select specific files from mapped drives. It imitates the Windows Explorer and Unix File Manager programs. This Java tip shows you how to use it, and gives you details on some of the problems it can run into. (2,300 words)

3. http://leepoint.net/notes-java/30GUI/35containers/20dialogs/30filechooser.html

   A very nice outline of the syntax and usage.

4. http://www.particle.kth.se/~lindsey/JavaCourse/Book/Part1/Java/Chapter09/chooser.html

   Gives a very nice example of using the code, a section of a chapter in the electronic java course at: http://www.particle.kth.se/~lindsey/JavaCourse/Book/courseMap.html

Re Exercise 84-4: StringTokenizer is covered in detail in Kjell's chapter 47D.

Detecting End of File: It is often important to detect the end of a file when reading data from a file. After reading some interesting notes by Peter Burden on Java - Integer input [web] [csg], one recognizes two distinct strategies.

Java takes advantage of the fact that Java reads all input as string objects. When the string reading variable is unable to read a string because there is no more data (end of file is reached), the value of that string reading variable is null

There are two ways to handling errors in Java.

1. C-style == throw exceptions and let the interpreter spew out a trace table of line numbers. For example:

   import java.io.*; class ReadTextFile { public static void main ( String[] args ) throws IOException { String fileName = "reaper.txt" ; BufferedReader in = new BufferedReader( new FileReader( fileName ) ); String line = in.readLine(); // prime the loop while ( line != null ) // continue until end of file { System.out.println( line ); line = in.readLine(); } in.close(); } // end main() } // end class

   
   
   

2. Java-style == catch exceptions: check for errors and provide a remedy at the point where the error will occur. Example

   import java.io.*; class ReadTextFile { public static void main ( String[] args ) { String fileName = "reaper.txt" ; String line; try { BufferedReader in = new BufferedReader( new FileReader( fileName ) ); line = in.readLine(); while ( line != null ) // continue until end of file { System.out.println( line ); line = in.readLine(); } in.close(); } catch ( IOException iox ) { System.out.println("Problem reading " + fileName ); } } }

Assignments

1. Peruse Bradley Kjell's gentle introduction Chapter 80 - Exceptions and Errors and its elaboration Chapter 81 - More About Exceptions. This will make covering the Deitel Chapter 14 much easier.

2. Overview the Chapter 14 PowerPoint Slideshow. This just gives you the "lay of the land" for now. Later, after you read the chapter, this slide show will be a very meaningful review.

3. Read the chapter actively! Execute and tinker with the code. Draw diagrams of concepts.

4. Implement and run the Chapter 14 source code.

5. Mentally review the "Self-Review Exercises" (834-835) (The section containing the answers to these questions follows in the book itself.) This may easily alert you to potential holes in your knowledge and skills.

6. Read Eck's Explanation of Correctness and Robustness

   Read Chapter 9: Correctness and Robustness from the 4th edition of David Eck's book Introduction to Programming Using Java.

   
   

7. Study the following practice exercises on the left to get a good feel for how to solve problems in this chapter. Clicking on their links will present you with the publisher's solutions. Then solve and submit solutions to exercises on the right that will be reviewed for grading purposes.

   WARNING: Work through some or all of the practice exercises before attempting exercises to be submitted. Use the syntax and organization of the practice exercises as models. Failure to first study the practise exercises will probably result in significant frustration!

   Programming Exercises For Practice	Programming Exercises For Grades
   14.21:     Demonstrate that the catch specifying a superclass catches subclass exceptions. 14.26:     Illustrate rethrowing an exception.	14.22:     Demonstrate that not all finalizers for objects are necessarily called. 14.23:     Demonstrate how exceptions are caught with catch (Exception exception). 14.24:     Demonstrate the importance of the order of exception handlers. 14.25:     Show a constructor passing information about to an exception handler. 14.27:     Demonstrate that some exceptions can be handled in other scopes.

8. Include the following documentation for each exercise that is submitted to be graded.

   1. List the specifications of the program. These may be deduced in the statement of the exercise.

   2. Source Code of all new files: html file for applets, class file(s), driver program(s).

      Print the source code and screen dump in a Word Processor, two pages per side, double sided. Simultaneously pressing [Alt][PrtScn] will copy the GUI output to the clipboard from whence you can paste it just below your source code. Use a non-proportional font (example: Courier New) to maintain the vertical alignment of the stucture of your source code.

   3. Screen Shots of Input and Output dialog boxes.

      Where I/O (Input/Output) inlcudes multiple GUI (Graphical User Interface) dialog boxes, include at least one screen shot for each input and output dialog box. Where there are various types of dialog boxes and/or messages and/or types of data, include a "reasonable" number of screen shots.

      Typically there will be 1-2 screen shots showing input and 1-2 screen shots showing output. In extraordinary cases, there could conceivably be a dozen or more screen shots. What is "reasonable" is the product of using reason (thought) and reasons (related information). BE REASONABLE!

9. There will be a multiple choice test at the end of this chapter.

Horstmann
15

Unit testing code automates testing so that the testing code may be kept separate from application code.

Ideally, every method of every class is tested every time that application code is changed. While this "regressive" testing sounds agonizingly laborious, it effectively builds code that is valid: that wil do what it is supposed to do!

In 2003-2004 I asked students to place all tests in the main() method, but unit testing is a more methodical approach. In 2004-2005 I ask students to use JUnit Testing with the Java programming language. The stand alone JUnit3.8.1.zip contains the current (25 September 2004) stand alone JUnit app, but we can also access JUnit Testing as integrated with NetBeans 3.6 after Tools -> JUnit Tests.

1. Download and install JUnit3.8.1.zip
2. Complete the tutorial:   JUnit Howto
3. Implement suggestions in Getting Started, especially working through the article, Test Infected - Programmers Love Writing Tests. This article demonstrates the development process with JUnit in the context of multiple currency arithmetic. The corresponding source code is in junit\samples\money.
4. Read the JUnit Cookbook, showing you the steps you can follow in writing and organizing your own tests using JUnit.
5. Study JUnit A Cook's Tour which opens with a discussion of the goals of the framework. The goals then reappear in many small details during the presentation of the framework itself. Following this, the article presents the design and implementation of the framework. The design is described in terms of patterns, the implementation as a literate program. It concludes with "choice thoughts" about framework development.
6. Peruse the JUnit FAQ noting focii on the writing, organizing and running of tests.
7. Study the classes and methods of JUnit javadocs.
8. Implement the code in Installing and Running a JUnit Test -- A Tutorial.
9. Read some of these interesting articles concerning JUnit.
10. Practice using JUnit as it is integrated with NetBeans 3.6 and above.

Assignments

1. Take a peek at the following slide shows , which is a quick way to get different perspectives on similar information:

   • Litvin's Streams and Files
   • Lewis and Loftus powerpoint Exceptions and IO Streams
   • K. N. King's Files

2. Peruse Bradley Kjell's Java Tutorials and do the corresponding exercises:

   • Chapter 82 - Input and Output Streams
   • Chapter 83 - Writing Text Files
   • Chapter 84 - Reading Text Files
   • Chapter 85 - Writing Binary Files
   • Chapter 86 - Reading Binary Files
   • Chapter 87 - The File Class

3. Overview Deitel's Chapter 16 PowerPoint Slideshow. This just gives you the "lay of the land" for now. Later, after you read the chapter, this slide show will be a very meaningful review.

   You will now do some fancy academic juggling as you go through this slide show. As you note a reference to a class, or an object created from a class, or the invocation of a method in a class, you must insure that you understand what it does and how you will later incorporate it into your programs. It is therefore essential that, as you proceed through the slideshow, you simultaneously refer to the slideshow, the corresponding chapter in the Deitel textbook, and explanations in Sun MircoSystem's Java API Specification.

   Before starting the slide show, open your Deitel textbook to the beginning of Chapter 16. As you move through explanations of source code with the slide show, flip to the relevant pages of the textbook that show screen dumps of the the GUI components used in the program that is being explained. You will far better understand what the GUI related code is doing if you can simultaneously observe it's output.

   Before starting the slide show, also connect to Sun MicroSystem's web page containing the Java API Specification. When the slideshow deals with the declaration and instantiation of a standard Java class, or invokes methods that are defined within a standard Java class, then flip to Sun's Java API Specification and navigate your way to the class that you are studying. You will find explanations of every standard package, class, and method in Java.

   As you move through the slide show, flip back and forth among the slide show, text book, and Sun MicroSystem's Java API Specification.

4. Implement and run the Chapter 16 source code.

5. Implement and run Dave Mulkey's RandomAccessFiles Mini Project [csg] [web].

6. Read Eck's Explanation of Advanced Input/Output

   Read Chapter 10: Advanced Input/Output from the 4th edition of David Eck's book Introduction to Programming Using Java.

   
   

7. Check out the PowerPoint slide shows Java I/O and More File I/O: Random Access and Object Serialization created by Aaron Cohen for his Fall 2002 Advanced Programming class at Oregon Health & Science University.

8. A really clear example of random access file handling of objects of fields dealing with a book may be studied in the online text, Object-Oriented Software Design and Construction with Java by Dr. Dennis Kafura.

9. Another clear example is this random access records for a file of employee records which is just one part of the course CS586: High-Octane Java! taught by Bryan J. Higgs at River college in Nashua, NH.

10. Java Lecture Notes by Elliotte Rusty Harold offers a lot of material on Java I/O generally, and specifically Random Access Files. Also see his Java I/O HTML Slides.

11. Read the chapter actively! Execute and tinker with the code. Draw diagrams of concepts.

    Note that the programs in this chapter import classes from both Sun's Standard Libraries and classes created by the authors of the textbook. For example, the BankUI.java classes that is first explained in the slideshow can be compiled but cannot be executed by itself. Ditto for the AccountRecord.java class that is next encountered. Both the BankUI and AccountRecord classes are imported into the CreateSequentialFile class. Only after compiling and executing the CreateSqeunetialFile.java file will you be able to execute and thus test the implementation of the BankUI.java and AccountRecord.java files.

    Imported classes must be placed where the path in the source code says they will be found.For example, ensure that you have copied both the path and files to the same directory where the bytecode files ("*.class") placed. Two of the Deitel classes that are imported by other classes througout this chapter are the BankUI and AccountRecord classes.

    // Deitel packages import com.deitel.jhtp4.ch16.BankUI; import com.deitel.jhtp4.ch16.AccountRecord;

12. Mentally review the "Self-Review Exercises" (972) (The section containing the answers to these questions follows in the book itself.) This may easily alert you to potential holes in your knowledge and skills.

13. Peruse Files, File Organization, Random Access Files, and source code of related examples at IB-Computing Home, a site developed by IB Assistant Chief Examiner Richard Jones.

14. Peruse Sun Microsystem's tutorial lesson on I/O: Reading and Writing (but no 'rithmetic).

15. Peruse Olivier Baby's Lecture Notes on Files, and Random Access Files.

16. Check out the Tech Tip on Random Access For Files at Sun Microsystems.

17. If interested, here is how to open and close a file twice.

18. Study the following practice exercise on the left to get a good feel for how to solve problems in this chapter. Clicking on it's link will present you with the publisher's solution. Then solve and submit solutions to exercises on the right that will be reviewed for grading purposes.

    Note that this chapter requires that you develop separate classes of code that may be used by client programs. You should therefore expect to develop at least two files for each exercise. One file will contain the source code for the class itself. The other file will be a driver program that uses and tests the features of the code generated by the class file.

    WARNING: Work through some or all of the practice exercises before attempting exercises to be submitted. Use the syntax and organization of the practice exercises as models. Failure to first study the practise exercises will probably result in significant frustration!

    Convention For Naming A Package: In Section 8.5 the Deitels reminded us of Sun MicroSystems' convention for naming a package of classes. Students at Churchill are asked to name their packages starting with "swc" (Sir Winston Churchill High School), then an abbreviation of the course name (eg: "cs202"), followed by the student's initials (eg: "gdd" for Gerry Douglas Donaldson), followed by the author's name of the textbook being used ("deitel"), followed by a reference to the chapter and exercise numbers ("c8e18"). Thus, the first statement of a file containing a "package" could be:    package  swc.cs202.gdd.deitel.c8e18

    Programming Exercise For Practice	Programming Exercises For Grades
    16.11:     Telephone Number Word Generator:  Write a program that, given a seven-digit number, writes to a file every possible seven-letter word combination corresponding to that number.	Documetation for the following exercises must include: Internal Javadoc comments that generate an HTML file in the format of Sun's Java API Documentation. See pdf handout and associated examples of Javadoc. Hardcopy of each program's HTML Javadoc file. UML Class Diagram generated with VP-UML. Always give the user the option to view all data in a data file. The sequential and direct access data fules that you will create by doing the following questions are NOT TEXT FILES. The data cannot be read by a normal text editor. Your program(s) must therefore offer the user an option to print all data, minmally, to the screen and, preferably, to the printer as well. In solving questions 16.7, 16.8, 16.9, and 16.10 there must never be data from more than two records in memory at the same time. Click here for explanation and justification. 16.7:     [PairPrg] File-Processing Accounts Receivable Program:  16.8:     [PairPrg] Program that creates Test Data for the Accounts Receivable Program done for Exercise 16.7:   In solving question 16.8, "Print the new master file." should be interpreted to mean that all data in the master file should be displayable one screen full at a time. 16.9:     [PairPrg] Rewrite File-Processing Accounts Receivable Program done for Exercise 16.7:   It should provide for the possibity of handling several transaction records with the same record key. 16.10:     [PairPrg] Hardware Inventory:  You are the owner of a hardware store and need to keep an inventory that can tell you what different tools you have, how many of each you have on hand and the cost of each one. Write a program that initializes the random-access file "hardware.dat" to one hundred empty records, lets you input the data concerning each tool, enables you to list all your tools, lets you delete a record for a tool that you no longer have and lets you update any information in the file. The tool identification number should be the record number. Use the information in Fig. 16.26 of your textbook (page 976) to start your file. Magic numbers are not allowed. See the example in the green box below for appropriate documentation of the length of a direct access data record. Make string fields a constant length. See the example in the pink box below for code that sets the length of a String object to the appropriate length.
    Magic numbers are not allowed. All returned values must be appropriately documented. /** * @pre Size of record is not known. * @post Size of record is calculated as sum of lengths of fields. * */ public static int size() { // FIELDS of RECORD return 4 // 4 bytes for primitive int: account number + 30 // 15 char (2 bytes each) array: first name + 30 // 15 char (2 bytes each) array: last name + 8 ; // 8 bytes for primitive double: account balance // ----- // 72 ==> sum of bytes == length of this data record. // ===== } // end method size( ) Make String Fields a Constant Length One technique converts String objects to arrays of char, as does the Deitel texbook. Alternatively, ensure that String objects are set to a specified length, as below. static final int TITLE_BYTE_SIZE = 20; public void setTitle(String title) { StringBuffer buf = new StringBuffer(title); buf.setLength(TITLE_BYTE_SIZE); this.title = buf.toString(); } The setLength( ) method either truncates the String length or fills the extras slots with blanks. Care must be taken when comparing, because of the extra characters at the end, and when displaying, where the extra characters should be removed.

19. Include the following documentation for each exercise that is submitted to be graded.

    You will want to read the first couple of chapters of an excellent online textbook, Java An Object First Approach to learn about some new techniques that are used to plan and document objects and programs.

    1. List the specifications of the program. These may be deduced in the statement of the exercise.

    2. Source Code of all new files: html file for applets, class file(s), driver program(s).

       Print the source code and screen dump in a Word Processor, two pages per side, double sided. Simultaneously pressing [Alt][PrtScn] will copy the GUI output to the clipboard from whence you can paste it just below your source code. Use a non-proportional font (example: Courier New) to maintain the vertical alignment of the stucture of your source code.

    3. Screen Shots of Input and Output dialog boxes.

       Where I/O (Input/Output) inlcudes multiple GUI (Graphical User Interface) dialog boxes, include at least one screen shot for each input and output dialog box. Where there are various types of dialog boxes and/or messages and/or types of data, include a "reasonable" number of screen shots.

       Typically there will be 1-2 screen shots showing input and 1-2 screen shots showing output. In extraordinary cases, there could conceivably be a dozen or more screen shots. What is "reasonable" is the product of using reason (thought) and reasons (related information). BE REASONABLE!

    4. Trace Table of Changes in Values of the Variables During Execution.

20. There will be a multiple choice test at the end of this chapter.

Use
Javadocs

Javadoc HTML documentaion is the industry standard for documentating Java source code.

Hereafter all submitted Java source code must contain the required Javadoc tags and comments.

Unless otherwise requested, you need not submit a copy of the HTML Javadoc files.

Go to this page to find resources for learning how to use Javadoc documentation.

Specifically, nail the superb NCSU (North Carolina State University) Javadoc Tutorial by Laurie Williams, Dright Ho land Sarah Smith that teaches the use of Javadoc documentation and how to generate it using the Eclipse Javadoc plug-in.

BIG
JAVA
20

Horstmann Chap 20

Sedgewick Chap 4.0

TJ SCT [csg] [web]
Updated 13 Nov 2007

Sedgewick & Wayne
Stacks & Queues

Jeff Hunter's Programming
→ Programming
→ Data Structures

Dictionary of Algorithms and Data Structures

JHAVÉ

Horstmann 20

Study Horstmann's An Introduction to Data Structures: Chapter 20.

Study Sedgewick and Wayne's Introduction to Programming in Java: 4.3 Stacks & Queues. Read their "Q + A" section. (<Ctrl><F> "Q + A" on the web page.) IB students must know and understand Infix and Postfix notation for their IB final exams. (<Ctrl><F> "Stack and queue applications".)

Note that Sedgewick and Wayne identify preconditions as "known bugs" in the Postfix documentation.

Check out Jeff Hunter's Programming → Programming → Data Structures. Note especially his discussion of data structures and linked list source code.

All submitted Java source code must contain the required Javadoc tags and comments.

All external classes must be preceded by a Javadoc comment generated by an Eclipse Javadoc template containing the following information. Use template variables and standard and customized Javadoc taglets in creating the template. The comment should adhere to conventions of the Javadoc tool and not the format seen below.

1. Programming Exercises To Be Graded (pp 769-771): A single program incorporationg exercises 20.1 through 20.10, including both odd and even numbered exercises.

2. Exercises Project 20.2.

3. Submit a printed copy of the Eclipse template used to generate Javadoc class comments. the template should generate a javadoc like the one below.

4. Exercises 20.11, 20.12, 20.13. 20.14.

5. Understand and generate Java code that

   1. reads and evaluates postfix expressions and

   2. converts infix to outfix notation.

BIG
JAVA
21

Horstmann Chap 21

Sedgewick Chap 4.0

Data Structure Visualizations

Horstmann 21

Study Horstmann's An Introduction to Data Structures: Chapter 21.

Study the section on Hash tables in the electronic course Data Structures and Algorithms.

Double click the following button to view an animation for building hash tables.

Study animations of Binary Tree Traversals using the George Washington University applet, Interactive Data Structure Visualizations. Be sure to click the menu option Traversals at the top of the menu in the left frame. Note also that you must click the Start Visualization and Start Visualization buttons in order to start and stop the applet. Pay specific attention to the order of building a binary search tree and the three in-depth orders for traversing it.

Study animations of Priority Queue and the Heap Sort Algroithm using the George Washington University applet, Interactive Data Structure Visualizations.

All submitted Java source code must contain the required Javadoc tags and comments.

Programming Exercises To Be Graded (pp 836-838): P21.2, P21.4, P21.6, P21.8, P21.10, P21.12, P21.14, P21.16, P21.18, P21.20.

The following articles by Jeff Friesen were published in Java World during 2003. Students who find our textbook treatments to be stuffy and formal may find Jeff's "hobby-geek" enthusiasm to be refreshing.

An interesting treatment of structures with clear diagrams and welcomed, bite-sized explanations will be found in the electronic book by Fintan Culwin: Java As A First Language.

Be advised that meeting IB dossier specifications requires that students develop their own classes for linked lists, trees and direct (random) access file-handling.

Chapters from Fintan Culwin's Java As A First Language that are specific to structures are:

Assignments

1. Overview the Chapter 19 PowerPoint Slideshow. This just gives you the "lay of the land" for now. Later, after you read the chapter, this slide show will be a very meaningful review.

2. Read the chapter actively! Execute and tinker with the code. Draw diagrams of concepts.

3. Implement and run the Chapter 19 source code.

4. Mentally review the "Self-Review Exercises" (1126-1127) (The section containing the answers to these questions follows in the book itself.) This may easily alert you to potential holes in your knowledge and skills.

5. Read Eck's Explanation of Linked Data Structures and Recursion

   Read Chapter 11: Linked Data Structures and Recursion from the 4th edition of David Eck's book Introduction to Programming Using Java.

   
   

6. Refer to Chapter 4 of the "Walls and Mirrors" Java textbook, Data Abstraction and Problem Solving With Java, by Frank Carrano and Janet Prichard. Using that chapter, implement in Java Gerry Donaldson's 18 part C++ tutorial, Making a Linked List From Scratch. This exercise offers the added benefits of acquainting you with how linked lists were developed using C++ and a bit of the impact that Albertans have had on the design computer programming languages.

   Eventually Mr. Donaldson will convert this C++ tutorial to a full implementation of a Java tutorial. Meanwhile, it offers an excellent opportunity to observe the significant similarities and relatively minor differences between C++ and Java in implementing a linked list and saving it to a sequential file.

7. Check out Advanced Placement's implementation classes for linked lists and tree nodes and their interfaces for stacks, queues, and priority queues. These classes and interfaces are used in Advanced Placement's (higher) AB Computer Science course.

8. Preview the Powerpoint slide shows on lists, stacks and queues form Carrano and Prichard's Walls and Mirrors textbook: Chapter 4: Linked Lists, Chapter 6: Stacks, and Chapter 7: Queues. You may download powerpoint slide shows and/or source code from the Walls & Mirrors (Java) text from:

   ftp://ftp.aw.com/cseng/authors/carrano/java/"

9. Preview the Powerpoint slide shows from the Litvin Advanced Placement textbook, Java Methods AB: Data Structures.

   Chapter 02: Lists and Iterators Chapter 03: Stacks and Queues Chapter 05: Binary Trees

10. Study the following practice exercises on the left to get a good feel for how to solve problems in this chapter. Clicking on their links will present you with the publisher's solutions. Then solve and submit solutions to exercises on the right that will be reviewed for grading purposes.

    WARNING: Work through some or all of the practice exercises before attempting exercises to be submitted. Use the syntax and organization of the practice exercises as models. Failure to first study the practise exercises will probably result in significant frustration!

11. Do chapter 19's Programming Exercises For Grades in the following sequence. Use the given solutions related to the Programming Exercises For Practice as models of how to proceed.

    Linked Lists	19.07, 19.09, 19.21, 19.31, and 19.34.
    Stacks	19.12, 19.13 and 19.14.
    Queues	19.15 and 19.32.
    Binary SearchTrees	19.17, 19.22 and 19.33.

    Programming Exercises For Practice

    Programming Exercises For Grades

    19.06:     Write a program that concatenates two linked-list objects of characters. Class ListConcatenate should include a method concatenate that takes references to both list objects as arguments and concatenates the second list to the first list. 19.08:     Write a program that inserts 25 random integers from 0 to 100 in order into a linked list object. The program should calculate the sum of the elements and the floating-point average of the elements. 19.10:     Write a program that inputs a line of text and uses a stack object to print the words of the line in reverse order. 19.11:     Write a program that uses a stack to determine whether a string is a palindrome (i.e., the string is spelled identically backward and forward). The program should ignore spaces and punctuation. 19.16:     Modify the program of Fig. 19.17 and Fig. 19.18 to allow the binary tree to contain duplicates. 19.17:     Write a program based on the program of Fig. 19.17 and Fig. 19.18 that inputs a line of text, tokenizes the sentence into separate words (you might want to use the StreamTokenizer class from the java.io package), inserts the words in a binary search tree and prints the inorder, preorder and post-order traversals of the tree. 19.19:     Write a method depth that receives a binary tree and determines how many levels it has. 19.20:     (Recursively Print a List Backwards) Write a method printListBackwards that recursively outputs the items in a linked list object in reverse order. Write a test program that creates a sorted list of integers and prints the list in reverse order. 19.23:     (Binary Tree Search) Write method binaryTreeSearch, which attempts to locate a specified value in a binary search tree object. The method should take as an argument a search key to be located. If the node containing the search key is found, the method should return a reference to that node; otherwise, the method should return a null reference. 19.25:     (Printing Trees) Write a recursive method outputTree to display a binary tree object on the screen. The method should output the tree row-by-row, with the top of the tree at the left of the screen and the bottom of the tree toward the right of the screen. Each row is output vertically.

    Documetation for the following exercises must include: Internal Javadoc comments that generate an HTML file in the format of Sun's Java API Documentation. See pdf handout and associated examples of Javadoc. Hardcopy of each program's HTML Javadoc file. UML Class Diagram generated with VP-UML. In solving Deitel's exercise 19.07, when comparing the magnitude of objects, implement the abstract interface java.lang.Comparable and over-ride the corresponding abstract method compareTo(Object o). An interesting article at Java World discusses compareTo in Sort It Out. Also check out pp 173-174 of Walls and Mirrors, Java's API Specification for Interface Comparable, an interesting discussion in Sun's Java Technology Fundamentals newsletter of 30 April 2003, and the Java Practice of Implementing compareTo. 19.07:     Write a program that merges two ordered-list objects of integers into a single ordered list object of integers. Method merge of class ListMerge should receive references to each of the list objects to be merged and should return a reference to the merged list object. 19.09:     Write a program that creates a linked list object of 10 characters, then creates a second list object containing a copy of the first list, but in reverse order. Before solving Deitel's exercises 19.12, 19.13 and 19.14 below, read "Chapter 4: Stacks" (pages 169-204) in Larry Nyhoff's textbook C++ An Introduction to Data Structures. Pay particular attention to the section "Application of Stacks to Reverse Polish Notation" (pages 193-201). Answer all odd-numbered exercises found on pages 204-206. Before solving Deitel's exercises 19.12, 19.13 and 19.14 below, you should also read "Chapter 6: Stacks" in the textbook by Carrano, Frank M. and Paul Helman and Robert Veroff, 1998, Data Abstraction and Problem Solving with C++: Walls and Mirrors (Addison Wesley Longman, Inc.: Don Mills, Ontario). 19.12:     Write a Java version of the infix-to-postfix conversion algorithm. 19.13:     Write a Java version of the postfix expression evaluation algorithm. 19.14:     Modify the postfix evaluator program of Exercise 19.13 so that it can process integer operands larger than 9. Before solving Deitel's exercise 19.15 below, read "Chapter 5: Queues" (pages 211-240) in Larry Nyhoff's textbook C++ An Introduction to Data Structures. Before solving Deitel's exercise 19.15 below, you should also read "Chapter 7: Queues" in the textbook by Carrano, Frank M. and Paul Helman and Robert Veroff, 1998, Data Abstraction and Problem Solving with C++: Walls and Mirrors (Addison Wesley Longman, Inc.: Don Mills, Ontario). 19.15:     (Supermarket Simulation) Write a program that simulates a checkout line at a supermarket. 19.17:     (BST Traversals) Write a program that inserts words in a binary search tree and prints the inorder, preorder and post-order traversals of the tree. Deitel's exercise 19.21 asks you to prompt the user for a value to locate in a linked list. You may wish to learn or review how to read data from a command line prompt and convert it to a numerical (integer or floating point) value. To do so, study Kjell's chapter 10 tutorial, Input and Output. 19.21:     (Recursively Search a List) Write a method searchList that recursively searches a linked list object for a specified value. Before solving Deitel's exercise 19.22 below, read "Chapter 10: Binary Trees" (pages 513-569) in Larry Nyhoff's textbook C++ An Introduction to Data Structures. 19.22:     (Binary Tree Delete) Delete items from binary search trees. 19.23:     (Binary Tree Locate) Locate a specified value in the Binary Search Tree object. 19.31:     (Insert/Delete Anywhere in a Linked List) Our linked-list class allowed insertions and deletions at only the front and the back of the linked list. These capabilities were convenient for us when we used inheritance or composition to produce a stack class and a queue class with a minimal amount of code simply by reusing the list class. Linked lists are normally more general than those we provided. Modify the linked-list class we developed in this chapter to handle insertions and deletions anywhere in the list. 19.32:     (Lists and Queues without Tail References) Our implementation of a linked list ( Fig. 19.3) used both a firstNode and a lastNode. The lastNode was useful for the insertAtBack and removeFromBack methods of the List class. The insertAtBack method corresponds to the enqueue method of the Queue class. Rewrite the List class so that it does not use a lastNode. Thus, any operations on the tail of a list must begin searching the list from the front. Does this affect our implementation of the Queue class ( Fig. 19.13)? 19.33:     (Performance of Binary Tree Sorting and Searching) One problem with the binary tree sort is that the order in which the data is inserted affects the shape of the tree—for the same collection of data, different orderings can yield binary trees of dramatically different shapes. The performance of the binary tree sorting and searching algorithms is sensitive to the shape of the binary tree. What shape would a binary tree have if its data were inserted in increasing order? in decreasing order? What shape should the tree have to achieve maximal searching performance? In solving Deitel's exercise 19.34, ensure that the list is maintained as an ordered list. Thus method insertInIndexedList() must insert new nodes in the appropriate ordered position of a single linked list. Why? If we go to the trouble of creating and maintaining an index to the list to increase the speed of searching, then we should also ensure that the list remains sorted so that a search may be abondoned as soon as it is determined that an item is not in the list without having to search the entire segment of the list. =================== Also, in solving Deitel's exercise 19.34, first construct a single linked list with 26 different nodes, each node containing a different alphabetical ('A' ... 'Z') character. Then construct a one dimensional array containing 26 references (addresses) to the 26 different nodes of the linked list. Each node in the linked list will be the "head" of a segment of the linked list. Do not construct 26 different linked lists. 19.34:     (Indexed Lists) As presented in the text, linked lists must be searched sequentially. For large lists, this can result in poor performance. A common technique for improving list-searching performance is to create and maintain an index to the list. An index is a set of references to key places in the list. For example, an application that searches a large list of names could improve performance by creating an index with 26 entries—one for each letter of the alphabet. A search operation for a last name beginning with 'Y' would then first search the index to determine where the 'Y' entries begin, then "jump into" the list at that point and search linearly until the desired name is found. This would be much faster than searching the linked list from the beginning. Use the List class of Fig. 19.3 as the basis of an IndexedList class. Write a program that demonstrates the operation of indexed lists. Be sure to include methods insertInIndexedList, searchIndexedList and deleteFromIndexedList.

12. Include the following documentation for each exercise that is submitted to be graded.

    1. List the specifications of the program. These may be deduced in the statement of the exercise.

    2. Source Code of all new files: html file for applets, class file(s), driver program(s).

       Print the source code and screen dump in a Word Processor, two pages per side, double sided. Simultaneously pressing [Alt][PrtScn] will copy the GUI output to the clipboard from whence you can paste it just below your source code. Use a non-proportional font (example: Courier New) to maintain the vertical alignment of the stucture of your source code.

    3. Screen Shots of Input and Output dialog boxes.

       Where I/O (Input/Output) inlcudes multiple GUI (Graphical User Interface) dialog boxes, include at least one screen shot for each input and output dialog box. Where there are various types of dialog boxes and/or messages and/or types of data, include a "reasonable" number of screen shots.

       Typically there will be 1-2 screen shots showing input and 1-2 screen shots showing output. In extraordinary cases, there could conceivably be a dozen or more screen shots. What is "reasonable" is the product of using reason (thought) and reasons (related information). BE REASONABLE!

13. There will be a multiple choice test at the end of this chapter.

Warning: Students will NOT receive credit toward their IB Dossier mastery techniques for use of Java's Collection interface and Collections class..

Assignments

1. Overview the Chapter 21 PowerPoint Slideshow. This just gives you the "lay of the land" for now. Later, after you read the chapter, this slide show will be a very meaningful review.

2. Read the chapter actively! Execute and tinker with the code. Draw diagrams of concepts.

3. Implement and run the Chapter 21 source code.

4. Mentally review the "Self-Review Exercises" (1234) (The section containing the answers to these questions follows in the book itself.) This may easily alert you to potential holes in your knowledge and skills.

5. Read Eck's Explanation of Generic Programming and Collection Classes

   Read Chapter 12: Generic Programming and Collection Classes from the 4th edition of David Eck's book Introduction to Programming Using Java.

   
   

6. Study the following practice exercises on the left to get a good feel for how to solve problems in this chapter. Clicking on their links will present you with the publisher's solutions. Then solve and submit solutions to exercises on the right that will be reviewed for grading purposes.

   WARNING: Work through some or all of the practice exercises before attempting exercises to be submitted. Use the syntax and organization of the practice exercises as models. Failure to first study the practise exercises will probably result in significant frustration!

   Programming Exercises For Practice

   Programming Exercises For Grades

   21.03:     Define each of the following terms: Collection Collections Comparator List See Virtual Course, Chapter 21, "Selected Answers", for answers. 21.05:     Explain briefly the operation of each of the following Iterator-related methods: iterator hasNext next See Virtual Course, Chapter 21, "Selected Answers", for answers. 21.06:     State whether each of the following is true or false. If false, explain why. Elements in a Collection must be sorted in ascending order before performing a binarySearch. Method first gets the first element in a TreeSet. A List created with Arrays.asList is resizable. Class Arrays provides static method sort for sorting array elements. See Virtual Course, Chapter 21, "Selected Answers", for answers. 21.07:     Rewrite method printList of Fig. 21.4 to use a ListIterator 21.08:     Rewrite lines 16-23 in Fig. 21.4 to be more concise by using the asList method and the LinkedList constructor that takes a Collection argument. 21.12:     Rewrite your solution to Exercise 19.8 to use a LinkedList collection. 21.16:     Write a program that tokenizes (using class StreamTokenizer) a line of text input by the user and places each token in a tree. Print the elements of the sorted tree.

   Documetation for the following exercises must include: Internal Javadoc comments that generate an HTML file in the format of Sun's Java API Documentation. See pdf handout and associated examples of Javadoc. Hardcopy of each program's HTML Javadoc file. UML Class Diagram generated with VP-UML. 21.09:     Write a program that reads in a series of first names and stores them in a LinkedList. Do not store duplicate names. Allow the user to search for a first name. 21.10:     Modify the program of Fig. 21.13 to count the number of occurrences of all letters (e.g., five occurrences of "o" in the example). Display the results. 21.11:     Write a program that determines and prints the number of duplicate words in a sentence. Treat uppercase and lowercase letters the same. Ignore punctuation. 21.14:     Write a program that takes a whole-number input from a user and determines if it is prime. If the number is prime, add it to a JTextArea. If the number is not prime, display the prime factors of the number in a JLabel. Remember that a prime number's factors are only 1 and the prime number itself. Every number that is not prime has a unique prime factorization. For example, consider the number 54. The factors of 54 are 2, 3, 3 and 3. When the values are multiplied together, the result is 54. For the number 54, the prime factors output should be 2 and 3. Use Sets as part of your solution.

7. Include the following documentation for each exercise that is submitted to be graded.

   1. List the specifications of the program. These may be deduced in the statement of the exercise.

   2. Source Code of all new files: html file for applets, class file(s), driver program(s).

      Print the source code and screen dump in a Word Processor, two pages per side, double sided. Simultaneously pressing [Alt][PrtScn] will copy the GUI output to the clipboard from whence you can paste it just below your source code. Use a non-proportional font (example: Courier New) to maintain the vertical alignment of the stucture of your source code.

   3. Screen Shots of Input and Output dialog boxes.

      Where I/O (Input/Output) inlcudes multiple GUI (Graphical User Interface) dialog boxes, include at least one screen shot for each input and output dialog box. Where there are various types of dialog boxes and/or messages and/or types of data, include a "reasonable" number of screen shots.

      Typically there will be 1-2 screen shots showing input and 1-2 screen shots showing output. In extraordinary cases, there could conceivably be a dozen or more screen shots. What is "reasonable" is the product of using reason (thought) and reasons (related information). BE REASONABLE!

8. There will be a multiple choice test at the end of this chapter.