SHARE
TWEET

DataStructuresAlgorithmsAndComplexityTask3

g-stoyanov May 30th, 2013 112 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Task 3
  3.  * * What is the expected running time of the
  4.  * following C# code? Explain why.
  5.  * Assume the input matrix has size of n * m.
  6.  */
  7.  
  8. namespace Task3
  9. {
  10.     using System;
  11.     using System.Diagnostics;
  12.  
  13.     public class Task3
  14.     {
  15.         /// <summary>
  16.         /// Original Code from homework.
  17.         /// </summary>
  18.         public static long CalcSumOriginal(int[,] matrix, int row)
  19.         {
  20.             long sum = 0;
  21.  
  22.             // There is a bug in matrix.GetLength(0) - must be matrix.GetLength(1) because this is a number of cols
  23.             for (int col = 0; col < matrix.GetLength(0); col++)
  24.                 sum += matrix[row, col];
  25.  
  26.             // There is a bug in matrix.GetLength(1) - must be matrix.GetLength(0) because this is a number of rows
  27.             if (row + 1 < matrix.GetLength(1))
  28.                 sum += CalcSumOriginal(matrix, row + 1);
  29.             return sum;
  30.         }
  31.  
  32.         /// <summary>
  33.         /// Fixed Code.
  34.         /// </summary>
  35.         public static long CalcSumFixed(int[,] matrix, int row)
  36.         {
  37.             long sum = 0;
  38.  
  39.             // Bug Fixed
  40.             for (int col = 0; col < matrix.GetLength(1); col++)
  41.             {
  42.                 sum = sum + matrix[row, col];
  43.             }
  44.  
  45.             // Bug Fixed
  46.             if (row + 1 < matrix.GetLength(0))
  47.             {
  48.                 sum = sum + CalcSumFixed(matrix, row + 1);
  49.             }
  50.  
  51.             return sum;
  52.         }
  53.  
  54.         /*
  55.          * Runing time of this code is: O(n * m)
  56.          * Because for every column we recursive call
  57.          * function for each row in the column - n * m!
  58.          * Minor improving is available:
  59.          */
  60.  
  61.         /// <summary>
  62.         /// Minor improved code.
  63.         /// </summary>
  64.         public static long CalcSumImproved(int[,] matrix)
  65.         {
  66.             long sum = 0;
  67.             for (int row = 0; row < matrix.GetLength(0); row++)
  68.             {
  69.                 for (int col = 0; col < matrix.GetLength(1); col++)
  70.                 {
  71.                     sum = sum + matrix[row, col];
  72.                 }
  73.             }
  74.  
  75.             return sum;
  76.         }
  77.  
  78.         /// <summary>
  79.         /// Test fixed and improved code.
  80.         /// </summary>
  81.         private static void Main()
  82.         {
  83.             // Test fixed code
  84.             int[,] matrix = new int[,]
  85.             {
  86.                 { 1, 2, 4, -5, 3 },
  87.                 { 122, 33, -56, 22, 3 },
  88.                 { 1, 2, 4, -5, 3 },
  89.                 { 122, 33, -56, 22, 3 },
  90.             };
  91.  
  92.             Console.WriteLine(CalcSumFixed(matrix, 0));
  93.             Console.WriteLine(CalcSumImproved(matrix));
  94.  
  95.             // Compare fixed and minor improved code
  96.             int repeats = 10000000;
  97.             Stopwatch timer = new Stopwatch();
  98.             timer.Start();
  99.             for (int i = 0; i < repeats; i++)
  100.             {
  101.                 CalcSumFixed(matrix, 0);
  102.             }
  103.  
  104.             timer.Stop();
  105.             Console.WriteLine("Time of fixed original code after {0} repeats: {1}", repeats, timer.Elapsed);
  106.  
  107.             timer.Reset();
  108.  
  109.             timer.Start();
  110.             for (int i = 0; i < repeats; i++)
  111.             {
  112.                 CalcSumImproved(matrix);
  113.             }
  114.  
  115.             timer.Stop();
  116.             Console.WriteLine("Time of minor improved code after {0} repeats: {1}", repeats, timer.Elapsed);
  117.         }
  118.     }
  119. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top