• API
• FAQ
• Tools
• Archive
SHARE
TWEET  g-stoyanov   May 30th, 2013 112 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
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.
9. {
10.     using System;
11.     using System.Diagnostics;
12.
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.
Top