CIS-5050 Homework #1: Introduction

Due: Friday, September 7, 2018

Read Chapter 2 in the text. Take note of the pseudo-code for Insertion_Sort and Merge_Sort.

  1. Download and install the GNAT Community 2018 Ada compiler from AdaCore. Download my samples project and unzip it in some suitable location. Start the GPS integrated development environment on the samples.gpr project file. Make sure you can compile the main program and that it executes correctly. You will be able to use this project for future samples that I'll be providing throughout the course. In the future I will just provide the source files that you can drop into your src folder. You could also use this project for your own coding.

  2. In Chapter 4 of the text, review section 4.1 on the maximum subarray problem. That section describes a recursive algorithm to solve the problem and also shows a sample problem instance to help explain the problem. Implement the pseudo-code for the two functions Find_Max_Crossing_Subarray and Find_Maximum_Subarray. Use my Merge_Sort example for ideas. For example, one of the procedures can be local to the other.

    The pseudo-code makes use of tuple types. Ada does not have tuple types, but you can simulate them using Ada records. For example:

            type Subarray_Summary is
               record
                  Low_Index  : Positive;
                  High_Index : Positive;
                  Sum        : Element_Type;
               end record;
          

    You can then declare the functions, for example, like this:

            function Find_Max_Crossing_Subarray
              (A : in Array_Type; Low, Mid, High : in Positive) return Subarray_Summary;
          

    The pseudo-code also uses downto to describe a loop that iterates backwards over its range. In Ada you use in reverse to do this:

            for I in reverse 1 .. 10 loop
          

    Notice that the range is still specified in forward order as 1 .. 10. In Ada ranges like 10 .. 1 are actually considered empty ranges containing no values at all!

    Finally, this algorithm assumes the elements of the array are integers that can be added together (with both positive and negative values). Using the generic parameter declaration of Element_Type is private is too general; such a declaration does not require Element_Type to be anything like an integer. To deal with this, declare the generic parameter this way:

            type Element_Type is range <>;
          

    This will require the actual parameter to be some kind of signed integer. This also means you can use integer operations on variables of type Element_Type, like integer addition, etc., inside the generic body (without tediously declaring the needed operations in the generic header).

  3. Put your code inside a new package called Homework01 (in two new files). Modify the main file so that it demonstrates your implementation. For example, show it working on the example given in the text. I call such programs "demonstration" programs because they show off how to use the code. A true test program would attempt to exercise the code with good coverage and would be much longer and more involved to write. We will get to that!

Create a zip archive of the three files main.adb, homework01.ads, and homework01.adb. Submit your achive to Moodle.


Last Revised: 2018-08-13
© Copyright 2018 by Peter C. Chapin <pchapin@vtc.edu>