Problem 1: Polynomial Evaluation

Write a C++ program that evaluate a degree-n polynomial

anxn + an1xn1 + + a1x + a0

with n multiplications and n additions only. Note that this is the optimal, meaning that you cannot do this evaluation with fewer arithmetic operations.

Implement the Horners method to achieve this optimal computation.

Input:

A single line containing n + 3 numbers, separated by spaces. The first number is the value of x, then the degree n of the polynomial to evaluate, followed by the n + 1 coefficients a_n, a_n1, ,

a₀.

The value x is a floating-point number and the numbers n, a_n, a_n1, , a₀ are integers, and n 0.

Output:

A single line containing the result of the polynomial evaluation, printed as a fixed floating number with 6 decimal places.

You may use setprecision(n) defined in the header <iomanip> to set the precision parameter of the output stream.

Requirement:

Use the _float data type for all floating point computations in this program.

You can ONLY use the simple data types char , bool , int , float . In other words, you are not allowed the use other data types or data structures such as arrays, vectors, etc.

Sample Test Cases

User inputs are shown in blue.

1_1

-1.5 0 4

4.000000

1_2

2.43 1 4 -2

7.720000

1_3

3.289 3 -1 2 4 -6

-6.787785

1_4

-0.0001 10 11 -10 9 -8 7 -6 5 -4 3 -2 1

1.000200

Problem 2: A Divisor Matrix

Write a C++ program that implement the divisor matrix as follows:

Input:

Your program should prompt the user for two positive integers _a , _b . (See sample test cases for the required prompt messages.) You may assume that the user will always input positive integers such that the following holds, 0 <= a < b < 1000 .

The user will then be prompted for two divisors. You may assume that divisors entered by the user are valid, for which the following holds, 1 <= divisor < 1000 .

Output:

The program will then output a matrix with the following elements.

The first row will start with an _M followed by the two divisors in input order.

The first column, beneath the _M , will contain the integers between _a and _b (including _a and excluding _b ), in increasing order.

For the remaining two elements of each row, there will be a ₁ if the integer in that row is

divisible by the divisor at the head of that column, otherwise ₀ .

Matrix elements should be separated by a space. Note that there is no trailing space after the last element of a row.

Requirement:

You can ONLY use the simple data types char , bool , int , double . In other words, you are not allowed the use other data types or data structures such as strings, arrays, vectors, etc.

Sample Test Cases

User inputs are shown in blue.

2_1:

a: 1

b: 10

Divisor 1: 2

Divisor 2: 3

M 2 3

• 0 0
• 1 0
• 0 1
• 1 0
• 0 0
• 1 1
• 0 0
• 1 0
• 0 1

2_2:

a: 134 b: 141 Divisor 1: 4

Divisor 2: 5

M 4 5

• 0 0
• 0 1
• 1 0
• 0 0
• 0 0
• 0 0
• 1 1

2_3:

a: 2 b: 21 Divisor 1: 2

Divisor 2: 5

M 2 5

• 1 0
• 0 0
• 1 0
• 0 1
• 1 0
• 0 0
• 1 0
• 0 0
• 1 1
• 0 0
• 1 0
• 0 0
• 1 0
• 0 1
• 1 0
• 0 0
• 1 0
• 0 0
• 1 1

Problem 3: Sine Function Approximation

Write a C++ program which calculates an estimation of sinx using Taylor series approximation with the formula:

sinx = n (1)i 2i+1, x (2i + 1)! i=0

where i! = 1 2 3 i denote the factorial of i, and 0⁰ is defined as 1. The integer n governs the order of approximation and you may assume that n ranges from 0 to 50 inclusively in this

question.

Input:

a line with two numbers: a real number x (3 x 3) followed by an integer n (0 n 50).

Output:

Your program should output the estimations of sinx as n increases. Specifically, your program should

On the first line, print the result of sinx as returned by the predefined function _sin() in

_<cmath> as a fixed floating number with 15 decimal places.

Output the values of n and sinx on the subsequent lines as n increases. The values n and sinx on each line are separated by a space. The value sinx is printed as a fixed floating number with 15 decimal places.

You may use setprecision(n) defined in the header <iomanip> to set the precision parameter of the output stream.

Requirement:

Use only the double and int data types in your calculations.

You can ONLY use the simple data types char , bool , int , double . In other words, you are not allowed the use other data types or data structures such as strings, arrays, vectors, etc.

Note:

You cannot evaluate the factorial operator in a brute-force manner using multiplications only, because overflow can easily occur which means that the resulting value is too large to be stored in an _int . (Consider 30! ~= 2.6525e+32 which cannot be held by even the

unsigned long long type).

Divisions involving some large numbers can easily run into numerical inaccuracy issues (you will learn more about this in the machine organization course).

Hence, you should do divisions before multiplications (whenever possible) to keep the intermediate values at each iteration of the calculation small.

Since different orders of arithmetic operations may entail slight difference in the final evaluation, your results will be check against the test outputs for correctness up to the first 5 decimal points only.

Sample Test Cases

User inputs are shown in blue.

3-1

• 0

sin(x) by cmath: 0.000000000000000

Taylor series approximation: 0 0.000000000000000

3_2

• 10

sin(x) by cmath: 0.841470984807897

Taylor series approximation:

• 000000000000000
• 833333333333333
• 841666666666667
• 841468253968254
• 841471009700176
• 841470984648068
• 841470984808658
• 841470984807894
• 841470984807897
• 841470984807897
• 841470984807897

3_3

-2.9 20

sin(x) by cmath: -0.239249329213982

Taylor series approximation:

0 -2.900000000000000 1 1.164833333333333

• -0.544429083333334
• -0.202169632757937
• -0.242147438026535
• -0.239090953096454
• -0.239255728982749
• -0.239249130100826
• -0.239249334132433
• -0.239249329115164
• -0.239249329215629
• -0.239249329213960
• -0.239249329213983
• -0.239249329213983
• -0.239249329213983
• -0.239249329213983
• -0.239249329213983
• -0.239249329213983
• -0.239249329213983
• -0.239249329213983
• -0.239249329213983

Problem 4: Caesar Shifting

Write a C++ program which encrypts and decrypts some input characters using the Casesar Shifting algorithm detailed below.

Input:

a line of input s k c₁ c₂ c₃ , where s is either the character _e for encryption, or the character _d for decryption k is an integer for the number of shifts used in the Caesar shift algorithm

c₁ c₂ c₃ is a sequence of space separated characters, ended by _! , to be encrypted or decrypted

Output:

the encrypted/decrypted message ended by _! . No space between two consecutive characters.

Algorithm:

To encrypt (decrypt) a letter c (within the alphabet A-Z or a-z) with a shift of k positions:

1. Let x be cs position in the alphabet (0 based), e.g., position of _B is 1 and position of _g is 6.
2. For encryption, calculate y = x + k modulo 26; for decryption, calculate y = x k modulo 26.
3. Let w be the letter corresponding to position y in the alphabet. If c is in uppercase, the encrypted (decrypted) letter is w in lowercase; otherwise, the encrypted (decrypted) letter is w in uppercase.

A character which is not within the alphabet A-Z or a-z will remain unchanged under encryption or decryption.

Example. Given letter _B and k = 3, we have x = 1, y = 1 + 3 mod 26 = 4, and w = _E . As _B is in uppercase, the encrypted letter is _e .

Requirement:

Implement a function CasesarShift() which takes in a char c and an int k , where c is the character to undergo Caesar Shifting and _k is the number of positions (can be negative) to shift, and return the processed _char after Caesar Shifting. The function prototype is given by:

char CaesarShift(char c, int k)

You can ONLY use the simple data types char , bool , int , double . In other words, you are not allowed the use other data types or data structures such as strings, arrays, vectors, etc.

Sample Test Cases

User inputs are shown in blue.

4_1

e 1 ! !

4_2

e 3 a B c D e !

DeFgH!

4_3

• 3 D e F g H ! aBcDe!

4_4

• -1 H e l l o E N G G 1 3 4 0 / C O M P 2 1 1 3 ! gDKKNdmff1340/bnlo2113!

4_5

d 10 n 3 V 3 D 3 N _ M Y N 3 _ S C _ N 3 L E Q Q 3 N _ M Y N 3 ! D3l3t3d_cod3_is_d3bugg3d_cod3!

Problem 5: Bounding Boxes

Write a C++ program to compute a minimum-sized axis-aligned bounding box (AABB) for a set of input 2D geometries. An AABB is a rectangle with sides parallel to the x-, y-axes which encloses some given geometries. The input and output of your program are as follows:

Input: Each line of the user input begins with a character indicating the type of geometry, followed by some parameters of the geometric object. The input line can be one of the followings:

R x y width height

where _R represents an input rectangle, x, y are floating-point numbers for the x-, y-coordinates of the rectangle center, width and height are floating-point numbers for the rectangle size along the x- and y-axes, respectively.

C x y radius

where _C represents an input circle, x, y are floating-point numbers for the x-, y-coordinates of the circle center, and radius is a floating-point number for the radius of the center

P n x₁ y₁ x₂ y₂ x_n y_n

where _P represents an input point set, n is an integer indicating the number of points in the set, and x_i, y_i, i = 1,,n are floating point numbers for the x-, y-coordinates of the n points

#

indicates end of input

Output:

A single line

x y width height

where x and y are floating-point numbers for the x-, y-coordinates of the center of the minimumsized AABB, width and height are floating-point numbers giving the sizes of the AABB along the x-, y-axes, respectively.

Requirement:

Use the double data type for floating point calculations.

Implement the functions RectangleBB() , CircleBB() and PointSetBB() which take user inputs and calculate the corresponding bounding boxes of the different geometries (rectangles, circles & point sets). The function prototypes are:

void RectangleBB(double &xmin, double &xmax, double &ymin, double &ymax)

void CircleBB(double &xmin, double &xmax, double &ymin, double &ymax)

void PointSetBB(double &xmin, double &xmax, double &ymin, double &ymax) where xmin , xmax , ymin , ymax are the calculated extends of the bounding boxes for the geometry. Note that these parameters are pass-by-reference, since they are the computation results with we would like the calling function to be able to access after function termination. By using pass-by-reference, the functions would be able to modify the actual arguments passed in from the calling function.

You can ONLY use the simple data types char , bool , int , double . In other words, you are not allowed the use other data types or data structures such as strings, arrays, vectors, etc.

Note:

The questions assume no bound for the floating-point parameters (x, y, width, height, radius) of the input geometries and therefore they can be any values that a double data type can hold. You may use std::numeric_limits<double>::lowest() and

std::numeric_limits<double>::max() defined in the header <limits> in your program to obtain the smallest and the largest possible values, respectively, for the double data type.

Sample Test Cases

User inputs are shown in blue.

5_1

R 0 0 3 2

#

0 0 3 2

5_2

C -0.5 3.2 1.6

#

-0.5 3.2 3.2 3 2

5 3

P 2 3 -2 -1 4

# 1 1 4 6

5_4

P 3 -1.5 3 3 3 5 3

#

1.75 3 6.5 0

5_5

P 2 3 -2 -1 4

C -0.5 3.2 1.6

P 3 -1.5 3 3 3 5 3

R 0 5.75 3 2

#

1.45 2.375 7.1 8.75