[Unified-mailman] BigO[1..3].adb

[Kristina Lundqvist]

Students,

Attached are the three Ada files that was used in todays recitation.

..IKL
-------------- next part --------------
------------------------------------------------------------------------
-- BigO.adb Recitation 3
-- Demonstrates an O(N^2) algorithm
-- when size of n (Array size) doubles, the execution time grows 2^2 times
-- Specified: IKL
-- Created: 4/22/04
-- Last Modified:
------------------------------------------------------------------------

with Ada.Text_Io;
use Ada.Text_Io;

with Ada.Calendar;
use Ada.Calendar;

procedure Bigo is 

   type Int_Array is array (Integer range <>) of Integer; 

   procedure Measure (
         A : Int_Array ) is 
      Start : Time    := Clock;  
      Sum   : Integer := 0;  

   begin -- Measure
      for I in A'range loop
         for J in A'range loop
            Sum := Sum + A(J);
         end loop;
      end loop;

      Put_Line ("Size of array is: " & Integer'Image (A'Length));
      Put_Line ("and time in seconds is: " & Duration'Image (Clock-Start));
      New_Line (2);

   end Measure;


begin --Main
   for I in 1..20 loop
      -- for I in 1..10 loop

      declare
         A : Int_Array (1 .. 2**I) := (others => 0);  
         --       A : Int_Array (1 .. 10**I) := (others => 0);  
      begin

         Measure (A);
      end;
   end loop;
end Bigo;

-------------- next part --------------
------------------------------------------------------------------------
-- BigO2.adb Recitation 3
-- Demonstrates an O(n^2) algorithm
-- when size of n (Array size) doubles, the execution time grows 
-- quadratic
-- Specified: IKL
-- Created: 4/22/04
-- Last Modified:
------------------------------------------------------------------------


with Ada.Text_Io;
use Ada.Text_Io;

with Ada.Calendar;
use Ada.Calendar;

procedure Bigo2 is 

   type Int_Array is array (Integer range <>) of Integer; 

   procedure Measure (
         A : Int_Array ) is 
      Start : Time    := Clock;  
      Sum   : Integer := 0;  

   begin -- Measure
      for I in A'range loop
         --       for J in A'range loop
         for J in 1 .. I loop

            Sum := Sum + A(J);
         end loop;
      end loop;
      
      Put_Line ("Size of array is: " & Integer'Image (A'Length));
      Put_Line ("and time in seconds is: " & Duration'Image (Clock-Start));
      New_Line (2);
      
   end Measure;


begin -- Main
   for I in 1..20 loop
      -- for I in 1..10 loop

      declare
         A : Int_Array (1 .. 2**I) := (others => 0);  
         --       A : Int_Array (1 .. 10**I) := (others => 0);  
      begin

         Measure (A);
      end;
   end loop;
end Bigo2;

-------------- next part --------------
------------------------------------------------------------------------
-- BigO3.adb Recitation 3
-- Demonstrates an O(n) algorithm
-- when size of n (Array size) doubles, the execution time also doubles
-- Specified: IKL
-- Created: 4/22/04
-- Last Modified:
------------------------------------------------------------------------


with Ada.Text_Io;
use Ada.Text_Io;

with Ada.Calendar;
use Ada.Calendar;

procedure Bigo3 is 

   type Int_Array is array (Integer range <>) of Integer; 

   procedure Measure (
         A : Int_Array ) is 
      Start : Time    := Clock;  
      Sum   : Integer := 0;  

   begin -- Measure
      for I in A'range loop
         --       for J in A'range loop
         --       for J in 1 .. I loop
         for J in 1 .. 4 loop
            Sum := Sum + A(I);
         end loop;
      end loop;
      
      Put_Line ("Size of array is: " & Integer'Image (A'Length));
      Put_Line ("and time in seconds is: " & Duration'Image (Clock-Start));
      New_Line (2);
      
   end Measure;

begin -- Main
   for I in 1..20 loop
      -- for I in 1..10 loop

      declare
         A : Int_Array (1 .. 2**I) := (others => 0);  
         --       A : Int_Array (1 .. 10**I) := (others => 0);  
      begin

         Measure (A);
      end;
   end loop;
end Bigo3;