Table of Contents Syllabus Ada Resources Laboratory Assignments Lab 1: The Lovelace Tutorial Lab 2: Playing with Access Types Lab 3: Playing with OOP Lab 4: Writing An Adjust Procedure Comments on writing the Adjust procedure Lab 5: Writing A Finalize Procedure Lab 6: Stack Iterator Lab Lab 7: Binary Search Tree Lab Lab 8: AVL Restructuring Lab Lab 9: Coming soon Lab 10: GWU Lab Programming Assignments Assignment # 1 - Merge of two linearly linked structures Comments on Assignment 1 Assignment # 2 - The Two Way Linear Hunt [NOTE: Pay particular attention to what must be submitted. I expect to see well documented code.] Assignment #3 - Recursive Hunt. do the hunt assignment as a recursive program based upon the recursive list paradigm and use List_Polymorphic_Cntl. Assignment #4 - The Border Crossing Problem Assignment #5 - Sorting Out Sorts Tests Test 1: 14 Feb Comments on Test 1 Test 2: 13 Mar Test 3: 24 Apr Final Exam: 13 May Grades

Cmps 240 (Spring 1996) Data Structures and Algorithms

Syllabus

Laboratory Assignments

Lab 1: The Lovelace Tutorial

Goal: The purpose of this laboratory assignment is to acquaint you with surfing the web and for you to take a look at the Lovelace tutorial that was written by David Wheeler of IDA. As the course progresses and you find yourself having difficulty with certain aspects of Ada, make use of this tutorial to gain insight into the various features of the language.

The Assignment: Use Netscape Navigator, either from the Suns, or from any other scource (there are some PCs that are on the net that have Netscape on them). Access the URL, http://academic.uofs.edu/faculty/beidler/. From that web page you can directly access the Lovelace tutorial. Spend some time browsing the tutorial. Complete at least one of the tutorial's Lessons.

Due Date: You must complete this laboratory assignment by 12 midnight Sunday February 4, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: In class you were assignned a lesson number. From the tutorial's Table of Contents click on your assigned lesson number and bring that lesson up. Pull down the File menu and use the Save option to same the page your viewing in a file. Simply email that file containing that page to beidler@cs.uofs.edu

Lab 2: Playing with Access Types

Goal: Learn about the basics of working with pointer (access types)

Assignment:Do the following:

• Get the code and data file for this assignment. Do this by clicking on the pointers below to ftp these items to your directory
  • ftp tile.dat
  • ftp tile_lab.adb
  • If the ftp does not work, the files may be copied from the ~beilder/Cmps_240/ directory on the Suns on to a 3.5" microdisk by using the mcopy command.
• Study the program. Pay particular attention to the procedure Get_And_Sort_Tiles and the recursive procedure that it contains, Place_It Notice how the code places the records in a linearly linked structure in order according to their areas.
• Now, complete the code in the procedure Sort_In, which is in the procedure Perim_Order. This code should take the rectangle record passed to it as the first parameter, and copy the contents into a record in the linear structure that is being created in such a way that the records are ordered in the linear structure from the record with the smallest perimeter to the record with the largest perimeter.
• The code in Sort_In should somewhat parallel the code in Place_It. GOOD LUCK!!

Due Date: You must complete this laboratory assignment by 12 midnight Sunday February 11, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: Send me two email messages:

• In the first message, cut and paste the procedure Perim_Order into an email message and send it to me.
• In Perim_Order there is a comment that tells you to remove a particular line of code. Send me a second email message with your explanation of what happenned, and your explanation as to why it happened.

Lab 3: Playing with OOP

Goal: Gain some experience with type extension and dynamic dispatch using tagged types in Ada.

Assignment:

• There are three files in ftp.cs.uofs.edu/pub/courses/cmps240. You may pull these files into your account by:
  • CLICK HERE to obtain figures.ads
  • CLICK HERE to obtain figures.adb
  • CLICK HERE to obtain uses_figures.adb Place this file in usesfigu.adb if you are on a DOS machine, and in uses_figures.adb on a unix or linux machine.
• Compile figures.adb
• Now, compile uses_figures.adb. Note the compiler error messages. These were created because the program uses_figures.adb was constructed using an earlier version of GNAT that did not conform to the final version of the international Ada standard. Your first task is to correct this by
• Add the specifications for Square and Square's Get procedure to figures.ads
• Place the body of Square's Get procedure in figure.adb Compile figures.adb and make any necessary corrections to obtain a clean compile.
• Remove the offending code from uses_figures.adb, compile, link, and run it. Make sure you run enough data through the program to verify that it is functioning correctly.
• Add an Is_Square function to the Figures specifications file as a dispatchable subprogram. Do this only for Rectangle type. The function return's true if and only if the height = width, regardless of whether the object type is a square of a rectangle.
• Now, since you only wrote it for rectangle type, the function can only be dispatched for rectangles and squares. You can write an if structure in the loop that tests for a rectangle or a square, and calls Is_Square inside the if. For tagged types there is a 'Tag attribute. The 'Tag is the internal code used by the system to distinguish between tagged types. The 'Tag attribute works for tagged objects as well as for the types. For example, the expression
  
  

            Point.all'tag = rectangle'tag

  tests to see if the record point.all is a rectangle. You will have to construct a compound boolean expression to test to see if the record being accessed by Point is a rectangle or a square, then execute a statement sequence within the if, like
  
  

                       if Is_Square (Point.all) then
                           text_io.Put ("Is a square");
                         else
                           text_io.Put ("Is not a square");
                       end if;
                       text_io.new_line;
  

  
  to print whether a square or rectangle is a rectangle.

Due Date: You must complete this laboratory assignment by 12 midnight Sunday February 18, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: Send me two email messages:

• Email me a copy of your uses_figures.adb source file.
• Email me your understanding of how dynamic dispatch does what it does at run time and what that means instead of being done at compile time.

Lab 4: Writing An Adjust Procedure

Goal: Write an Adjust procedure for a controlled type

Resources: You will need four file, a data file, the specifications and body for a polynomial package, and a procedure that uses the polynomial package:

• Click here to obtain poly.dat
• Click here to obtain polynomial.ads
• Click here to obtain polynomial.adb
• Click here to obtain use_polynomial.adb

Description: First of all compile the polynomial package, then compile, link, and run use_polynomial. When you run use polynomial note how the first pair of outputs for P and Q are different, after

           Q := P, 

           5.00000E00 x^2 

Due Date: You must complete this laboratory assignment by 12 midnight Sunday February 25, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: Cut and paste your Adjust Procedure into an email message and send it to me.

Lab 5: Writing A Finalize Procedure

Due Date: You must complete this laboratory assignment by 12 midnight Sunday March 3, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: Cut and Paste your Finalize procedure into an email message and send it to me.

Lab 6: Working with an Iterator

To perform this lab you will be using the polymorphic stack package, which is already available on the Suns, or you can ftp the complete set of polymorphic data structures to your machine from ftp.cs.uofs.edu from the pub/Ada subdirectory. To perform this lab you need three resources,

• poly_paren.adb.
• poly_paren_pak.ads
• poly_paren_pak.adb

The poly_Paren procedure reads a string and checks for correct matching of parentheses types, { to }, [ to ], and ( to ). Other symbols may appear in the string. This procedure reads the string and checks for the match. However, every time it sees an 'x' it calls the iterator to print the contents of the stack. To illustrate, here is a sample dialog with the program:

Enter any string - checks for proper parenthesis matching
  ([({()})((aa))]) would be accepted, but (())) would not
Enter Paren string: [[[x(((x[x]))x)]x]x]x
                        Stack top-to-bottom = [[[
                            Stack top-to-bottom = ((([[[
                              Stack top-to-bottom = [((([[[
                                  Stack top-to-bottom = ([[[
                                     Stack top-to-bottom = [[
                                       Stack top-to-bottom = [
                                         Stack top-to-bottom = 
                                         ACCEPTED

I'd suggest you do the following:

• Compile poly_paren_pak first
• Compile and link poly_paren.
• Run poly_paren a few times to get a feel for how it works
• Edit Poly_Paren_PAK.adb and construct the code in Print_Obj to print the object passed to it. NOTE: only print the object, do not issue any new_line or other command.
• Recompile poly_paren_pak, then compile, link, and run poly_paren.adb to verify that your code works correctly.

Due Date: You must complete this laboratory assignment by 12 midnight Sunday March 10, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: Email to me poly_paren_pak.adb

Lab 7: Binary Search Tree Lab

• random.dat
• avl_support.ads
• avl_support.adb
• bin_search_tree.adb

Description:In this lab you will complete three subprograms in bin_search_tree.adb as follows:

• Review the contents of avl_support.ads. Note the construction of AVL_Node type. It contains both the data that will be in each node and the balance information that will be placed in the node in the next laboratory assignment.
• Compile avl_support.adb. This package provides the AVL restructuring support that will be used in the next lab assignment. It also provides the interface between the bin_search_tree.adb and the polymorphic tree package.
• Inset the code in the tree procedures. The locations where the code must be placed is indicated with the --<< mark. The three subprograms that must be completed are:
  • In Recursive_Place include the code to correctly graft the node to the tree and make the correct recursive calls, with the correct parameters, to recursively traverse the tree.
  • In Longest_Path insert the correct decision that determines if the current path length is longer than the length of the currently recorded longest path.
  • In Shortest_Path insert the decision that determines when a node is a terminal node, it has no children.
• Once the program compiles successfully, pay attention to the role Side_Ways (Tree)aches plays in helping you see how the tree is being constructed. Each time through the loop, Side_Ways prints the tree for you. Press return to see the next node attached. The program attaches 30 node to the tree. After you are satisfied that you code is working successfully, comment out the call to Side_Ways and Skip_Line. Also, replace the for loop with the indicated while loop. Now run the program. If the numbers print in order, you may assume that the program is correct.

Due Date: You must complete this laboratory assignment by 12 midnight Sunday April 21, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: bin_search_tree.adb

Lab 8: AVL Restructuring Lab

Assignment:Complete the AVL restructuring in avl_tree.adb.

Resources: Use the avl_support package and random.dat file from the previous Lab. assignment. Bring avl_tree.adb into your account. It contains the same "--<<" tags to the locations you must modify, as the previous Lab

Description: Do the following:

• Place your Longest_Path and Shortest_Path functions from gthe previous lab into this assignment.
• Complete the AVL code. You are respponsible for
  • Doing the correct rebalancing as the procedure comes out of each recursive call.
  • Setting the value of arc
  • Making the correct calls to the four AVL procedures.
• Compile and run the program with the sideways printer in it to visually check and see whether you have everything in the right place.
• After you feel confident that your code is correct, comment out the sideways printing and the skip_line to run your program with the full set of data.

What to submit Email the avl_tree procedure. Also include in your email message the values returned by the longest and shortest path procedures.

Due Date: You must complete this laboratory assignment by 12 midnight Sunday April 27, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: Cut and Paste your Finalize procedure into an email message and send it to me.

You will be participating in a doctoral research experiment at George Washington University. Details of you participation will be placed here shortly.

Due Date: Probably midnight Sunday May 5, 1996

Programming Assignments

Goal:

• Gain experience working with access types
• Work on the details at the heart of one of the fastest sorting methods.

Assignment:Complete the code in link_merge. The program contains a procedure to create two linked structures, each structure contains twenty random numbers. The software system also contains a procedure that either prints the symbol "<>" when the list is null, or prints the numbers in the records in the order in which they appear in the linear structure, from first to last. Your task it to complete the software system so that the output produced by the five calls to the printing procedure demonstrate that the original sets in the two lists are ordered, then after the call to the merge procedure that you complete, the three remaining calls demonstrate that the two original lists had been emptied and that the third list contains the complete set of values properly merged.

To obtain the resources you need to complete this task,

• Click here to obtain the random data set (random.dat) that is used by the program to initialize the two lists.
• Click here to obtain the partial program, store it as linkmerg.adb (DOS) or link_merge.adb (unix).

Due Date: You must complete this laboratory assignment by midnight Wednesday February 21, 1996. NO EXCEPTIONS, NO EXCUSES. If you wait until the last minute and the system is down, the grade is "0".

What to Submit: Note how the initial source code contains in-line comments. Place similar and meaningful comments along with your code. Send me two email messages:

• Email me your completed linkmerg.adb file
• Email me the .lst file produce by the compiler when you compiled the linkmerg.adb file

Tests

• Comments on Test 1.

Grades

I compute grades by using a weighted average. Specifically, each item is given a maximum possible grade, M_i , and a weighht, W_i. Given your grade for an assignment or test, G_i, the effective grade for that assignment is W_i*G_i/M_i. Your final grade is computed as

This computation produces a value in a standardized range. I reserve the right to determine the correspondence between these values and letter grades.

The Border Crossing Problem is described in Section 8.6 of the notes. Your task is to carry out the solution described in that section. To get you started, a piece of code to read the border information has been supplied, as well as a data set thaht contains the border information for a map of the forty eight contiguous United States. These files are:

• Map.adb. This file contains procedures to create a table representation of a map and prints the map for you. It contains some subprograms to help navigate the table represntation.
• usa.dat. This is the data file for the map of the 48 continental United States. It is read by the program above.

Compile. link and run map.adb before you get started. You may want to take a look at how it works. Impliment the solution to the border crossing problem as described in Section 8.6. Your program should accept two two-letter string abbreviations for the names of states, solve the problem, and print a solution path.

DUE DATE: By noon on Friday May 17, 1996, email me a copy of your program.

Exercise 6 in Section 11.4 of the notes describe the results when five sets of data are run through three sort procedures. Write a paper describing your analysis of the five data sets and the three sort procedures that were used. One data set is the numbers in order, one is the numbers in reverse order, one are all the same, one random, and one where each number is almost where it belongs. Your task is to try and decide which set is which, and what are the three sort techniques that were used.

Write your analysis of the data sets. You may assume that one sort is an O(n^2) sort, and one is an O(n log n) sort. A good start would be to draw a line graph of the data as a starting point.

Your analysis must be word processed, double spaced. Please place your name in the upper left corner of each page and "Cmps 240" in the upper right corner. Include in your submission your line graphs.