1
// Overload operator< for class Rectangle such that r < s if and only if the area of r is less than that of s.
2

3
#include <iostream>
4

5
class Rectangle
6
{
7
public:
8
    // fields
9
    int xLow;
10
    int yLow;
11
    int height;
12
    int width;
13

14
    // methods
15
    Rectangle(int xLow = 0, int yLow = 0, int height = 0, int width = 0) : xLow(xLow), yLow(yLow), height(height), width(width) {}
16
    ~Rectangle() {}
17
    int Area() const;
18
    bool operator<(const Rectangle &s);
19
};
20

21
int Rectangle::Area() const
22
{
23
    return height * width;
24
}
25

26
bool Rectangle::operator<(const Rectangle &s)
27
{
28
    return (this->Area()) < (s.Area());
29
}
30

31
int main()
32
{
33
    std::cout << "An example of overload < for Rectangle:" << std::endl;
34
    // >
35
    std::cout << "a(0, 0, 10, 20), b(0, 0, 11, 20)" << std::endl;
36
    Rectangle a(0, 0, 10, 20), b(0, 0, 11, 20);
37
    std::cout << "result: " << bool(a < b) << std::endl;
38
    // ==
39
    std::cout << "e(0, 0, 10, 20), f(0, 0, 10, 20)" << std::endl;
40
    Rectangle e(0, 0, 10, 20), f(0, 0, 10, 20);
41
    std::cout << "result: " << bool(e < f) << std::endl;
42
    // <
43
    std::cout << "c(0, 0, 10, 20), d(0, 0, 9, 20)" << std::endl;
44
    Rectangle c(0, 0, 10, 20), d(0, 0, 9, 20);
45
    std::cout << "result: " << bool(c < d) << std::endl;
46
}

1
// If a = (a_0, ..., a_{n-1}) and b = (b_0, ..., b_{m-1}) are ordered lists,
2
//  then a < b if:
3
//      a_i = b_i for 0 <= i < j and a_j < b_j,
4
//      or, if a_i = b_i for 0 <= i < n and n < m.
5
// Write a function that returns -1, 0, or +1, depending upon whether a < b, a = b, or a > b.
6
// Assume that the a_is and b_js are integer.
7

8
#include <iostream>
9
#include <algorithm>
10
#include <vector>
11

12
int compare_lists(const std::vector<int> &a, const std::vector<int> &b)
13
{
14
    size_t n = a.size();
15
    size_t m = b.size();
16

17
    size_t min_len = std::min(n, m);
18

19
    for (size_t i = 0; i < min_len; i++)
20
    {
21
        if (a[i] < b[i])
22
        {
23
            return -1;
24
        }
25
        else if (a[i] > b[i])
26
        {
27
            return 1;
28
        }
29
    }
30

31
    // all elements up to min_len are equal
32
    // compare length
33
    if (n < m)
34
    {
35
        return -1;
36
    }
37
    else if (n > m)
38
    {
39
        return 1;
40
    }
41
    else
42
    {
43
        return 0;
44
    }
45
}
46

47
void print_vector(const std::vector<int> &a)
48
{
49
    for (int e : a)
50
    {
51
        std::cout << e << " ";
52
    }
53
    std::cout << "\n";
54
}
55

56
int main()
57
{
58
    std::cout << "Verify function:" << std::endl;
59
    std::vector<int> a, b;
60
    for (int i = 0; i < 10; i++)
61
    {
62
        a.push_back(i);
63
    }
64
    for (int i = 0; i < 11; i++)
65
    {
66
        b.push_back(i);
67
    }
68

69
    // -1
70
    std::cout << "a: ";
71
    print_vector(a);
72

73
    std::cout << "b: ";
74
    print_vector(b);
75
    std::cout << "compare result: " << compare_lists(a, b) << std::endl;
76

77
    // 1
78
    a.push_back(10);
79
    a.push_back(11);
80
    std::cout << "a: ";
81
    print_vector(a);
82

83
    std::cout << "b: ";
84
    print_vector(b);
85
    std::cout << "compare result: " << compare_lists(a, b) << std::endl;
86

87
    // 0
88
    std::cout << "a: ";
89
    print_vector(a);
90

91
    b.push_back(11);
92
    std::cout << "b: ";
93
    print_vector(b);
94
    std::cout << "compare result: " << compare_lists(a, b) << std::endl;
95
    return 0;
96
}

1
// Modify function Add so that it reduces the size of c.termArray to c.terms prior to termination.
2
// With this modification, can we dispense with the data member capacity?
3

4
#include <iostream>
5

6
class Polynomial;
7
class Term
8
{
9
    friend Polynomial;
10

11
private:
12
    float coef; // coefficient
13
    int exp;    // exponent
14
};
15

16
class Polynomial
17
{
18
    // p(x) = a_0*x^{e_0} + ... + a_n*x^{e_n}; a set of ordered pairs of <e_i, a_i>,
19
    // where a_i is a nonzero float coefficient and e_i is a non-negative integer exponent.
20
public:
21
    Polynomial() : termArray(nullptr), terms(0) {} // Construct the polynomial p(x) = 0.
22
    ~Polynomial() { delete[] termArray; }
23
    Polynomial Add(Polynomial poly); // Return the sum of the polynomials *this and poly.
24
    void NewTerm(const float theCoeff, const int theExp);
25

26
private:
27
    Term *termArray; // array of nonzero terms
28
    // int capacity;    // size of termArray, we can delete it
29
    int terms; // number of nonzero terms
30
};
31

32
void Polynomial::NewTerm(const float theCoeff, const int theExp)
33
// Add a new term to the end of termArray
34
{
35
    Term *temp = new Term[terms + 1]; // new array, don't double the capacity
36
    if (termArray)
37
    {
38
        std::copy(termArray, termArray + terms, temp);
39
        delete[] termArray; // deallocate old memory
40
    }
41
    termArray = temp;
42

43
    termArray[terms].coef = theCoeff;
44
    termArray[terms++].exp = theExp;
45
}
46

47
Polynomial Polynomial::Add(Polynomial b)
48
{ // Return the sum of the polynomials *this and b.
49
    Polynomial c;
50
    int aPos = 0, bPos = 0;
51
    while ((aPos < terms) && (bPos < b.terms))
52
    {
53
        if (termArray[aPos].exp == b.termArray[bPos].exp)
54
        {
55
            float t = termArray[aPos].coef + b.termArray[bPos].coef;
56
            if (t)
57
                c.NewTerm(t, termArray[aPos].exp);
58
            aPos++;
59
            bPos++;
60
        }
61
        else if (termArray[aPos].exp < b.termArray[bPos].exp)
62
        {
63
            c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
64
            bPos++;
65
        }
66
        else
67
        {
68
            c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
69
            aPos++;
70
        }
71
    }
72

73
    // add in remaining terms of *this
74
    for (; aPos < terms; aPos++)
75
    {
76
        c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
77
    }
78
    // add in remaining terms of b(x)
79
    for (; bPos < b.terms; bPos++)
80
    {
81
        c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
82
    }
83
    return c;
84
}
85

86
int main()
87
{
88
    return 0;
89
}

1
// Write a C++ function that multiplies two polynomials represented as in this section.
2
// What is the computing time of your function?
3

4
#include <iostream>
5

6
class Polynomial;
7
class Term
8
{
9
    friend Polynomial;
10

11
private:
12
    float coef; // coefficient
13
    int exp;    // exponent
14
};
15

16
class Polynomial
17
{
18
public:
19
    Polynomial() : termArray(nullptr), terms(0) {}
20
    ~Polynomial() { delete[] termArray; }
21
    void NewTerm(const float theCoeff, const int theExp);
22
    Polynomial Multiply(Polynomial b); // New multiplication function
23

24
private:
25
    Term *termArray;
26
    int terms;
27
};
28

29
void Polynomial::NewTerm(const float theCoeff, const int theExp)
30
{
31
    Term *temp = new Term[terms + 1];
32
    if (termArray)
33
    {
34
        std::copy(termArray, termArray + terms, temp);
35
        delete[] termArray;
36
    }
37
    termArray = temp;
38
    termArray[terms].coef = theCoeff;
39
    termArray[terms++].exp = theExp;
40
}
41

42
Polynomial Polynomial::Multiply(Polynomial b)
43
{
44
    Polynomial c;
45

46
    // Multiply each term of first polynomial with each term of second polynomial
47
    for (int i = 0; i < terms; i++)
48
    {
49
        for (int j = 0; j < b.terms; j++)
50
        {
51
            // Calculate new coefficient and exponent
52
            float newCoef = termArray[i].coef * b.termArray[j].coef;
53
            int newExp = termArray[i].exp + b.termArray[j].exp;
54

55
            // Search if this exponent already exists in result
56
            bool found = false;
57
            for (int k = 0; k < c.terms; k++)
58
            {
59
                if (c.termArray[k].exp == newExp)
60
                {
61
                    // Add to existing term
62
                    c.termArray[k].coef += newCoef;
63
                    found = true;
64
                    break;
65
                }
66
            }
67

68
            // If exponent wasn't found, add new term
69
            if (!found && newCoef != 0)
70
            {
71
                c.NewTerm(newCoef, newExp);
72
            }
73
        }
74
    }
75
    return c;
76
}
77

78
int main()
79
{
80
    return 0;
81
}

1
// Write a C++ functions to input and output a sparse martrix.
2
//     These should be implemented by overloading the >> and << operators.
3
//     You should design the input and output formats.
4
// However, the internal representation should be a one dimensional array of nonzero terms as used in this section.
5
// Analyze the computing time of your functions.
6

7
#include <iostream>
8
#include <iomanip>
9

10
class SparseMatrix;
11
class MatrixTerm
12
{
13
    friend SparseMatrix;
14
    friend std::ostream &operator<<(std::ostream &os, const SparseMatrix &matrix);
15
    friend std::istream &operator>>(std::istream &is, SparseMatrix &matrix);
16

17
private:
18
    int row, col, value;
19
};
20

21
// A set of triples, <row, column, value>, where row and column are non-negative
22
//  integers and form a unique combination; value is also an integer.
23
class SparseMatrix
24
{
25
    friend std::ostream &operator<<(std::ostream &os, const SparseMatrix &matrix);
26
    friend std::istream &operator>>(std::istream &is, SparseMatrix &matrix);
27

28
public:
29
    // The constructor function creates a SparseMatrix with
30
    //  r rows, c columns, and a capacity of t nonzero terms.
31
    SparseMatrix(int r, int c, int t) : rows(r), cols(c), terms(0), capacity(t)
32
    {
33
        if (r < 0 || c < 0 || t < 0)
34
            throw std::invalid_argument("Negative dimensions or capacity");
35
        smArray = new MatrixTerm[capacity];
36
    }
37
    ~SparseMatrix()
38
    {
39
        delete[] smArray;
40
    }
41

42
private:
43
    int rows, cols, terms, capacity;
44
    MatrixTerm *smArray;
45
};
46

47
// Input operator overloading
48
std::istream &operator>>(std::istream &is, SparseMatrix &matrix)
49
{
50
    std::cout << "Enter the number of non-zero terms: ";
51
    is >> matrix.terms;
52
    if (matrix.terms > matrix.capacity)
53
    {
54
        throw std::overflow_error("Number of terms exceeds matrix capacity");
55
    }
56

57
    std::cout << "Enter each term as row, column value (separate by space):" << std::endl;
58
    for (int i = 0; i < matrix.terms; i++)
59
    {
60
        is >> matrix.smArray[i].row >> matrix.smArray[i].col >> matrix.smArray[i].value;
61
    }
62
    return is;
63
}
64

65
// Output operator overloading
66
std::ostream &operator<<(std::ostream &os, const SparseMatrix &matrix)
67
{
68
    int current_term = 0;
69
    for (int i = 0; i < matrix.rows; i++)
70
    {
71
        for (int j = 0; j < matrix.cols; j++)
72
        {
73
            if (current_term < matrix.terms &&
74
                matrix.smArray[current_term].row == i &&
75
                matrix.smArray[current_term].col == j)
76
            {
77
                os << std::setw(4) << matrix.smArray[current_term++].value;
78
            }
79
            else
80
            {
81
                os << std::setw(4) << 0;
82
            }
83
        }
84
        os << std::endl;
85
    }
86
    return os;
87
}
88
int main()
89
{
90
    try
91
    {
92
        int r, c, t;
93
        std::cout << "enter the rows, columns, and capacity of non-zero terms r, c, t:" << std::endl;
94
        std::cin >> r >> c >> t;
95
        SparseMatrix sm(r, c, t);
96
        std::cin >> sm;
97

98
        std::cout << "\nThe sparse matrix is:" << std::endl;
99
        std::cout << sm;
100
    }
101
    catch (const std::exception &e)
102
    {
103
        std::cerr << "Error: " << e.what() << std::endl;
104
        return 1;
105
    }
106

107
    return 0;
108
}

1
// If x = (x_0, ..., x_{m-1}) and y = (y_0, ..., y_{n-1}) are strings,
2
//  where x_i and y_i are letters of the alphabet, then
3
//  x is less then y if x_i = y_i for 0 <= i < j and x_j < y_j
4
//  or if x_i = y_i for 0 <= i <= m and m < n.
5
// Write an algorithm that takes two strings x, y and returns either -1, 0, or +1 if x < y, x = y, or x > y repectively.
6

7
#include <string>
8

9
int compareStrings(const std::string &x, const std::string &y)
10
{
11
    // Get the lengths of both strings
12
    int m = x.length();
13
    int n = y.length();
14

15
    // Find the minimum length between the two strings
16
    int minLength = std::min(m, n);
17

18
    // Compare characters until we find a difference or reach the end of a string
19
    for (int i = 0; i < minLength; i++)
20
    {
21
        if (x[i] < y[i])
22
        {
23
            return -1; // x is less than y
24
        }
25
        if (x[i] > y[i])
26
        {
27
            return 1; // x is greater than y
28
        }
29
    }
30

31
    // All characters up to minlength are equal
32
    // Now check the length
33
    if (m < n)
34
        return -1;
35
    if (m > n)
36
        return 1;
37
    return 0; // exactly equal
38
}
39

40
int main()
41
{
42
    return 0;
43
}

1
// Compute the failure function for each of the following patterns:
2
//  (a) a a a b
3
//  (b) a b a b a a
4
//  (c) a b a a b a a b b
5

6
#include <iostream>
7
#include <string>
8
#include <vector>
9

10
std::vector<int> build_failure_function(std::string &t)
11
{
12
    std::vector<int> F(t.size());
13
    F[0] = -1;
14

15
    for (int i = 1, pos = -1; i < t.size(); i++)
16
    {
17
        while (~pos && t[i] != t[pos + 1])
18
            pos = F[pos];
19

20
        if (t[i] == t[pos + 1])
21
            pos++;
22

23
        F[i] = pos;
24
    }
25
    return F;
26
}
27

28
int main()
29
{
30
    std::cout << "failure function of a: " << std::endl;
31
    std::string str_a = "aaaab";
32
    std::vector<int> a = build_failure_function(str_a);
33
    for (int e : a)
34
    {
35
        std::cout << e << " ";
36
    }
37
    std::cout << std::endl;
38

39
    std::cout << "failure function of b: " << std::endl;
40
    std::string str_b = "ababaa";
41
    std::vector<int> b = build_failure_function(str_b);
42
    for (int e : b)
43
    {
44
        std::cout << e << " ";
45
    }
46
    std::cout << std::endl;
47

48
    std::cout << "failure function of c: " << std::endl;
49
    std::string str_c = "abaabaabb";
50
    std::vector<int> c = build_failure_function(str_c);
51
    for (int e : c)
52
    {
53
        std::cout << e << " ";
54
    }
55
    std::cout << std::endl;
56
    return 0;
57
}