CSE 221 Lab 8

Table of Contents

• Lab 8 - Part 1
• Lab 8 - Part 2

CSE 221 Lab 8-Part 1

Table of Contents

• Objectives
• The Problem
• Set Up
• Method
• VERY IMPORTANT NOTE
• What To Turn In
• Want To Do More?

Objectives

• Familiarity with using Natural_Number objects and operations.
• Familiarity with using interval halving to invert a function.

The Problem

Set Up

1. In an xterm window, create a new directory (folder) for this lab by typing the "make directory" command:

        mkdir lab08-part1

2. Change or move to the new directory (folder) for this lab by typing the "change directory" command:

        cd lab08-part1

3. Copy the catalog for this lab by typing the "copy" command:

       cp -R /class/sce/now/221/labs/catalogs/lab08-part1/* . 

   NOTE: The period . is part of the command. It denotes the current directory (folder).
   
   

   This "copy command" will copy recursively (because of the -R) all the files and directories from the shared class directory into your directory, effectively duplicating the entire substructure from the class directory into your directory.




4. To see what was copied, type the "list" command:

        ls

   You should see
   • two files: Root_Test.cpp and Root_1_Test.cpp
   • four directories: AI, AT, CT, and CI
   
   

   In the directories AI and CI, you will see a Natural subdirectory. Within AI/Natural you will see two files: Power.h and Root.h. Within CI/Natural you will see one file: Root_1.h.

VERY IMPORTANT NOTE

1. Using the "change directory" cd command, move to the lab08-part1/CI/Natural directory.
   
   
2. Copy the Power_2.h file by typing the "copy" command:

       cp  /class/sce/now/221/labs/catalogs/lab08-part1/CI/Natural/Power_2.h . 

   NOTE: The period . is part of the command. It denotes the current directory (folder).
   
   

Method

Step 1 - Coding Root as a global operation

1. Examine the file Root_Test.cpp, which is a simple test driver for global_procedure Root specified below:

global_procedure Root (
        alters Natural_Power_2& n,
        preserves Integer r
    );
/*!
    requires
        r > 0
    ensures
        n^(r) <= #n < (n+1)^(r)
!*/

2. Write a body for the Root operation that uses the interval halving algorithm as illustrated in the "Interval Halving" worksheet. This body goes into Root_Test.cpp. Notice that n is of type Natural_Power_2, so in addition to all the Natural_Number operations you may also invoke the Power operation on n -- and you'll need to do this in order to implement the interval halving algorithm!

 
3. Test the above implementation, revising as necessary until you're convinced that this implementation of Root works. Remember, to do this you'll need the file Power_2.h that contains a correct body for Power. So if you haven't got this from Lab 7, you'll need to complete this step after 5:00 pm, Saturday, May 30. The grader will look at the source code of Root_Test.cpp and the output of Root_Test to grade this section of the lab.

Step 2 - Making Root an extension

1. Examine the file Root_1_Test.cpp, which is the same simple test driver as above but this time for Root as an extension in abstract_instance class Natural_Root, which is in the file AI/Natural/Root.h in your lab08-part1 directory.

 
2. Write a body for the Root operation in the file CI/Natural/Root_1.h, in your lab08-part1 directory, using the interval halving algorithm. DO NOT write the body in the test driver. This should be very staightforward if you completed the first part of the lab!

 
3. Test Natural_Root_1::Root, revising the operation body as necessary until you're convinced that this implementation of Root works. The grader will look at the source code of Root_1_Body.h and the output of Root_1_Test to grade this part.

What To Turn In

• The files Power.h, Power_2.h, Root.h, and Root_1.h with your implementation of Root as an extension.
• Root_Test.cpp (with Root as a global operation) and Root_1_Test.cpp (with Root as an extension).

rcpp-submit c221xx lab08-part1

Want To Do More?

• Write another implementation (say, Natural_Root_2) of abstract_instance class Natural_Root using interval halving with a smaller starting interval. It turns out that you can start not with the interval [0,#n+1) but with the (generally much smaller) interval [10^k, 10^k+1), where k is the greatest integer less than or equal to (|#n|-1)/r. Here, |#n| denotes the discrete log of #n. Compare performance of the two implementations.

CSE 221 Lab 8-Part 2

Table of Contents

• Objectives
• The Problem
• Set Up
• Method
• What To Turn In

Objectives

• Familiarity with using Natural_Number objects and operations.
• Familiarity with using template components.

The Problem

Set Up

1. In an xterm window, create a new directory (folder) for this lab by typing the "make directory" command:

        mkdir lab08-part2

2. Change or move to the new directory (folder) for this lab by typing the "change directory" command:

        cd lab08-part2

3. Copy the catalog for this lab by typing the "copy" command:

       cp -R /class/sce/now/221/labs/catalogs/lab08-part2/* . 

   NOTE: The period . is part of the command. It denotes the current directory (folder).
   
   

   This "copy command" will copy recursively (because of the -R) all the files and directories from the shared class directory into your directory, effectively duplicating the entire substructure from the class directory into your directory.




4. To see what was copied, type the "list" command:

        ls

   You should see
   • two files: Nice_Display.cpp and data.txt
   • four directories: AI, AT, CT, and CI
   
   

   In the directories AI and CI, you will see a Natural subdirectory. Within AI/Natural you will see the file Put_To_With_Commas.h and within CI/Natural you will see the file Put_To_With_Commas_1.h.

Method

1. In the Global Context section of Nice_Display.cpp, fill in the two template instantiations creating
   
   
   • a component called Queue_Of_Naturals which is an appropriate customized version of Queue_Kernel_1a_C.
   • a component called Sequence_Of_Queue_Of_Naturals which is an appropriate customized version of Sequence_Kernel_1a_C.
   
   
2. Provide operation bodies implementing Create_Display_Representation and Display_Width.
   
   
3. Modify program_body main () of Nice_Display.cpp so that it displays a "NICE_DISPLAY" of the natural numbers that are in the sequence object called s.
   
   
4. After successfully compiling Nice_Display.cpp, you can test it by typing the command

   Nice_Display < data.txt

   in a terminal window.
   
   

What To Turn In

rcpp-submit c221xx lab08-part2