Computer Science 202


Pre-2006 Computer Science 202 Web Page


Immediate Strategy of Term Beginning Term 3 in January - April, 2008

  1. Boolean Algebra
  2. Bit and Shift Operations
  3. Arrays Using Kjell Tutorials
  4. String Handling
  5. Test Driven Development


Today's files are BIG. Consider a flash drive.

CLICK HERE TO INSTALL JAVA & ECLIPSE

TopicAssignments

Test-Driven Development

Shortcut To Print To Console:   Enter the "stuff" to be printed. → Highlight "stuff" with the mouse. → <Ctrl-Space> → <Up-Arrow> → <Enter> → Eclipse surrounds the "stuff" with System.out.println( ).

To create a separate testing folder to isolate JUnit testing code from application code:   File → New → Source Folder → Folder Name: test → Finish. This avoids deploying testing code with an application.

To create a JUnit package containing the same name as the application package being tested:   Select ("highlight") the name of the testing folder in the package view → File → New → Package → Type the same name as the source code package. (Both the application and testing package have the same names.) → Finish.

To create a JUnit test class:   Right mouse click the testing package → New → Other → JUnit → JUnit Test Case → Type name of testing class == name of class to be test followed by "Test" (eg: "BeHappyTest") → Place desired ✓s for method stubs → Finish → Finish.

To create a JUnit test suite:   Highlight the testing package. → Right mouse click → New → Other → JUnit → JUnit Test Suite → Next → Place desired ✓s → Finish. This creates a single-button test for an entire application!

Names of all JUnit testing methods begin with "test..."

Variable name that is italicized is a static variable.

To open a new Java Scrapbook Page:   File → New → Other.... → Select Java → Java Run/Debug → Scrapbook Page. → Click Next. Don't forget to later select ("highlight") the code before clicking the "inspect" button.

To automatically generate accessor &/or mutator methods:   Source → Generate Getters and Setters... → Place desired ✓s → OK.

Quick Fix:   <Ctrl><1> ( ie: Control-One ) OR Click on the light bulb. The Java editor offers corrections for most problems underlined with a problem highlight line.

TODO Comment:   // TODO tada tada tada
(No space between "TO" and "DO") Eclipse maintains a task "ToDo" list for you. Window → Show View → Tasks.

Comment a section of code:   Highlight the section of code → <Ctrl>< / > Toggling <Ctrl>< / > "uncomments" commented code.

To provide package access to a class member:   Remove all scope modifiers. Scope modifiers are private, public and protected.

To convert a local variable to an instance variable (ie: instance "field"):   Select a declaration or a reference to a local variable → Refactor → Convert Local Variable to Field... → Select access modifier → Select location for initialization → Select whether field is to be static → Select whether field is to be final (ie: a constant) → OK

To automatically extract a method from a block of code:   Highlight the lines → Refactor → Extract Method... → Type methodName → OK Same blocks of code throughout the class are replaced by the method call!

To automatically create a public method template:   Type "pub" (initial three letters of "public") → <Ctrl-Space> → Select "Public_method - public method" → Type "void" or other return type → Enter → Tab → Type "testToString" or other name of method Do a similar process for a private method template.

To automatically create the public static void main( String[ ] args ) template:   Type "main" → <Ctrl-Space> → Press <Enter> This is the point in Java where execution of the program begins.

To automatically create an assertEquals( expected, actual) call:   Type "asserte" (initial letters of "assertEquals...") → <Ctrl-Space> → Press Enter → Type "Smith" or other string → Enter → Tab → Type b2.toString() or other string reference call → Type a semicolon to end the statement Do a similar process for other standard method calls.

Test-Driven Development
  1. Think about what the method should do.
  2. Write a test case that will test this method.
  3. Write the new method.
  4. Test the new method.
  5. When it passes ... we're done!

... the unit tests document the program without the need to maintain separate written documentation that can easily become out of date.

Mark Dexter, Using Test-First Development


Follow and implement the lessons and activities of Mark Dexter's sixteen 15-minute tutorials of Eclipse And Java For Total Beginners [csg] [web]

Toggle <F11> to switch between IE's normal and full screen views.

Toggle <Alt-Tab> to switch to your last application, as between Eclipse (program development) and Internet Explorer (tutorial).

Preserve the project at the end of each tutorial. To do this, create a new project at the beginning of each tutorial and import the project from the end of the last tutorial into a the new tutorial's project. Projects can be called TB1, TB2 .... (TB == Total Beginner)

Refer to this Tutorial Companion Guide [pdf].

Beware This GOTCHYA: The tutorial code refers to an object "ml" of a class "MyLibrary". The "ml" is "m" followed by the letter "l" (pronounced "el"), not the digit "1" (one).

  1. Create Your First Class
  2. Add Methods to Class
  3. Use Eclipse Scrapbook
  4. JUnit: Create Test Class
  5. JUnit: Create Test Methods
  6. Using Test-First Development
  7. Create Book Class
  8. Add Person to Book Class
  9. MyLibrary Class and ArrayList
  10. Start on MyLibrary Class
  11. Create first methods in MyLibrary class
  12. Create checkOut( ), checkIn( ) Methods
  13. Continue checkOut( ) Method
  14. Finish checkOut( ) Method
  15. Finish MyLibrary Methods
  16. Create main( ) Method and JAR File

For the final code, including all application and testing code, submit a printed copy of a wordprocessing document containing:

  1. Footer
  2. BIG JAVA's Formatting Style by importing UBC's file.
  3. Identification Template
  4. Screen Dump(s)
  5. HTML Javadoc files including the standard tags @author, @version, @param, @return and the customized tags @invariant, @pre and @post
  6. Print on both sides of a sheet of paper, two pages per side = = four pages per sheet of paper. See Make Hard Copy of Source Code.

To create an executable JAR file:   [ Hint: First save the path to your project so you can later paste it as the destination location of your executable JAR file → Right mouse click name of project → Properties → Select ("highlight") the location (eg: "H:\TotalBeginnerProjects\TB11") → Copy with → Cancel ] File → Java → JAR file → Next > → Select by checking ✓ only the #src directory → Select a directory to save the JAR file in → Give the JAR file a name (eg: mylibrary.jar) → Next > → Tell Eclipse which class has the main() method (Click the "Browse..." button.) → Finish    JAR == Java ARchival File. An executable JAR file will execute on any system that has a JRE (Java Runtime Engine) installed. Selecting only the #src directory allows us to now easily exclude the bundling of testing code with the application.

To check the run of your JAR file from the command line prompt:   Copy the path of your JAR file location: Right mouse click name of JAR file → Properties → Select ("highlight") the location sans name of file (eg: "H:\TotalBeginnerProjects\TB16") → Copy with <Ctrl-C> → OK ] → [ Note: In order for the JAR file to "automatically" execute at the command line prompt, the O/S environmental path variable must be contain the path to Java's jar.exe file. An example of the location of a jar.exe file is: C:\Program Files\Java\jdk1.6.0_01\bin.] → Start → Run... → Type cmd in the Open dialog window → A command prompt window (aka DOS window) opens → On the prompt line, type the drive location of the file (eg: "H:) → Press <Enter> → The prompt now reflects the root of the drive where the JAR file is located ( eg: H:\> ) → On the prompt line, type "cd" (stands for "change directory") → Press the space bar once. → Right mouse click the title bar. → Edit → Paste → The prompt line should now include the path of the JAR file. [ eg: H:\TotalBeginnerProjects\TB15\TB16> ] → Type "dir" to call the directory → You should now see the jar file. → At the command line, type "java -jar followed by the name of the jar file. [ eg: java -jar mylibrary.jar ] → Press <Enter> → The JAR file should now execute.

Create A "New" Project From An Existing Project

These are really "backups of prior stages" of a single, cumulative project. It would be tragic if, upon experiencing a "bug" during tutorial #12 that could not be corrected, you had to redo all eleven prior tutorials in order to continue the project. Taking a few moments at the beginning of each new stage of the project (each new tutorial) ensures that you always have a "last good stage" that is only one tutorial away. This also facilitates later review of code of a specific tutorial at that particular stage of development.

  1. Create a new project:   File → New → Project.. → Java → Java Project → Next → Project Name: TB12 → Create new project in workspace → Select a JRE (Java Runtime Environment) → Select Project layout → Finish

  2. Copy path of location of source project:   Right mouse click name of project → Properties → Select ("highlight") the location (eg: "H:\TotalBeginnerProjects\TB11") → Copy with <Ctrl-C> → Cancel

  3. Open the Import Wizard:   Select ("highlight") name of new project → From the main menu bar, select File → Import....

  4. Select Type of Resources To Import:   General → File System → Next.

  5. Specify Path and Files To Import:   Identify source directory as the "From directory:" → Paste <Ctrl-V> location of the source project (eg: "H:\TotalBeginnerProjects\TB11") → Click the "Browse..." button → The "Import from directory" dialog box appears with name of source folder → Click "OK" → Click the "Select All" button → Type name of "Into folder" (existing destination folder) if it is not already there. → Check ✓ "Overwrite existing resources without warning" → Select "Create selected folders only" → Finish

ResourcesAssignments

Boolean
Algebra

In past years students successfully practiced Boolean Logic with Electronic Workbench 5.12. It is more powerful than Eck's xLogicCircuits Java applet, but has a steeper learning curve. Eck's xLogicCircuits applet is sufficient to practice all of the electronic aspects of Boolean Logic that we require. Less powerful but interesting programmes that allow us to practice Boolean logic are:

  1. xLogicCircuits applet and labs & other applets
  2. DLSim 2.2
  3. Leggo My Logg-O
  4. Logic Gates Circuit Simulation Program
  5. Digital Workshop
  6. Multimedia Logic
  7. Xilinx ISE WebPACKTM
  8. The Iowa Logic Specificaiton Language

Check out former student web pages on this topic:

  1. Boolean Logic by Lisa Chen (2002).
  2. Boolean Logic by Brian Lau (2003).
  3. Karnaugh Maps by Jacky Yeung (2003).

Boolean Algebra

The ACSL Handout: Boolean Algebra [doc] offers a brief introduction.

Read How Boolean Logic Works on the web site How Stuff Works.

Digital Logic by Ken Bigelow offers a structured and cohesive introduction to Boolean Logic.

Richard Jones' treatment of IB - Boolean Logic as found on his web site, IB Computing Home clarifies IBO's expectations.

Check out xLogicCircuits Lab 1: Logic Circuits from David Eck's book, The Most Complex Machine: A Survey of Computers and Computing.

Do all 10 exercises in Eck's LogicCircuits Lab 1: Logic Circuits [csg] [web].

You cannot normally save from an applet. Do a screen dump to a wordprocessor or paint programme to capture the image: Focus (mouse click) on the applet --> [Alt-PrtScn] --> Go to wordprocessor or paint program --> Focus --> [Ctrl-v].

Note: It is possible to import the files associated with the applet into Eclipse, launch the applet from within Eclipse, and then save the diagrams from the applet. To do this:

  1. Download the applet's source code files from Eck's Source Code Page:

    • the folder:   xLogicCircuits/
    • the file:   xLogicCircuitsApplet.java
    • the file:   xLogicCircuitsFrame.java
    • the file:   xLogicCircuitsLauncher.java

    OR

    import the Eclipse project from this Circuit directory.

  2. To import the project into Eclipse, do this:

    Launch Eclipse → File → Import... → Existing Projects in Workspace → Next> → Select root directory: copy path of the Circuit directory → Browse → Check the box of the Project "Circuit" → Finish → Expand (click "+" sign) the newly imported project "Circuit" → Expand the directory "src" → Expand the package "tmcm" → Select (right mouse click) "xLogicCircuitsLauncher.java" → Run as → Java applet.

  3. Circuit Diagrams may now be named, saved and loaded from within Eclipse.

Check out xLogicCircuits Lab 2: Memory Circuits from David Eck's book, The Most Complex Machine: A Survey of Computers and Computing.

Do all 9 exercises in Eck's xLogicCircuits Lab 2: Memory Circuits [csg] [web].

You cannot normally save from an applet. Do a screen dump to a wordprocessor or paint programme to capture the image: Focus (mouse click) on the applet --> [Alt-PrtScn] --> Go to wordprocessor or paint program --> Focus --> [Ctrl-v].


TopicAssignments

Bit and Shift
Operations

OperatorLogicalBitwise
NOT!~
AND&
&&
&
OR|
|  |
|
XOR^ ^
shift leftNot Applicable<<
arithmetic shift rightNot Applicable>>
bitwise shift rightNot Applicable>>>

Check out this TopCoder article: A bit of fun: fun with bits

The ACSL Handout Bit-String Flicking [doc] uses the slang but colourful term flicking to describe these operations which change a one to zero and vice versa.

Review interesting presentations of Boolean Expressions and Short-circuit Operators and Truth Tables and De Morgan's Rules by Bradley Kjell.

Bit and Shift operations are summarized in Horstmann's Big Java 2nd Ed, Appendix M, pages 1158-1160.

This topic is better described as Binary Numbers and Logical Operators. It is an extension of the larger topic about Java Operators.

Note that a pair of symbols are used for the logical operations, "logical AND" [&&] and "inclusive OR" [ | | ] whereas a single symbol is used for bitwise operations, "bitwise AND" [&], "inclusive OR" [ | ], and "exclusive OR" [^].

The usefulness and application of these operations are seen in context in Kjell's course for assembly language programming, Programmed Introduction to MIPS Assembly Language. See in particular Kjell's chapters:

  1. Immediate Operands and Bitwise Logic
  2. Shift Instructions and Logic Instructions

Bit and shift operations compare equivaltent binary patterns of decimal or other integers. See example below.

public class BooleanOps
{
   public static void main(String[] args)
   {
      System.out.println(3 & 22);                 // 2
      System.out.println(13 ^ 6);                 //11
      System.out.println(0 & (3-3));              // 0
      System.out.println(45 | 16);                //61
      System.out.println((2 & 5) | ((7^3) & 5 )); // 4
   }
}
XOR is supported by Java, but it is not possible to short-circuit an XOR expression because overall evaluation of the XOR expression always depends upon both operands. Java uses the caret (aka "circumflex") [^] as its XOR operator.

public class DemoXOR
{
    public static void main( String[] args )
    {
        int x = 5, z=10 ;
        if ( (x<10) ^ (z>5) )
            System.out.println("True Block") ;
        else System.out.println("False Block");
    }
}
TopicAssignments

Chap 8
Arrays
and
Array Lists

Horstmann Chap 8

Kjell 46 47 48 49A 49B 49C 49D

Sedgewick Chap 2.5

Litvin Chap 12

Deitel Chap 7

Horstmann 8

Wu 10

King 5

Litvin 12 12½

Chapter 8 Demo Source Code

ArrayListTester.java BankAccount.java
Bank.java BankAccount.java BankTester.java
TicTacToe.java TicTacToeTester.java

Study the Kjell chapters: 46 47 48 49A 49B 49C 49D

Do exercises of the above Kjell chapters on arrays before appplying Java's Array List class:   46 [1-5], 47 [1-5 ], 48 [1-3], 49B [1-3], 49C [1-9] and 49D [1-3].

Study Kjell's Tutorial in ArrayLists and Iterators.

Study Horstmann's Arrays and Array Lists: Chapter 8.

Programming Exercises To Be Graded (pp 315-319): P8.2, P8.4, P8.6, P8.8, P8.10, P8.12, P8.14, P8.16, P8.18.

For each exercise, submit a printed copy of a wordprocessing document containing:

  1. Footer
  2. BIG JAVA's Formatting Style by importing UBC's file.
  3. Identification Template
  4. Screen Dump(s)
  5. HTML Javadoc files including the standard tags @author, @version, @param, @return and the customized tags @invariant, @pre and @post
  6. Print on both sides of a sheet of paper, two pages per side = = four pages per sheet of paper. See Make Hard Copy of Source Code.
TopicResourcesSlide ShowAssignments

Chap 9
Designing Classes

How do I get the assert statement to work?

Go to Window -> Preferences -> Java -> Compiler and set the Compiler Compliance Level to 1.4, 5.0 or 6.0. Also check Use Default compliance settings. This tells the compiler to recognize and allow assert statements, but does not enable them.

To enable (make active) assert statements, you must set a flag to the compiler. Go to Run -> Run... -> Arguments, and in the box labeled VM arguments:, enter either -enableassertions or just -ea. Accept the changes and close the dialog.


Horstmann Chap 9

Kjell 25 26 27

Sedgewick Chap 2.6

Litvin Chap 9

Deitel Chap 8

Horstmann 1

Deitel 8

Wu 4

King 10

Study Horstmann's Designing Classes: Chapter 9.

Study Horstmann's Javadoc Summary in BIG JAVA, Appendix K, pages 1149-1151. Implement JavaDoc tags in documenting source code.

Refer to the UBC instructions, Using Custom tags with Javadoc and Eclipse. Customize Eclipse to use the @invariant, @pre, and @post JavaDoc tags.

This chapter does not have a model program.

Programming Exercises To Be Graded (pp 366-368): P9.2, P9.4, P9.6, P9.8, P9.10, P9.12, P9.14, P9.16.

For each exercise, submit a printed copy of a wordprocessing document containing:

  1. Footer
  2. BIG JAVA's Formatting Style by importing UBC's file.
  3. Identification Template
  4. Screen Dump(s)
  5. HTML Javadoc files including the standard tags @author, @version, @param, @return and the customized tags @invariant, @pre and @post
  6. Print on both sides of a sheet of paper, two pages per side = = four pages per sheet of paper. See Make Hard Copy of Source Code.
TopicResourcesSlide ShowAssignments

Chap 10
Testing
and
Debugging

Follow and implement the lessons and activities of Mark Dexter's seven 15-minute tutorials of Using the Debugger [csg] [web]

Refer to this Tutorial Companion Guide [pdf].
Import this DebuggerTutorial project into your Eclipse workspace.
  1. Startup, Step Over, Step Into, Step Return
  2. Examine Contents of Variables
  3. Add Watch Sessions, JUnit Tests
  4. Exception Breakpoints, Change Values
  5. Breakpoint Options, Watchpoints
  6. Debug into Java System Classes
  7. Study Recursion, Stack Frames

Horstmann Chap 10

Sedgewick Chap 3.0

Using the Debugger
[csg] [web]

Learn JUnit Testing

Horstmann 10

King 10

Chapter 10 Demo Source Code

Word.java
WordTester.java

junit/Numeric.java
junit/RootApproximator.java
junit/RootApproximatorTest.java

TaxReturn.java
TaxReturnTester.java

root1/Numeric.java
root1/RootApproximator.java
root1/RootApproximatorTest.java

root2/Numeric.java
root2/RootApproximator.java
root2/RootApproximatorHarness1.java
root2/RootApproximatorHarness2.java
root2/RootApproximatorHarness3.java
root2/RootApproximatorHarness4.java
root2/test.in

root3/Numeric.java
root3/RootApproximator.java
root3/RootApproximatorHarness5.java
root3/RootApproximatorHarness6.java

Follow and implement the lessons and activities of Mark Dexter's seven 15-minute tutorials of Using the Debugger [csg] [web]. See the lower pink box in the far left column.

Study Horstmann's Designing Classes: Chapter 10.

Note: You need not understand the math of the following exercises in order to do them!

Programming Exercises To Be Graded (pp 439-441): P10.2, P10.4, P10.6, P10.8, P10.10, P10.12.

Do the tutorials found in Learn JUnit Regression Testing.

For each tutorial, submit a printed copy of a wordprocessing document containing:

  1. Footer
  2. BIG JAVA's Formatting Style by importing UBC's file.
  3. Identification Template
  4. Screen Dump(s)
  5. HTML Javadoc files including the standard tags @author, @version, @param, @return and the customized tags @invariant, @pre and @post
  6. Print on both sides of a sheet of paper, two pages per side = = four pages per sheet of paper. See Make Hard Copy of Source Code.
TopicResourcesSlide ShowAssignments

Chap 11
Interfaces
and
Polymorphism

Horstmann Chap 11

Sedgewick Chap 3.0

Horstmann 11

King 10

Chapter 11 Demo Source Code

BankAccount.java Coin.java DataSet.java DataSetTester.java Measurable.java

DataSet.java DataSetTester2.java Measurer.java RectangleMeasurer.java

DataSet.java DataSetTester3.java Measurer.java

TimerTester.java

TimerTester2.java


Read Gerry Donaldson's explanation of an interface in response to another teacher's question.

Read Joe Bergin's explanation of an interface in response to another teacher's question.

Study the Kjell chapters:  

Programming Exercises To Be Graded: Kjell's Chapter 53B - Exercises 1 and 2

Study Horstmann's Interfaces & Polymorphism: Chapter 11.

Programming Exercises To Be Graded (pp 439-441): P11.2, P11.4, P11.6, P11.8, P11.10, P11.12, P11.14, 11.16, 11.18.

For each exercise, submit a printed copy of a wordprocessing document containing:

  1. Footer
  2. BIG JAVA's Formatting Style by importing UBC's file.
  3. Identification Template
  4. Screen Dump(s)
  5. HTML Javadoc files including the standard tags @author, @version, @param, @return and the customized tags @invariant, @pre and @post
  6. Print on both sides of a sheet of paper, two pages per side = = four pages per sheet of paper. See Make Hard Copy of Source Code.
TopicResourcesSlide ShowAssignments

Chap 13
Inheritance

Horstmann Chap 13

Sedgewick Chap 3.0

Horstmann 13

King 10

Chapter 13 Demo Source Code

AccountTester.java
BankAccount.java
CheckingAccount.java
SavingsAccount.java

Study Horstmann's Inheritance: Chapter 13.

Programming Exercises To Be Graded (pp 512-513): P13.2, P13.4, P13.6, P13.8.

For each exercise, submit a printed copy of a wordprocessing document containing:

  1. Footer
  2. BIG JAVA's Formatting Style by importing UBC's file.
  3. Identification Template
  4. Screen Dump(s)
  5. HTML Javadoc files including the standard tags @author, @version, @param, @return and the customized tags @invariant, @pre and @post
  6. Print on both sides of a sheet of paper, two pages per side = = four pages per sheet of paper. See Make Hard Copy of Source Code.

Read Gerry Donaldson's explanation of an interface in response to another teacher's question.

Read Joe Bergin's explanation of an interface in response to another teacher's question.

TopicAssignments

Chap 18
Recursion

"In order to understand recursion you must understand recursion."
- Dan R. Ghica, Java Workshop: Recursion

Three Rules For Recursion:

  1. Find out how to take just one step.

  2. Break each journey down into one step plus a smaller journey.

  3. Know when to stop.

Source: How TO teach and NOT TO teach Recursion (opinions from the experts?), page 14 [pdf] by Fran Trees


Check out the following two parts of a TopCoder tutorial that applies recursion to computing contest programming problems.

  1. An Introduction to Recursion, Part 1
  2. An Introduction to Recursion, Part 2

Teaching Strategies

  1. Martin and the Dragon
  2. Evaluate combo(4,3)
  3. The Cat In The Hat Comes Back

Real Recursion - Fibonacci Numbers and Nature

Kjell's Java Tutorials
70, 71, 72, 73, 74

Sedgewick Chap 2.7

Horstmann 18 [ppt]

Carrano/Savitch 10 [ppt]

Chapter 16, "Squashing Bugs", in Eclipse For Dummies by Barry Burd [ISBN: 0-7645-7470-1], pp 315-321

MIT Eclipse Debug Tutorial [pdf]

UBC Eclipse Debug Tutorial

Leszek's Eclipse Debug Tutorial

Wisconsin Eclipse Debug Tutorial

Quigley Eclipse Debug Tutorial

  1. Learn about recursion by studying the Recursion Tutorial [csg] [web] retrieved from the web site of North Carolina teacher Ruth Hartsook.

  2. Study Mark Dexter's 15-minute screencast tutorial Study Recursion, Stack Frames → Anatomy of a Recursive Method. Implement the tutorial's code after importing this Eclipse project. Go here for instructions on importing an Eclipse project.

  3. Read and do the recursive examples in Fran Trees' presentation, How TO teach and NOT TO teach Recursion (opinions from the experts?) [pdf].

  4. How does the song There's a Hole in the Bucket exemplify infinite recursion?

  5. Read and study the Kjell Java Tutorials covering "Recursion": 70, 71, 72, 73, and 74.

  6. Study Horstmann's Recursion: Chapter 18.

    Chapter 18 Demo Source Code

    Triangle.java TriangleTester.java
    PermutationGenerator.java PermutationGeneratorTester.java
    FibTester.java FibTrace.java FibLoop.java
    Evaluator.java ExpressionTokenizer.java EvaluatorTester.java

  7. Recursion = Russian Nesting Dolls: Russian nesting dolls (aka "matryoshka") may be seen as a metaphor for recursion. Can you see why? In what way does each smaller doll represent a smaller version of the same "problem" of the larger doll in which it was/is encased?

  8. Recursion = Shockwave app of a red square tilting recursively
    A neat animation of recursion (no source code) here.

  9. Recursion = Escher's Ascending Descending Staircase

    The animated M.C. Escher's Ascending Descending Staircase may also be viewed as a representation of recursion. It was retrieved from the site, M.C. Escher work (c) Cordon Art B.V. - Baarn - the Netherlands.

    Incidentally, the initials M.C. in Escher's name stand for "Maurtis Cornelis". Click here to see what Escher's actual Ascending Descending Staircase looked like.

    Now check out the beauty of the java code implementing recursion at The Animation of Recursion"


  10. Towers of Hanoi is the most famous recursion exercise in Computer Science. Virtually every book that covers recursion uses the Towers of Hanoi as either a demonstration or an exercise.


  11. Assignment for Programming Exercises To Be Graded

    1. First: Read and do the recursive examples in Fran Trees' presentation, How TO teach and NOT TO teach Recursion (opinions from the experts?) [pdf].

    2. Read and study the Kjell Java Tutorials on recursion: 70, 71, 72, 73, and 74

    3. Do the eleven Kjell exercises that correspond to the Kjell Java Tutorials on recursion: 70 (no exercises), 71 (1 exercise), 72 (2 exercises), 73 (5 exercises), and 74 (3 exercises).

    4. Do two Horstmann exercises in BIG JAVA, chapter 18 (pp 695-700): P18.2 and P18.4.

    5. Implement in Eclipse's JDT recursive source code that solves the Towers of Hanoi puzzle. You may obtain the source code from any source.

    6. For each exercise, submit a printed copy of a wordprocessing document containing:

      1. Footer
      2. BIG JAVA's Formatting Style by importing UBC's file.
      3. Identification Template
      4. Screen Dump(s)
      5. Print on both sides of a sheet of paper, two pages per side = = four pages per sheet of paper. See Make Hard Copy of Source Code.

TopicAssignments

Chap 19
Sorting
and
Searching

Horstmann 19 [ppt]

Roedy Green's
Canadian Mind Products

Eck's xSortLab Lab

Woi Ang's Sorting Animations

Duane Jarc's Interactive Visualizations

AVI clips of Students Sorting Cups

Big-O Notation [Wikipedia]

Sedgewick:    4   4.1   4.2  

Eck: Arrays, Searching, Sorting

Videotape: Sorting Out Sorting
[Baeker, 1981, ISBN: 1558600302]

Carrano & Savitch:
ppt --> 9  11  12  16 

PRACTICAL TEST: Students must schedule a time with their teacher to demonstrate various sorting algorithms using stacking cups.

BIG JAVA Chapter 19 Demo Source Code

Measuring Selection Sort in Milliseconds:
ArrayUtil.java SelectionSorter.java SelectionSortTester.java
SelectionSortTimer.java StopWatch.java

Measuring Selection Sort in Nanoseconds:
ArrayUtil.java SelectionSorter.java SelectionSortTester.java
SelectionSortTimer.java StopWatch.java

Insertion Sort:
ArrayUtil.java InsertionSorter.java InsertionSortTester.java

Measuring Merge Sort in Milliseconds:
ArrayUtil.java MergeSorter.java MergeSortTester.java
MergeSortTimer.java StopWatch.java

Measuring Merge Sort in Nanoseconds:
ArrayUtil.java MergeSorter.java MergeSortTester.java
MergeSortTimer.java StopWatch.java

Quick Sort (Uses Recursion):
ArrayUtil.java QuickSorter.java QuickSortTester.java

Linear Search:
ArrayUtil.java LinearSearcher.java LinearSearchTester.java

Binary Search:
ArrayUtil.java BinarySearcher.java BinarySearchTester.java

Read about Measuring Time In Java by Roedy Green.
  1. View Horstmann 19 Sorting and Searching Powerpoint Slide Show.

  2. Get an intuitive feeling for sorting generally and then the Insertion Sort and Quick Sort at Sorting Bricks and Sticks on the Berkley MathSite.

  3. View Measuring the Difficulty/Complexity of a Problem web page by Gerry Donaldson

  4. View Tradeoffs, Intuition Analysis, Understanding Big-Oh aka O-Notation Powerpoint Slide Show by Owen Astrachan. Also view the Java source code examples associated with this PowerPoint slide show.


  5. From the 2003 text Data Structures and Abstractions With Java by Frank M. Carrano and Walter Savitch [ISBN 0-13-017489-0], view the following Powerpoint slide shows.


  6. Read the brief Sedgewick 4 Fundamental Abstract Data Types

  7. Read the text and review all examples from Sedgewick 4.1 Analysis of Algorithms

  8. Read the text and review all examples from Sedgewick 4.2 Sorting

  9. A super reference (really an entire university 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.

  10. Read Eck's Explanation of Arrays
    Read Chapter 8: Arrays from the 4th edition of David Eck's book Introduction to Programming Using Java.

  11. You want to know how to trace and implement the searching and sorting algorithms.

  12. Read about the four sorting algorithm's required by IB's 2000 syllabus by viewing Raksha Vasudevan's Kyell-style tutorial, The 4 Array Sorts Required by IB.

  13. Ask Mr. Donaldson to let you view the 30 minute videotape entitled, "Sorting Out Sorting".
    [Baeker, Ronald M., published by Morgan Kaufman, 1981, ISBN: 1558600302]

  14. Check out xSortLab Lab: Sorting and the Analysis of Algorithms from David Eck's book, The Most Complex Machine: A Survey of Computers and Computing.

  15. Learn to demonstrate each of the six sorting algorithms with the stacking cups. Its fun and, incidentally, an excellent way to visualize and internalize each of the sorting algorithms, and that is our objective! First study the visualization of an algorithm. Then, once you have the hang of it, implement it using a dozen stacking cups.

  16. In the last term of 2002 the first eight students to take Computer Science 201 in Java were examined in their application of sorting algorithms using stacking measuring cups. Judge for yourself as you watch AVI clips of their final tests .. a physical demonstration of each of four different sorting algorithms using a dozen toddler stacking cups.

  17. Students must generate and/or complete trace tables of searching and sorting algorithms.

    Hint To Automatically Generate A Trace Table:

    1. Place an output statement with the heading before the first call to the loop or recursive method that generates the next "pass" of the sorting algorithm.

    2. Place an output statement in the body of the loop or recursive method which generates the next "pass" of the sorting algorithm so it will output the values of each of the variables.

    Check out an example of how to do this taken from an answer key by Gerry Donaldson to Question 16 of Paper 1 of the May, 2002 IB Higher Level final examinations: [WordPerfect file] [pdf file] [WORD file]

  18. Programming Exercises To Be Graded (pp 738-739): P19.2, P19.4, P19.8, P19.10, P19.12, P19.14.

    For each exercise, submit a printed copy of a wordprocessing document containing:

    1. Footer
    2. BIG JAVA's Formatting Style by importing UBC's file.
    3. Identification Template
    4. Screen Dump(s)
    5. HTML Javadoc files including the standard tags @author, @version, @param, @return and the customized tags @invariant, @pre and @post
    6. Print on both sides of a sheet of paper, two pages per side = = four pages per sheet of paper. See Make Hard Copy of Source Code.

  19. There will be three tests for this chapter.

    There will be the usual brief 20 question quiz.

    The quick sort must be reproduced without reference to resources other than the student's mind. Hint: Understand it thoroughly and you will be able to think your way through it.

    Students will physically demonstrate all of the following searching and sorting algorithms using 12 stacking cups.

    • Linear Search
    • Binary Search
    • Bubble Sort
    • Selection Sort
    • Insertion Sort
    • Bucket Sort
    • Quick Sort
    • Merge Sort

On the Internet Since March 9, 1996    URL:   http://www.comscigate.com    Last Revised:   January 25, 2006.