Problems

1. Which function grows faster? N log N or N1+ε where ε > 0?
2. An algorithm takes 0.5ms for input size 100. How long will it take for input size 500 if the running time is the following?
   • linear
   • O(n log n)
   • quadratic
   • cubic
3. An algorithm takes 0.5 ms for input size 100. How large of aproblem can be solved in 1 minute if the running time is the following
   • linear
   • O(n log n)
   • quadratic
   • cubic
4. Why is it important to assume integers in our computer model have a fixed width / size?

Coding

You will use GitHub Classroom for this assignment. The invitation link is classroom.github.com/a/eOmRrwVj

Remember to use the flags -Wall" and -std=c++17 when compiling.

Maximum Subsequence

Write a linear-time template function in C++ that will give the indices of the maximum subsequence of a vector.

• Begin by writing test cases. Use maxSubsequenceSampleTest.cpp as a starting point. (Rename the file so it doesn't include Sample), then add more tests. Don't forget to test types other than int.
• Edit maxSubSequence.hpp and place your code inside the existing maxSubsequence function. Do not edit the method signature.
• When you are finished, your code should compile against both maxSubsequenceMain.cpp and MaxSubsequenceTest.cpp without changes. If it doesn't, then it probably won't compile against my test suite.
• Your submission must include a script or makefile to build an executable that runs your tests. This script/makefile must run on EOS.

Matrix search

Suppose you have an NxN matrix such that each individual row is increasing from left to right and each individual column is increasing from top to bottom. Write a template function in C++ that decides if a given value is in the matrix. The running time of this function must be O(N). (Notice that the size of the matrix is O(N2); therefore, you can't examine each element in the matrix.) Write the function as a template that works for both integers and doubles.

• Begin by writing test cases. Use matrixSearchSampleTest.cpp as a starting point. (Rename the file so it doesn't include Sample), then add more tests. Don't forget to test types other than int.
• Edit searchMatrix.hpp and place your code inside the existing searchMatrix function. Do not edit the method signature.
• Your function should raise an std::invalid_argument exception if the matrix is not square.
• You may assume that the data in the matrix is ascending in each row and column. You do not need to verify this.
• When you are finished, your code should compile against both searchMatrixMain.cpp and searchMatrixTest.cpp without changes. If it doesn't, then it probably won't compile against my test suite.
• Your submission must include a script or makefile to build an executable that runs your tests. This script/makefile must run on EOS.

Submission and grading

• Submit the written problems in class.
• Make sure all relevant code is checked in to GitHub by the due date.
• Unless you indicate otherwise, I will assume that the code to be graded is on the master branch.
• You are expected to fix and re-submit buggy code. Because your code will eventually be correct, your grade will be based primarily on timliness.
• There is a penalty for each buggy submission.

Updated Tuesday, 20 August 2019, 6:53 AM