Problem Set #1 Solution

De nition 1. Suppose f and g are positive functions from N to N. We say that f(n) = O(g(n)) if there exists a positive constant C such that for every n in N, we have f(n) Cg(n).




Problem 1 (Quiz). I. Answer the following questions. Enter your answers under the Quizzes section of Canvas. We will open the Canvas submission page on January 10.




 
True or False: n = O(n log2 n).




 
True or False: n2 = O(n).




 
True or False: n log52 n = O(n2).




 
True or False: log2 n = O(loge n).




 
True or False: loge n = O(log2 n).




 
True or False: 2n = O(nlog2 n).




 
True or False: nlog2 n = O(2n).




 
True or False: For all positive functions f and g, if f(n) = O(g(n)), then n f(n) = O(n g(n)).




 
True or False: For all positive functions f and g, if f(n) = O(g(n)), then f(n)+n = O(g(n)+n).




Problem 2 (Warmup programming exercise. You can discuss this problem with your classmates. However, you must acknowledge any collaboration.). A group of students at Northwestern University (NU) want to nd out how popular Northwestern is. In order to do so, they plan to write a program that reads news on the Internet and counts the number of occurrences of the word \NU" (the letters must be capitalized). Your goal is to write a function with the following signature/declaration:




int CountNUOccurrences(const std::string& message)




that counts and returns the number of substrings \NU" in the string message.




Instructions for the programming assignment. Download les:




student code 1.h { this le should contain your solution.




problem solver 1.cpp { this is the main le in the project (don't edit this le!).




test framework.h { this is a library responsible for reading and writing data les (don't edit this le!)




problem set 1.in { this le contains test problems for your algorithm (don't edit this le!)







Place all les in a new folder/directory. Write your code in the function CountNUOccurrences. Also, write your name in the function GetStudentName. Both functions are located in le student code 1.h. Compile and run your code. To compile your code do the following.










1
If you use GNU C++ compiler, type




g++ -std=c++11 problem solver 1.cpp -o problem solver 1




If you use CLang compiler, type




clang++ -std=c++11 problem solver 1.cpp -o problem solver 1




If you use Microsoft Visual C++ compiler, start Developer Command Prompt and type cl /EHsc problem solver 1.cpp







Your compiler should be compatible with C++11. If you work in TLab, you need to start developer tools rst: Type




scl enable devtoolset-4 bash




Once you compile your code, start your program. Type ./problem solver 1 on Unix or Mac and problem solver 1.exe on Windows. Make sure that the executable is located in the same folder as le problem set 1.in. Your program will generate solution 1.dat that contains solutions to the problems from le problem set 1.in. If your code works correctly, you will get the following message:







Problem set 1. Your algorithm solved all test problems correctly. Congratulations! Don't forget to submit your source code and le solution 1.dat via Canvas.




If your code makes a mistake, you may get a message like this:




Problem set 1. Mistake in problem #15. Correct answer: 4. Your answer: 12.




Finally, when your code is ready, submit les student code 1.h and solution 1.dat via Canvas.




Make sure that you are submitting the latest versions.




Remark: If you want to debug your code, please, type ./problem solver 1 15 on Unix or Mac and problem solver 1.exe 15 on Windows. This command will call your function only on one problem { the problem #15 and thus let you debug your code on the problem where your program erred. Note that this command will not generate or update solution 1.dat. So before submitting your solution, you need to run your program without any command line arguments.









































































2