CIS-5050 Homework #1: Maximum Subarray

Due: Friday, January 31, 2020

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 2019 Ada compiler from AdaCore. Download my samples project and unzip it in some suitable location. You will be building on this project throughout the course by adding new files to it in both this and future homework assignments. The project's configuration is controlled by the cis5050.gpr project file. You can either open this project in the GPS integrated development environment, or use it as a command line argument with the gprbuild command line tool. See the README.md file contained in the archive for more information. Be sure you can compile the test program (main.adb) and execute it.

  2. The zip archive contains examples of Insertion_Sort and Merge_Sort in Ada, as translated from the pseudo-code in the text. It also contains a GNAT project file and an appropriate build folder. Unzip the archive in some suitable place to use as a framework for future samples and homework assignments.

  3. 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. Your assignment is to implement the pseudo-code for the two functions Find_Max_Crossing_Subarray and Find_Maximum_Subarray.

    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_Maximum_Subarray
              (A : Array_Type; Low, High : Positive) return Subarray_Summary
            with Pre => (Low <= High);
          

    Note that for this to work the entire package must be generic and not just the procedure inside that package (This is because a generic type is being used in the definition of Subarray_Summary. To declare a generic package, put the generic header immediately before the package Homework01 is... line in the specification file.

    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).

    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!

    I provide starter files for this assignment. Unzip the starter files in the same folder as where cis5050.gpr is located. The starter files contain an updated main.adb test program, and a test for the maximum subarray problem that includes the text book's example. The specification file is fully complete. You only need to flesh out the "FINISH ME" sections in the homework01.adb body file.

Submit only your modified homework01.adb file to Canvas.


Last Revised: 2020-01-10
© Copyright 2020 by Peter C. Chapin <pchapin@vtc.edu>