Median and matrices

Questions 1 to 5 of 8

1. 1. Using the usual method from the lesson, how many scalar multiplications does it take to multiply two 1000 by 1000 matrices?

   Type a number.

2. 2. What is the running time of the binary-search median method, where m and n are the lengths of the two sorted lists?

   O(m + n), because the method still reads every value onceO(log(min(m, n))), because the search runs over the smaller listO(m * n), because every value of one list is compared with every value of the otherO(log(m + n)), because the search runs over all values together
3. 3. What does this program print? ``cpp #include <algorithm> #include <climits> #include <iostream> #include <span> #include <stdexcept> #include <vector> double findMedianSortedArrays(std::span<const int> a, std::span<const int> b) { if (a.size() > b.size()) { return findMedianSortedArrays(b, a); } const int m = static_cast<int>(a.size()); const int n = static_cast<int>(b.size()); const int total = m + n; const int leftCount = (total + 1) / 2; int lo = 0; int hi = m; while (lo <= hi) { const int i = (lo + hi) / 2; const int j = leftCount - i; const int aLeft = (i == 0) ? INT_MIN : a[i - 1]; const int aRight = (i == m) ? INT_MAX : a[i]; const int bLeft = (j == 0) ? INT_MIN : b[j - 1]; const int bRight = (j == n) ? INT_MAX : b[j]; if (aLeft <= bRight && bLeft <= aRight) { if (total % 2 == 1) { return std::max(aLeft, bLeft); } return (static_cast<double>(std::max(aLeft, bLeft)) + static_cast<double>(std::min(aRight, bRight))) / 2.0; } if (aLeft > bRight) { hi = i - 1; } else { lo = i + 1; } } throw std::invalid_argument("inputs are not sorted"); } int main() { std::vector<int> a = {1, 4, 6}; std::vector<int> b = {2, 3, 5, 7, 8}; std::cout << findMedianSortedArrays(a, b) << '\n'; } ``

   44.254.55
4. 4. What does this program print? ``cpp #include <iostream> int main() { long long A11 = 2, A12 = 1, A21 = 0, A22 = 3; long long B11 = 4, B12 = 5, B21 = 6, B22 = 7; long long M1 = (A11 + A22) * (B11 + B22); long long M2 = (A21 + A22) * B11; long long M3 = A11 * (B12 - B22); long long M4 = A22 * (B21 - B11); long long M5 = (A11 + A12) * B22; long long M6 = (A21 - A11) * (B11 + B12); long long M7 = (A12 - A22) * (B21 + B22); std::cout << M1 + M4 - M5 + M7 << ' ' << M3 + M5 << ' ' << M2 + M4 << ' ' << M1 - M2 + M3 + M6 << '\n'; } ``

   14 17 18 2214 17 19 2114 18 18 2114 17 18 21
5. 5. Why does findMedianSortedArrays swap the two lists when a is longer than b?

   Because the median changes if the lists are given in the other order.Because the count j = leftCount - i must stay between 0 and n, which holds for every step when the searched list is the shorter one.Because std::span cannot hold a list longer than 1000 values.Because the sum of the two middle values must be computed in double, which needs the shorter list first.