Must have 3 of the 5 questions done, can supply examples of some of the problems also.
Due: 11:59 PM on Thursday, November 19 Submit any three of the C++ programs below. If you are compiling a single file from the command line on a Mac/Linux system, I suggest using the command g++ your program name .cpp -std=c++1y -o your executable name g++ each program that requires only a single file. 1. An integer is a palindrome in base b if reversing its base b representation yields the same integer (i.e. if reading the number when written in base b forwards and backwards gives the same value). For example, 3124213 is a palindrome in base 10, since reversing the digits yields 3124213. However 34546 is not a palindrome in base 10, since reversing the digits yields 64543, a distinct number. 21 is a palindrome in base 2, since its base 2 representation is: 10101. Write a C++ program that takes an integer b ≥ 2, followed by any number of file names, passed by command line argument. The files passed to your program are guaranteed to consist of positive integers, separated by spaces or line breaks, with an unknown number of integers per line. Your program should report the total number of base b palindrome numbers encountered among all the files, the sum of the palindrome numbers, the number of distinct palindrome numbers, and the sum of all distinct palindrome numbers to the user. Among the three sample files on Sakai, there are 8646 base 10 palindromes, and the total of these is 392536868. There are 1098 distinct base 10 palindromes, and the total of these is 50045040. Among the three sample files on Sakai, there are 5144 base 2 palindromes, and the total of these is 177209440. There are 644 distinct base 2 palindromes, and the total of these is 21865050. Among the three sample files on Sakai, there are 8493 base 31 palindromes, and the total of these is 150725109. There are 1062 distinct base 31 palindromes, and the total of these is 19042462. (Use long long ints for this problem to avoid potential problems with the maximum size of the sum of all of the appropriate integers.) 2. Suppose a person flips (a potentially biased) coin repeatedly until they notice that a particular sequence of consecutive flips has occurred, making note of how many flips were required until that sequence occurred. For example, if they were looking for the pattern HHT and flipped: HTTHTHHT, then it took them eight total flips until the first appearance of the pattern HHT in consecutive flips. Write a program that uses a Monte Carlo simulation to determine the expected number of flips until the first emergence of the desired pattern. Your program should take three command line arguments: a filename where the pattern is stored, a double for the probability p of flipping heads on each flip, and a number of trials. The program reports to the user the expected number of flips required to see the pattern for the first time. The file will consist of the characters H and T separated by spaces (see the file on Sakai for an example of what this file might look like). For this problem, here are two hints that might be of use: consider using the list container class, instead of vector. The list container class supports push front and pop front member functions. Alternatively (and likely less efficiently), you can remove the first element of a vector v using v.erase(v.begin()). For the pattern HTTH, with a fair coin, the expected number of flips is 18. For the pattern HTH, with a 20% chance of heads on each flip, the expected number of flips is around 36.2. For the pattern HTT, with a 20% chance of heads on each flip, the expected number of flips is around 7.8. For the pattern HHTHT, with a fair coin, the expected number of flips is around 32. 3. Consider moving a rook around an M × M chess board at random, using only legal moves. The rook will start in the lower left corner of the board. For each move, the rook will move according to one of its available legal moves, selected uniformly at random (i.e. each legal move has the same chance of being selected as any other legal move). We are interested in the expected number of moves until the rook has been stationary on every square of the board at least once. After 0 moves, the rook has already been stationary on one square (the lower left). Write a C++ Monte Carlo simulation to compute the expected number of moves required. Your program should take two command line arguments: an integer M representing the size of the board and a long long integer N representing the number of trials to perform. Your program should report to the user the approximate expected number of moves that the rook must make until it has been stationary on every square of the board. For a 4 × 4 board, the expected number of moves to visit every square at least once is approximately 55.1 moves. 4. In this problem, we will write a C++ class to implement a polynomial with real coefficients. On Sakai, a file named “polynomial.h” appears, containing a class definition. Your goal is to implement the member functions in the corresponding “polynomial.cpp” file in order for the class to correctly implement the behavior of adding, subtracting and multipying polynomials with real coefficients (with some additional behaviors as specified in the header). For this problem, you only need to submit the “polynomial.cpp” file implementing the member functions for the polynomial class. A main routine has been provided, as well as some example output. Additionally, a “polynomial.cpp” file has been provided so that you do not need to copy-paste all the member (and non-member) function declarations. 5. For a non-negative integer n, let f(n) denote the number of ways that n can be written as a sum of 0 or more distinct positive primes, where the primes are assumed to be ordered from least to greatest. For example, f(8) = 1, as the only way to express 8 as a sum of distinct positive primes is as 8 = 3 + 5. However, f(16) = 3, as 16 can be expressed in three different ways as the sum of distinct positive primes: 16 = 2+3+11, 16 = 3+13, 16 = 5+11. Additionally, f(2) = 1 since 2 can only be expressed as the sum (with one addend) 2 = 2. f(0) = 1 as 0 can be expressed only as the empty sum. f(4) = 0 as 4 cannot be expressed as the sum of distinct positive prime numbers. Write a program that accepts a single command line argument, representing a non-negative integer N. The program then writes the values of f(n) for n = 0,1,...,N to a file named “final exam output.txt”, with one value per line in sequence. Use an implementation with a “reasonably efficient” execution time (e.g. the program will finish the computation for N = 1000 in at most a few seconds). (Make sure to use long long ints to calculate f, as this quantity grows quickly with n. For example, f(1000) = 2728799772.) A list of the first 83 values of this function is given at the Online Encyclopedia of Integer Sequences at: https://oeis.org/A000586/list Note: this problem is (in my opinion) more challenging conceptually than any other on this exam, but you will likely learn some new techniques (or how to use old ones more effectively) if you complete it.