CSE 212: Programming with Data Structures

Individual Activity: Dynamic Arrays and Performance Analysis

Special Instructions for this Week's Activity

Each week will contain a team activity. These activities are designed to take about one hour and should be completed by multiple people working together.

You need gather for a synchronous video call, where everyone can see the code that is being written and help contribute.

For this lesson, because the teams may not be fully defined you will work on the activity individually, but you are encouraged to collaborate with others by asking and answering questions in Microsoft Teams.

Even though you will not meet with a team this week, to help you see how the process will work, this activity is set up identically to the future team activities, including the I-Learn quiz that you will submit upon completion. For this lesson, you should simply answer "True" to any questions that ask if you met with your team or were on time to the meeting, etc. In future lessons, you should answer those questions honestly, according to what you actually did.

Instructions

Work through each problem, then compare your solution to the answer which is provided below.

All of the code files for this assignment will be found in the course GitHub repository in the week01/teach folder.

Using Dynamic Arrays

To ensure you have enough time for this activity, spend no more than 15 minutes implementing this method before looking at the solution to discuss.

  1. In the week01/teach folder, open up the following code: Divisors.cs

  2. Implement the FindDivisors() method in the Divisors class.
    • The method should create and return a list of divisors of the number provided into the method. The list should include the value 1 but should not include the actual number. If the number was 12, then the resulting list would be {1, 2, 3, 4, 6}. If the number was 17, then the resulting list would be just {1} because 17 is a prime number. When implementing the method, use a for loop, an if statement, and call Add.
  3. Compare your answer with the code found in DivisorsSolution.cs. If you want to run this code, you can do so by uncommenting the appropriate line in Program.cs.

Solving a Complicated Problem

Spend no more than 10 minutes on this problem before you look at the sample solution and then move on to the next one.

  1. Open up the following code: ArraySelector.cs

  2. Implement the int version of the ListSelector() method in the ArraySelector class.

  3. Come up with a plan (up to 10 minutes) on how to implement the integer version the ListSelector() method. The function takes two arrays and a selector array. The two arrays are combined together into a new array according to the selector array. The selector array only contains 1's and 2's. A value of 1 means that you should select the next number from the first array. A value of 2 means that you should select the next number from the second array. For example, if array 1 is {1, 2, 3, 4} and if array 2 is {10, 20, 30, 40} and if the selector array is {1, 1, 2, 2, 1, 1, 2, 2}, then the resulting array would be {1, 2, 10, 20, 3, 4, 30, 40}.

  4. Compare your plan with the following sample solution:

    Sample Solution (Click to Expand)

    To solve the Array Selector problem, we will need to do the following as we loop through the selector array:

    • If the current value in the selector array is a 1, then we want to get the next item from the first array
    • If the current value in the selector array is a 2, then we want to get the next item from the second array
    • We need to append the value we just selected to the new array

    We will need a way to determine what the next item is in either array 1 or array 2. We will need variables to keep track of where we are (i.e. the index) in both arrays:

    • array1Index - We will use this to keep track of the index of the next item in the first array
    • array2Index - We will use this to keep track of the index of the next item in the second array

    We will initialize both of these variables to 0. When we select an item from one of the arrays (per the selector array) we will add one to either array1Index or array2Index depending on which one was selected.

    Shows array1, array2, and a selectorArray as described in the example from W01-Teach. Arrows are drawn from the selectorArray to either array1 or array2 depending on the value in the selectorArray (1 goes to array1 and 2 goes to array2). A table is shown for each loop through the selector array (0 to 7) and the values of array1Index (0, 1, 1, 1, 2, 3, 3, 3) and array2Index (0, 0, 0, 1, 1, 1, 2, 3) as we go through the array. The building of the result_array based on the array1Index and array2Index is shown as: [1], [1,2], [1,2,10], [1,2,10,20], [1,2,10,20,3], [1,2,10,20,3,4], [1,2,10,20,3,4,30], [1,2,10,20,3,4,30,40].
    Solving the Problem Manually on Paper
  5. You can view the sample solution implemented in code in ArraySelectorSolution.cs. If you want to run this code, you can do so by uncommenting the appropriate line in Program.cs.

Predict, Measure, and Compare Code

  1. In the week01/teach folder, open the file Algorithms.cs (NOTE: Do not run the code until you're asked to below)

  2. This file contains three different methods called Algorithm1, Algorithm2, and Algorithm3. Predict the performance of each method using big O notation.

  3. Uncomment the call to Algorithms.Run() in Program.cs. Run the code and observe the outputs. Here is what the columns in the table represent:
    • n - The size of the data given to the methods in this test
    • alg1-count - The number of loop iterations (i.e. work) done by Algorithm1
    • alg2-count - The number of loop iterations (i.e. work) done by Algorithm2
    • alg3-count - The number of loop iterations (i.e. work) done by Algorithm3
    • alg1-time - The time in milliseconds it took to complete Algorithm1
    • alg2-time - The time in milliseconds it took to complete Algorithm2
    • alg3-time - The time in milliseconds it took to complete algorithm3

    While the alg#-count value should be the same in every execution, the time will vary each time it is executed on the same or different computers. To compute the timing numbers, the code runs the test 10 times and computes the average. This is done to account for any operating system conditions that could affect timing in some cases.

Answer the following questions. When you have answered each question, compare your response to the sample solution provided.

  1. Do the actual results agree with the big O predictions made earlier? If not, what do you think the big O should be?
    2. Sample Solution (Click to Expand)

    The Algorithm1 function has a single for loop. This implies O(n). If we look at the actual results, we see that count is the same value as the size of the list. The Algorithm2 function has a loop within a loop. This implies O(n^2). If we look at the actual results, we see that the count is the square of the size of the data. The Algorithm3 functions finds the center of the list and then looks at the 2nd half the list. This process is repeated in which each iteration of the while loop the list is cut in half again. This implies O(log n). If we look at the actual results, we see that the count is approximately the base 2 logarithm of the size.

  2. Which method (Algorithm1, Algorithm2, Algorithm3) has the best performance and which one the worst performance?
    3. Sample Solution (Click to Expand)

    Based on the timing data, Algorithm3 is much faster and Algorithm2 is much slower. Note that Algorithm3 is barely increasing (if at all) and Algorithm2 is growing by larger amounts as the size of the data increases. This result agrees with the big O notation from above. O(log n) is better than O(n), and O(n) is better than O(n2) when n is "large".

  3. Looking at the results, why do we say that big O only applies when n in "large"?
    4. Sample Solution (Click to Expand)

    When n is small, the time for all three algorithms is very close to each other. Realizing that these are in milliseconds, the amount of time to see the result for Algorithm2 when n is large will start to approach 1 second unlike the other 2 functions. However, when n is small, no difference is seen by the user.