algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

pre-read-problems.txt (1259B)


      1 2. Given an M × N integer matrix Q (1 ≤ M, N ≤ 30), determine if there exists a
      2 sub-matrix of Q of size A × B (1 ≤ A ≤ M, 1 ≤ B ≤ N) where mean(Q) = 7.
      3 (a) Try all possible sub-matrices and check if the mean of each sub-matrix is 7.
      4 This algorithm runs in O(M 3 × N 3 ).
      5 
      6 this would use 2 for loops to iterate over all possible upper left locations
      7 
      8 we would then have two more for loops, iterating from A -> M and B -> N, taking the mean at each step to check each possible submatrix of correct sizes from the given position.
      9 
     10 (b) Try all possible sub-matrices, but in O(M 2 × N 2 ) with this technique:
     11 
     12 memoize solution for sub-matrices that will be fully enclosed, reusing such computations? uncertain
     13 
     14 (this is a see what you know before starting type question)
     15 
     16 ---
     17 
     18 7. You want to test if the factorial of n, i.e. n! is divisible by an integer m. 1 ≤ n ≤ 10000.
     19 What should you do?
     20 (a) Test if n! % m == 0.
     21 (b) The naı̈ve approach above will not work, use:
     22 (Section 5.5.1).
     23 
     24 better approach:
     25 
     26 if m <= n -> true
     27 else compute prime factorization of n, iff any of the numbers <= n then true else false?
     28 
     29 (this seems wrong in the case of factorial matching, but not totally confident; seems like there's some sort of trick like that)