2020 MC Reflection

• • 17 min read

  • Corrections
  • Future Plan

    • Analysis

    MC

    Needs Significant Improvement

    • Mathematical Expressions (3.3, 0%): errors in order of operations or arithmetic calculations.
      • Plan: Review order of operations, practice problems, and ensure understanding of expression evaluation.
    • Strings (3.4, 0%): string indexing, slicing, or string methods.
      • Plan: Go over string manipulation techniques and common string functions.
    • Binary Search (3.11, 0%): trouble with search logic or adjusting indices properly.
      • Plan: Practice dry-running binary search on different datasets to understand its mechanics better.
    • Developing Procedures (3.13, 0%): confusion with function implementation, parameters, or return values.
      • Plan: Work on writing and debugging functions, understanding scope and return values.
    • Algorithmic Efficiency (3.17, 0%): analyzing algorithm performance.
      • Plan: Study common complexities and practice complexity analysis on different algorithms.

    Needs More Attention

    • Extracting Information from Data (2.3, 86%): interpreting data or applying transformations.
      • Plan: Practice working with data extraction and filtering techniques.
    • Developing Algorithms (3.9, 75%): Some logic errors in algorithm design or implementation.
      • Plan: Review algorithm patterns, pseudocode, and dry-run examples.
    • Calling Procedures (3.12, 80%): confusion with function calls, parameter passing, or return values.
      • Plan: Revise function definitions, argument types, and function execution flow.
    • The Internet (4.1, 75%): Some gaps in understanding networking concepts like HTTP, DNS, and IP addressing.
      • Plan: Review key concepts related to how the internet works, including data transmission and network protocols.

    Corrections

    Q14: Display Digits in Reverse Order

    Problem Statement

    The following algorithm is intended to take a positive integer as input and display its individual digits in order from right to left. For example, if the input is 512, the algorithm should produce the output: 2 1 5

    Step 3 of the algorithm is missing.

    Given Algorithm

    1. Step 1: Input a positive integer from the user and store it in the variable number.
    2. Step 2: Divide number by 10 and record:
      • The integer quotient (quotient with the decimal part dropped).
      • The remainder (last digit of number).
    3. Step 3: (Missing Step)
    4. Step 4: Repeat steps 2 and 3 until number becomes 0.

    Choices

    Which of the following can be used as Step 3 so that the algorithm works as intended?

    A. Display the remainder of number divided by 10 and store the remainder in number.

    B. Display the remainder of number divided by 10 and store the integer quotient in number.

    C. Display the integer quotient of number divided by 10 and store the remainder in number.

    D. Display the integer quotient of number divided by 10 and store the integer quotient in number.

    Correct Answer: B

    Explanation:

    • Step 2 gives the remainder (last digit) and the integer quotient.
    • Step 3 should display the remainder (the last digit).
    • Step 3 should also store the integer quotient back into number so that in the next iteration, the process continues with the remaining digits.

    Thus, the correct step is:

    Step 3: Display the remainder of number divided by 10 and store the integer quotient in number.

    Why A is Incorrect:

    • A stores the remainder in number, which leads to an infinite loop unless number is a multiple of 10.
    Example:
    • Input: 512
      1. Step 1: 512 % 10 = 2, store number = 2
      2. Step 2: 2 % 10 = 2, store number = 2 (loop continues forever)

    Thus, the algorithm gets stuck in an infinite loop because number never reduces to 0.

    Remind

    Carefully check the input number, remainder/integer!

    Category: 3.3

    Q20: Average amount of data per user

    Problem Statement

    A file storage application allows users to save their files on cloud servers. A group of researchers gathered user data for the first eight years of the application’s existence. Some of the data are summarized in the following graphs. The line graph on the left shows the number of registered users each year. The line graph on the right shows the total amount of data stored by all users each year. The circle graph shows the distribution of file sizes currently stored by all users. File Storage Data Graph

    Choices

    Which of the following best describes the average amount of data stored per user for the first eight years of the application’s existence?

    A. Across all eight years, the average amount of data stored per user was about 10 GB.

    B. Across all eight years, the average amount of data stored per user was about 100 GB.

    C. The average amount of data stored per user appears to increase by about 10 GB each year.

    D. The average amount of data stored per user appears to increase by about 100 GB each year.

    Correct Answer: A

    Explanation:

    • To determine the average amount of data stored per user, we compare the Total Amount of Data Stored graph with the Number of Registered Users graph.
    • From the graphs, each year’s total data storage (in million GB) is approximately 10 times the number of users (in million users).
    • This means the average storage per user is:
      Average storage per user = Total Data Stored / Number of Users ≈ 10 GB per user

    Why B is Incorrect:

    • Each value on the Total Amount of Data Stored graph is about 10 times the corresponding value on the Registered Users graph.
    • This suggests that the average amount of data stored per user is approximately 10 GB, not 100 GB.
    Example Calculation:
    • Year 8:
      • Total Data Stored: 6,986 million GB
      • Total Users: 701 million
      • Average Data per User: 6,986 ÷ 701 ≈ 10 GB

    Category: 2.3

    Q25: How the Internet Facilitates Large-Scale Communication

    Problem Statement:

    Which of the following statements correctly explain how the Internet is able to facilitate communication at a large scale?

    Statements:

    1. A central monitoring computer is used to track and maintain the connections of the Internet.
    2. Data is routed between points in multiple ways so that if a connection fails, the data can be rerouted around the inoperative connections.
    3. Protocols for packets and routing are used so that computers from different manufacturers can communicate in a standard way.

    Answer Choices:

    A. I and II only
    B. I and III only
    C. II and III only
    D. I, II, and III

    Correct Answer: C (II and III only)

    Explanation:

    ✅ Statement II (Correct):
    • The Internet is designed with redundant routing paths to ensure reliable communication.
    • If a network connection fails, packet-switching technology allows data to be rerouted dynamically through alternative paths.
    • This ensures fault tolerance, meaning the Internet remains operational even when some connections go down.
    ✅ Statement III (Correct):
    • The Internet relies on standardized protocols, such as TCP/IP, HTTP, and DNS, to allow communication between devices from different manufacturers.
    • These protocols define how data is formatted, transmitted, and received, ensuring that all devices can work together seamlessly.
    ❌ Statement I (Incorrect):
    • The Internet is decentralized and does not have a single central monitoring computer controlling all connections.
    • Instead, it operates through a distributed network managed by different ISPs (Internet Service Providers) and autonomous systems.
    • No single authority tracks or maintains all Internet connections.

    Category: 4.1

    Q35: Generalization of MaxTwo and MaxThree Procedures

    Problem Statement:

    A programmer notices two procedures in a library:

    • Procedure MaxTwo(x, y) → Returns the greater of its two integer parameters.
    • Procedure MaxThree(x, y, z) → Returns the greatest of its three integer parameters.

    Which of the following procedures generalizes both MaxTwo and MaxThree?

    Answer Choices:

    A. Min(x, y), which returns the lesser of its two integer parameters.
    B. Max(numList), which returns the maximum value in the list of integers numList.
    C. MaxFour(w, x, y, z), which returns the greatest of its four integer parameters.
    D. OverMax(numList, max), which returns the number of integers in numList that exceed the integer value max.

    Correct Answer: B (Max(numList))

    Explanation:

    • MaxTwo and MaxThree both return the maximum value from a fixed number of parameters (2 and 3, respectively).
    • A true generalization would allow finding the maximum value for any number of inputs.
    • Max(numList) achieves this by accepting a list of integers, making it applicable to any number of values.

    ❌ Why the Other Answers Are Incorrect?

    Choice Explanation
    A (Min(x, y)) This procedure finds the minimum, not the maximum, so it does not generalize MaxTwo and MaxThree.
    C (MaxFour(w, x, y, z)) While this finds the maximum of four numbers, it is still limited to a fixed number of inputs (like MaxTwo and MaxThree), rather than being a true generalization.
    D (OverMax(numList, max)) This counts how many numbers exceed a certain value, which is unrelated to finding the maximum of a set of numbers.

    Category: 3.1

    Q39: Program Logic Error for Summing First 10 Elements

    Problem Statement:

    Assume the list of numbers nums has more than 10 elements. The program is intended to compute and display the sum of the first 10 elements of nums.

    The given program is as follows:

        Line 1: i = 1
    Line 2: sum = 0
    Line 3: REPEAT UNTIL (i > 10)
    Line 4: {
    Line 5: i = i + 1
    Line 6: sum = sum + nums[i]
    Line 7: }
    Line 8: DISPLAY (sum)

    Choices:

    Which change, if any, is needed for the program to work as intended?

    • A. Lines 1 and 2 should be interchanged.
    • B. Line 3 should be changed to REPEAT UNTIL (i ≥ 10).
    • C. Lines 5 and 6 should be interchanged.
    • D. No change is needed; the program works correctly.

    Correct Answer: C (Lines 5 and 6 should be interchanged)

    Explanation:

    • The logic of the program intends to sum the first 10 elements of nums. However, as currently written:
      • The program starts with i = 1 (which is correct because lists typically start with index 0, and the first element corresponds to nums[0]).
      • However, in Line 5, i is incremented before it is used to access nums[i] in Line 6. This means that the program is skipping the first element (nums[0]), starting from nums[1] instead.
    • To fix this, Line 5 and Line 6 should be swapped so that nums[i] is accessed before i is incremented. This ensures the program starts with nums[0] and processes the first 10 elements.

    ❌ Why the Other Answers Are Incorrect?

    Choice Explanation
    A (Lines 1 and 2 should be interchanged) No need to interchange the initialization of i and sum. Starting i = 1 and sum = 0 is logical for summing the first 10 elements, as long as the increment happens correctly.
    B (Line 3 should be changed to REPEAT UNTIL (i ≥ 10)) REPEAT UNTIL (i > 10) is correct because i starts at 1. The loop should stop when i exceeds 10, ensuring that 10 elements are summed. Changing the condition to i ≥ 10 would cause the loop to stop too early.
    D (No change is needed; the program works correctly) The program has an issue where i is incremented before nums[i] is accessed, causing it to skip the first element. So, a change is needed.

    Category: 3.12

    Problem Statement:

    The procedure BinarySearch(numList, target) correctly implements a binary search algorithm on the list of numbers numList. The procedure returns an index where target occurs in numList, or -1 if target does not occur in numList.

    Which of the following conditions must be met in order for the procedure to work as intended?

    Choices:

    • A. The length of numList must be even.
    • B. The list numList must not contain any duplicate values.
    • C. The values in numList must be in sorted order.
    • D. The value of target must not be equal to -1.

    Correct Answer: C

    Explanation:

    • Binary search is a divide-and-conquer algorithm that works by repeatedly dividing the search interval in half.
    • In order for binary search to function correctly, the list must be sorted because the algorithm relies on comparing the target with the middle element of the list and eliminating half of the remaining elements based on whether the target is smaller or larger.
    • If the list is not sorted, the binary search will not work as expected because the middle element comparison will not allow for efficient elimination of search space.

    Why the Other Answers Are Incorrect:

    Choice Explanation
    A (The length of numList must be even) The length of numList does not need to be even for binary search. The algorithm works for both even and odd length lists.
    B (The list numList must not contain any duplicate values) Binary search can still work with duplicate values. The presence of duplicates may affect which index is returned, but it will not prevent the binary search from functioning.
    D (The value of target must not be equal to -1) This is irrelevant. The binary search can handle any target value, including -1. If target is not found, it will simply return -1 as the result, which is an indicator that the element is not present.

    Category: 3.11

    Q50: Reasonable Time Algorithms

    Problem Statement:

    Consider the following algorithms. Each algorithm operates on a list containing n elements, where n is a very large integer.

    • Algorithm I: An algorithm that accesses each element in the list twice.
    • Algorithm II: An algorithm that accesses each element in the list n times.
    • Algorithm III: An algorithm that accesses only the first 10 elements in the list, regardless of the size of the list.

    Which of the algorithms run in reasonable time?

    Choices:

    • A. I only
    • B. III only
    • C. I and II only
    • D. I, II, and III

    Correct Answer: D

    Explanation:

    • Algorithm I accesses each element twice. Even though n is large, it still operates in linear time, O(n), since the constant factor (2) does not change the overall time complexity.

    • Algorithm II accesses each element n times. While this sounds large, it still operates in O(n²) time, which is considered reasonable time for large values of n, depending on the context.

    • Algorithm III accesses only the first 10 elements, which is a constant time operation O(1). It runs in constant time, regardless of the size of the list, which is always considered reasonable.

    Since all three algorithms operate in a reasonable amount of time (either O(n), O(n²), or O(1)), the correct answer is D.

    Why the Other Answers Are Incorrect:

    • A (I only) is incorrect because Algorithm II and III also run in reasonable time.
    • B (III only) is incorrect because Algorithm I and Algorithm II also run in reasonable time.
    • C (I and II only) is incorrect because Algorithm III runs in constant time, which is the most efficient.

    Category: 3.17

    Q58: Error in AnyPairs procedure

    Problem Statement:

    The following procedure is intended to return true if at least two of the three parameters (x, y, z) are equal in value, and false otherwise.

    PROCEDURE AnyPairs (x, y, z)
{
    IF (x = y)
    {
        RETURN (true)
    }
    ELSE
    {
        RETURN (y = z)
    }
}

    For which of the following procedure calls does the procedure NOT return the intended value?

    Choices:

    • A. AnyPairs("bat", "cat", "rat")
    • B. AnyPairs("bat", "bat", "rat")
    • C. AnyPairs("bat", "cat", "bat")
    • D. AnyPairs("bat", "cat", "cat")

    Correct Answer: C

    Explanation:

    The procedure is supposed to check if at least two parameters are equal. The logic used in the procedure only checks if x = y, and if that is not true, it checks if y = z. This leaves a gap where the procedure does not correctly account for the case when x = z but neither x = y nor y = z.

    For Option C (AnyPairs("bat", "cat", "bat")), the procedure returns false because it first checks if x = y (i.e., “bat” = “cat”), which is false. Then, it checks if y = z (i.e., “cat” = “bat”), which is also false. However, there is a pair of values that are equal (x = z, “bat” = “bat”), but the procedure doesn’t account for this situation. Therefore, the procedure does not return the intended value because it doesn’t recognize that x = z.

    Why Other Answers Are Correct:

    • A. AnyPairs("bat", "cat", "rat"): There are no equal values in the three parameters, so the procedure correctly returns false.

    • B. AnyPairs("bat", "bat", "rat"): The first condition (x = y) is true, so the procedure correctly returns true as expected.

    • D. AnyPairs("bat", "cat", "cat"): The second condition (y = z) is true, so the procedure correctly returns true.

    Category: 1.4

    Q66: Error in counting perfect numbers

    Problem Statement:

    In mathematics, a perfect number is a type of integer. The procedure IsPerfect(num) returns true if num is a perfect number and returns false otherwise.

    The following program is intended to count and display the number of perfect numbers between the integers start and end, inclusive. Assume that start is less than end. The program does not work as intended.

    Line 1:  currentNum = start
Line 2:  count = 0
Line 3:  REPEAT UNTIL (currentNum > end)
Line 4:  {
Line 5:     count = count + 1
Line 6:     IF (IsPerfect(currentNum))
Line 7:     {
Line 8:        count = count + 1
Line 9:        currentNum = currentNum + 1
Line 10:    }
Line 11:    currentNum = currentNum + 1
Line 12: }
Line 13: DISPLAY(count)

    Which two lines of code should be removed so that the program will work as intended?

    Choices:

    • A. Line 5
    • B. Line 8
    • C. Line 9
    • D. Line 11

    Correct Answer: A and D

    Explanation:

    The program is intended to count the number of perfect numbers between start and end. However, there are issues with how the count and currentNum are being updated.

    • Line 5 increments count for each iteration of the loop, even when the number is not perfect. This is unnecessary because we only want to count perfect numbers.
    • Line 8 increments count again inside the IF block when IsPerfect(currentNum) returns true. This causes an incorrect double increment when a perfect number is found.
    • Line 9 increments currentNum inside the IF block, which is not needed because currentNum should only be incremented once per loop iteration.
    • Line 11 correctly increments currentNum during each iteration of the loop, but it is redundant because Line 9 also increments currentNum when a perfect number is found.

    To fix the program, we need to:

    • Remove Line 5 to avoid incrementing count in each iteration regardless of whether the number is perfect.
    • Remove Line 11 because the loop should increment currentNum only once per iteration.

    Why Other Answers Are Incorrect:

    • B. Removing Line 8 would prevent the correct double increment of count when a perfect number is found, so it is not the correct choice.
    • C. Removing Line 9 would not solve the issue because Line 11 is also redundant.

    Category: 1.4

    Future Plan

    • Strengthen weak areas – Revise topics where scores were 0% and practice problems related to these areas.
    • Analyze mistakes – Go through incorrect answers, understand errors, and find similar problems to solve.
    • Revisit knowledge points - Go back to the Big Idea 3 video and make further notes based on the wrong questions, marking the test points