Homework #10

Important

The file submission requirements are different than previous homeworks.

For the C++ problems below, you need to submit a header file (.H) implementing the class described in the problem and a source file (.cpp) containing the main() function and any tests that the problem asks for.

For the python problems below, you need to submit a python source file (.py).

Important

All work must be your own.

You may not use generative AI / large-language models for any part of this assignment.

1. Multi-dimensional array extensions : Start with our Contiguous multi-dimensional array implementation from class. Add the following member functions:

   • .sum() : returns the sum of all the elements in the array.

   • .max() : returns the maximum value in the array.

   • .min() : returns the minimum value in the array.

   Write a test driver, and create an array representing the following 5 by 4 matrix:

   \[\begin{split}\left ( \begin{array}{ccccc} -20.0 & 4.5 & 1.45 & 7.9 \\ -1.2 & -10.4 & 8.9 & 6.49 \\ 12.7 & 14.4 & 6.5 & -10.9 \\ -2.4 & 2.15 & 1.15 & 20.4 \\ -22.5 & 64.5 & -1.8 & -7.1 \end{array} \right )\end{split}\]
   solution

   First the updated header:

   Listing 175 array.H

   #ifndef ARRAY_H
   #define ARRAY_H
   
   #include <format>
   #include <algorithm>
   #include <numeric>
   #include <vector>
   #include <iostream>
   #include <cassert>
   
   // a contiguous 2-d array
   
   // here the data is stored in row-major order in a 1-d memory space
   // managed as a vector.  We overload () to allow us to index this as
   // a(irow, icol)
   
   struct Array {
   
       int _rows;
       int _cols;
       std::vector<double> _data;
   
       Array (int rows, int cols, double val=0.0)
           : _rows{rows},
             _cols{cols},
             _data(rows * cols, val)
       {
           // we do the asserts here after the initialization of _data
           // in the initialization list, but if the size is zero, we'll
           // abort here anyway.
   
           assert (rows > 0);
           assert (cols > 0);
   
       }
   
       // note the "const" after the argument list here -- this means
       // that this can be called on a const Array
   
       inline std::size_t ncols() const { return _cols;}
       inline std::size_t nrows() const { return _rows;}
   
       inline double& operator()(int row, int col) {
           assert (row >= 0 && row < _rows);
           assert (col >= 0 && col < _cols);
           return _data[row*_cols + col];
       }
   
       inline const double& operator()(int row, int col) const {
           assert (row >= 0 && row < _rows);
           assert (col >= 0 && col < _cols);
           return _data[row*_cols + col];
       }
   
       inline double sum() {
           return std::accumulate(_data.begin(), _data.end(), 0.0);
       }
   
       inline double min() {
           auto it = std::ranges::min_element(_data);
           return *it;
       }
   
       inline double max() {
           auto it = std::ranges::max_element(_data);
           return *it;
       }
   
   };
   
   // the << operator is not part of the of the class, so it is not a member
   
   inline
   std::ostream& operator<< (std::ostream& os, const Array& a) {
   
       for (std::size_t row = 0; row < a.nrows(); ++row) {
           for (std::size_t col = 0; col < a.ncols(); ++col) {
               os << std::format("{:6.2f} ", a(row, col));
           }
           os << std::endl;
       }
   
       return os;
   }
   
   #endif
   

   Here I chose to use the ranges and iterator algorithms, but you could have also written the loop (or loops) out explicitly.

   Now the driver.

   Listing 176 test_array.cpp

   #include <iostream>
   
   #include "array.H"
   
   int main() {
   
       Array a(5, 4);
   
       // there are a few ways we can initialize this we could just have
       // 20 lines where we use the () operator with the row, column
       // manually and set it to the value.  That would be fine.
   
       // a little nicer is something like this:
   
       std::vector<double> vals{-20.0, 4.5, 1.45, 7.9,
                                -1.2, -10.4, 8.9, 6.49,
                                12.7, 14.4, 6.5, -10.9,
                                -2.4, 2.15, 1.15, 20.4,
                                -22.5, 64.5, -1.8, -7.1};
   
       // and then we make use of the fact that _data is contiguous
       for (int i = 0; i < static_cast<int>(vals.size()); ++i) {
           a._data[i] = vals[i];
       }
   
       std::cout << "our array is: " << std::endl;
       std::cout << a << std::endl;
   
       std::cout << "sum of elements is " << a.sum() << std::endl;
   
       std::cout << "max element is " << a.max() << std::endl;
       std::cout << "min element is " << a.min() << std::endl;
   
   }
   

   There are a few ways to initialize the array. Here I create a vector (and just use newlines to make it look 2D) and then copy in. You could also just manually write out

   a(0, 0) = -20;
   a(0, 1) = 4.5;
   ...
   

   Tip

   An alternate way to do the initialization, is to create another constructor that takes a std::initializer_list and then copy from that.

   The constructor would look like:

   Array(std::initializer_list<std::initializer_list<double>> values)
       : _rows(values.size()),
         _cols(values.begin()->size()),
         _data()
   {
       assert(_rows > 0);
       for (const auto& row : values) {
           // Ensure all rows have the same number of columns
           assert(static_cast<int>(row.size()) == _cols);
           _data.insert(_data.end(), row.begin(), row.end());
       }
   }
   

   and the initialization would look like:

     Array a{{-20.0, 4.5, 1.45, 7.9},
             {-1.2, -10.4, 8.9, 6.49},
             {12.7, 14.4, 6.5, -10.9},
             {-2.4, 2.15, 1.15, 20.4},
             {-22.5, 64.5, -1.8, -7.1}};
   
   However, this is beyond what we covered in class.
   

2. In Function Practice, we wrote a function is_prime() took an int and returned a bool indicating whether the number was prime. Here’s the code we produced:

   Listing 177 primes.cpp

   #include <iostream>
   #include <cmath>
   
   bool is_prime(int N) {
   
       bool prime{true};
   
       int max_factor = static_cast<int>(std::sqrt(N));
   
       for (int q = 2; q <= max_factor; ++q) {
           if (N % q == 0) {
               prime = false;
               break;
           }
       }
   
       return prime;
   }
   
   int main() {
   
       const int n_max = 100;
   
       for (int n = 2; n <= n_max; ++n) {
           if (is_prime(n)) {
               std::cout << n << " is prime!" << std::endl;
           }
       }
   
   }
   

   Rewrite this example in python—your solution should include a python function named is_prime.

   solution

   Here’s the python version—it is pretty much a line-for-line conversion.

   Listing 178 primes.py

   import math
   
   
   def is_prime(N):
   
       prime = True
   
       max_factor = int(math.sqrt(N))
   
       for q in range(2, max_factor+1):
           if N % q == 0:
               prime = False
               break
   
       return prime
   
   N_MAX = 100
   
   for n in range(2, N_MAX+1):
       if is_prime(n):
           print(f"{n} is prime!")
   

3. In class, we write a python version of Trapezoid rule integration. Modify this to implement Simpson’s rule for integration (see our C++ version at High-order Integration: Simpson’s Rule).

   solution

   Here’s the python version. Notice when we use range we use a stride of 2.

   Listing 179 simpsons.py

   import math
   
   
   def simpsons(a, b, N, func):
       """Integrate function func(x) from a to b using N intervals of
       the Simpson's rule"""
   
       dx = (b - a) / N
   
       I = 0
       for n in range(0, N, 2):
           xl = a + dx * n
           xc = a + dx * (n+1)
           xr = a + dx * (n+2)
   
           fl = func(xl)
           fc = func(xc)
           fr = func(xr)
   
           I += dx / 3 * (fl + 4.0 * fc + fr)
   
       return I
   
   # test out our Simpson's rule
   a = 0.5
   b = 1.5
   
   I_exact = 1.0 - 1.0 / (2.0 * math.pi**2)
   
   for N in [2, 4, 8, 16, 32, 64, 128]:
       I = simpsons(a, b, N,
                    lambda x: 1.0 + 0.25 * x * math.sin(math.pi * x))
   
       err = abs(I - I_exact)
   
       print(f"{N:3} {I:7.5f} {err:9.6g}")
   

4. Write a python program that:

   • creates an empty list, angles

   • using a loop, adds the numbers \(n \pi / 8\) for \(n = 0, 1, \ldots 8\) to angles

   • creates a new list sines, and using a second loop, adds the sine of each angle in angles to our new list sines.

   • finally, outputs the results as (angle, sine) pairs, one pair per line.

   solution

   Here’s the code:

   Listing 180 angles.py

   import math
   
   angles = []
   for n in range(9):
       angles.append(math.pi * n / 8)
   
   sines = []
   for a in angles:
       sines.append(math.sin(a))
   
   for a, s in zip(angles, sines):
       print(f"{a:7.4f}: {s:7.4f}")
   
   

   Notice that I use zip() to loop over the two lists together (pairing like elements from each list in each loop iteration).

   You could also just loop with a range and index the two lists manually.