FN6805: Object Oriented Programming I

Problems - Set 4

Dr. Yang Ye
Nanyang Business School, NTU, Singapore
yy@runchee.com

Question 4-1
Euclidean Algorithm
The Euclidean algorithm for finding the GCD (Greatest Common Divisor) of two positive integers
m,n can be described as follows:
Algorithm:

If m = n then return m
If m < n use gcd(m,n) = gcd(m, n mod m)
If m > n use gcd(m,n) = gcd(m mod n, n)

Requirements:
• Write a function to calculate GCD for two integers with the convention gcd(0,a) = gcd(a,0)
= a for all positive integers a
• Write a test function to test at least 3 different cases
• Use modern C++ practices with appropriate parameter types

int gcd(int a, int b);

void test_gcd();

 Test Cases

Consider testing:
• Normal cases: gcd(48, 18) = 6
• Edge cases: gcd(0, 5), gcd(7, 0)
• Large numbers: gcd(1071, 462)

1
Question 4-2
Partition of Integer and p(n)
A partition of a positive integer n is a decreasing sequence of positive integers whose sum equals
n (the order of the terms does not matter).

For example, the partitions of 4 are: 4, 3+1, 2+2, 2+1+1, 1+1+1+1.

The number of partitions of n is denoted by p(n). For example, p(4) = 5.
Here is a table of the first values of p(n):

n p(n) partitions
1 1 1
2 2 2 = 1+1
3 3 3 = 2+1 = 1+1+1
4 5 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1
5 7 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1

Objective: Compute p(n) for a given n.

Let P(n, k) be the number of partitions of n with largest part not more than k.
For instance: P(5, 2) = 3, P(5, 3) = 5, P(5, 4) = 6, and P(5, 5) = 7.
Base cases:
• P(n, 1) = 1 for all n ≥ 1
• P(0, k) = 1 for all k ≥ 0
• P(n, k) = 0 for k < 1 or n < 0
Recurrence relation:
𝑃 (𝑛, 𝑘) = 𝑃 (𝑛, 𝑘 − 1) + 𝑃 (𝑛 − 𝑘, 𝑘) for all 𝑘, 𝑛 ≥ 0

Tasks:
1. Write the recursive function int P(int n, int k). Note that P(n,n) = p(n). It’s expected
that p(50) = 204226.
2. Create a memoization version of the recursive function to improve performance.

 Memoization

Use a 2D array or std::map to store previously computed values to avoid redundant calcu
lations.

2
Question 4-3
Bubble Sort
Bubble sort is a simple sorting algorithm that puts a given list of numbers 𝑎1 , …, 𝑎𝑁 into
increasing order by successively comparing adjacent elements and interchanging them if they are
in the wrong order.
Pseudo code:

for i := 1 to N - 1
for j := 1 to N - i
if a_j > a_{j+1} then exchange a_j and a_{j+1}
end
end

Requirements:
• Write a function called bubble_sort() to implement this algorithm
• The function should take a container of type double (STL std::vector or std::array, but not
C style array)
• Instead of traditional variable swapping, use std::swap() function from #include
<algorithm>
• Look up std::swap() on cppreference.com for proper usage

void bubble_sort(std::vector<double>& arr);

 Modern C++ Practice

• Use size_t for loop counters when working with container sizes
• Consider using range based for loops where applicable
• Pass containers by reference to avoid unnecessary copying

Question 4-4
STL List Operations
Tasks:
• Create a list L1 containing the numbers 0, 1, …, 9
• Create a list L2 containing 10, 11, …, 19
• Append L2 to the end of L1 using the splice() function
• Print the sizes of L1 and L2 to the screen
• Remove all even numbers from L1
• Print the first and last element of L1 to the screen

3
 std::list<int> L1, L2;
// Initialize lists...
L1.splice(L1.end(), L2); // Moves elements from L2 to L1

 STL List Operations

• Use std::list<int> for the list container

• splice() moves elements between lists without copying
• Use remove_if() with a lambda function to remove even numbers efficiently
• Remember to check if the list is empty before accessing front() or back()

Question 4-5
Prime Number Generation using Sieve Method
Objective: Find all prime numbers less than 1,000,000
Requirements:
• Store the final list of primes in an array of length 80,000 (whose size is more than enough) with
entries of type int
• Print the total number of primes found
• You may use the following optimization: an odd positive integer 𝑛 > 1 is prime if and only if it
√
has no prime divisor < 𝑛
Algorithm suggestion:
1. Use the Sieve of Eratosthenes algorithm for efficiency
2. Start with all numbers marked as potentially prime
3. For each prime found, mark all its multiples as composite

std::vector<bool> sieve(1000000, true); // true means potentially prime

std::vector<int> primes;
primes.reserve(80000); // Pre-allocate space

 Optimization

• Only check odd numbers after 2

• Use std::vector<bool> for the sieve (space efficient)
• Reserve space in the primes vector to avoid reallocations

Question 4-6
Matrix Storage and Access

4
Store a matrix using two different methods and print the entries to screen both row wise and
column wise.
Method 1: 2D vector

std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols));

Method 2: 1D vector with index calculation

std::vector<int> matrix(rows * cols);

// Access element at (i,j): matrix[i * cols + j]

Requirements:
• Create a 3×4 matrix with sample data
• Print all elements row by row
• Print all elements column by column
• Use modern C++ practices with appropriate loop constructs

 Modern C++ Iteration

Use range based for loops where possible:

for (const auto& row : matrix) {

for (const auto& element : row) {
std::cout << element << " ";
}
}

Question 4-7
List Element Replacement
Write and test a function:

void replace_list(std::list<int>& L);

Requirements:
• Replace all elements of value 0 in list L with value 1, while maintaining the order of elements
in L
• The function shall use pass by (non const) reference, so it can modify L directly
Example:
• Input list: 0-0-1-3-0-5-0-6
• Output list: 1-1-1-3-1-5-1-6

5
Implementation approaches:
1. Use iterators to traverse and modify the list
2. Use std::replace() algorithm from <algorithm>

// Method 1: Manual iteration

for (auto& element : L) {
if (element == 0) element = 1;
}

// Method 2: STL algorithm

std::replace(L.begin(), L.end(), 0, 1);

 Testing

Create test cases with various scenarios: all zeros, no zeros, mixed values, empty list.

Question 4-8
Vector Operations Practice
After each of the following operations, print all entries of the vector to the screen:
1. Create a vector of length 10 with entries of type int (initialized to default values)
2. Append two new values to the end of the vector
3. Remove the last element of the vector
4. Change the size of the vector to 20
5. Remove all entries of the vector
Implementation requirements:
• Use std::vector<int>
• Use appropriate vector member functions: push_back(), pop_back(), resize(), clear()
• Print vector contents using a range based for loop or iterators

void print_vector(const std::vector<int>& vec) {

std::cout << "Vector contents: ";
for (const auto& element : vec) {
std::cout << element << " ";
}
std::cout << " (size: " << vec.size() << ")\n";
}

6
  Vector Behavior

Observe how the vector behaves when resized to a larger size what values do the new
elements have?

Question 4-9
Sudoku Validation
Write a program that analyzes the following Sudoku puzzle:
Tasks:
• Print the nine rows (i.e., their entries) of the Sudoku square
• Print the nine columns of this Sudoku square
• Print the nine 3×3 subsquares of this Sudoku square
• Verify that the sum of each row, each column, and each 3×3 subsquare are equal
Sudoku data:

std::vector<std::vector<int>> sudoku = {
{8,9,5,7,4,1,6,2,3},
{2,4,3,9,5,6,8,1,7},
{7,6,1,8,2,3,4,9,5},
{9,3,4,6,7,5,1,8,2},
{6,1,7,2,9,8,5,3,4},
{5,8,2,3,1,4,9,7,6},
{3,5,9,1,6,2,7,4,8},
{1,2,6,4,8,7,3,5,9},
{4,7,8,5,3,9,2,6,1}
};

Expected sum: Each row, column, and 3×3 subsquare should sum to 45.

 Implementation Strategy

• Use nested loops to access elements systematically

• For 3×3 subsquares, use integer division to determine which subsquare an element belongs
to
• Create separate functions for each validation type to improve code organization

7
Question 4-10
Bond Pricing with Zero Curve
Background: The YTM pricing for a fixed rate bond finds the YTM that makes the bond price
equal to the market price:
𝐶 𝐶 𝐶 𝐶
𝑘 𝑘 𝑘 1+ 𝑘
𝑃𝑦𝑡𝑚 = 𝑦 + 2
+⋯+ +
1+ 𝑦 𝑛𝑘−1 𝑦 𝑛𝑘
𝑘 (1 + 𝑘𝑦 ) (1 + 𝑘) (1 + 𝑘)

With the zero coupon curve and the interpolator function from Question 3.7, we can implement
Zero pricing:
𝐶 𝐶 𝐶 𝐶
𝑃𝑧𝑒𝑟𝑜 = 𝐷0, 1 + 𝐷0, 2 + ⋯ + 𝐷0,𝑛− 1 + 𝐷0,𝑛 (1 + )
𝑘 𝑘 𝑘 𝑘 𝑘 𝑘 𝑘

Parameters:
• 𝐹 : face value
• 𝐶: coupon rate
• 𝑛: maturity time (in years)
• 𝑘: payment frequency parameter (1=“A”nnual, 2=“S”emi annual, 4=“Q”uarterly)
• 𝐷0,𝑡 : t maturity discount factor
Required Functions:
1. get_df(): Obtain discount factor from zero rate curve

double get_df(int end_date, const RateCurve& ic, int today) {

// ...
double r = interpolate(dates, rates, end_date);
double days_diff = (end_date - today);
double d = std::exp(-days_diff / 365.0 * r / 100.0);
return d;
}

2. bond_price_zero(): Calculate bond price from discount factors and payment schedule

double bond_price_zero(double face_value, double coupon_rate,

double maturity, const std::string& ps, int today,
const RateCurve& ic, double ic_spread = 0.0);

Parameters
• maturity: number of years
• ps: payment schedule (“A”=annual, “S”=semi annual, “Q”=quarterly)
• ic_spread: set to 0.0 (unused for now)
Discount Factor

8
 𝑡
𝐷0,𝑡 = 𝑒−𝑟× 365

where 𝑡 is the number of days between the end date and today.

Test Cases
auto v00 = bond_price_zero(100, 0.02, 4, "Q", 41082, IC, 0.0);
std::cout << "v00: " << v00 << '\n'; // Expected: v00: 100.579

auto v01 = bond_price_zero(100, 0.03, 2, "S", 41082, IC, 0.0);

std::cout << "v01: " << v01 << '\n'; // Expected: v01: 103.281

auto v02 = bond_price_zero(100, 0.04, 3, "A", 41082, IC, 0.0);

std::cout << "v02: " << v02 << '\n'; // Expected: v02: 106.992

 Implementation Notes

• Zero rate discount curve should be provided from NTULearn as zero_rate_curve.h

• Use the interpolation function from Question 3.7 to obtain rates on specific dates
• Both end date and today represent end of day (EOD), so days difference is simply (𝑡1 − 𝑡0 )