| CS 311 Fall 2007 > Midterm Exam Review Problems, Part 2 |
This is the second of three sets of review problems for the midterm exam. For all three sets, see the class web page, or the following links:
Review problems are given below. Answers are in the Answers section of this document. Do not turn these in.
Function div should divide a by b and return the result. If this is impossible, because b is zero, it should throw an exception of type std::overflow_error, with an appropriate message string. Include relevant comments, preconditions, and postconditions. You may assume that all relevant standard header files have been included, but that no using statements have been executed.double div(double a, double b);
Or we can do the same thing with std::advance.myIter += howFar;
Why is std::advance often preferable?std::advance(myIter, howFar);
template <typename FDIter>
void recursiveSelectionSort(FDIter first, FDIter last)
{
// BASE CASE
// Empty list? Done.
if (first == last)
return;
// RECURSIVE CASE
// Find minimum item
FDIter minItem = std::min_element(first, last);
// Put it at the beginning
std::iter_swap(first, minItem);
// Find iterator to item after first
FDIter afterFirst = first;
++afterFirst;
// And recurse
recursiveSelectionSort(afterFirst, last);
}// Dereferencing a valid Iterator must return an int
template<typename Iterator>
int sum_cubes(Iterator first, Iterator last)
{
int sum = 0;
for (Iterator iter = first; iter != last; ++iter)
{
int cube = 1;
for (int i = 0; i < 3; ++i)
cube *= *iter;
sum += cube;
}
return sum;
}void f2(int arr[], int n) // n is the length of arr
{
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n-1; ++j)
{
for int (k = 0; k < 10; ++k)
{
for int (m = 2; m < j+1; ++m)
{
cout << arr[m] << endl;
}
}
}
}
}// div
// Divides its parameters and returns the result: a/b.
// Pre: None.
// Post:
// Return value == a/b
// Throws std::overflow_error if b == 0.
double div(double a, double b)
{
if (b == 0.)
throw std::overflow_error("Division by zero");
// Must #include <stdexcept>
return a/b;
}// Must have #include'd <stdexcept> and <iostream>
bool allocSucceeded; // true if alloc succeeds
try
{
int * myArray = new int[10];
allocSucceeded = true;
}
catch (std::bad_alloc & e)
{
allocSucceeded = false;
std::cout << "Could not allocate" << std::endl;
}// Must have #include'd <stdexcept> and <iostream>
bool allocSucceeded = true; // set to false if alloc fails
try
{
int * myArray = new int[10];
}
catch (...)
{
allocSucceeded = false;
std::cout << "Could not allocate" << std::endl;
}// lucas1
// Given n, returns L(n) (the nth Lucas number).
// L(0) = 2. L(1) = 1. For n >= 2, L(n) = L(n-2) + L(n-1).
// Recursive.
// Pre:
// n >= 0.
// L(n) is a valid int value.
// Post:
// Return value is L(n).
// Does not throw
int lucas1(int n)
{
// Base case
if (n <= 1)
return 2 - n;
// Recursive case
return lucas1(n-2) + lucas1(n-1);
}// lucas2
// Given n, returns L(n) (the nth Lucas number).
// L(0) = 2. L(1) = 1. For n >= 2, L(n) = L(n-2) + L(n-1).
// Pre:
// n >= 0.
// L(n) is a valid int value.
// Post:
// Return value is L(n).
// Does not throw
int lucas2(int n)
{
int luc1 = -1; // Previous Lucas number [L(-1) = -1]
int luc2 = 2; // Current Lucas number
for (int i = 0; i < n; ++i)
{
// Invariants:
// luc1 == L(i-1)
// luc2 == L(i)
int next = luc1 + luc2;
luc1 = luc2;
luc2 = next;
}
return luc2;
}template <typename FDIter>
void recursiveSelectionSort(FDIter first, FDIter last)
{
while (true)
{
// BASE CASE
// Empty list? Done.
if (first == last)
return;
// RECURSIVE CASE
// Find minimum item
FDIter minItem = std::min_element(first, last);
// Put it at the beginning
std::iter_swap(first, minItem);
// Find iterator to item after first
FDIter afterFirst = first;
++afterFirst;
// And recurse
//recursiveSelectionSort(afterFirst, last);
first = afterFirst;
}
}template <typename FDIter>
void recursiveSelectionSort(FDIter first, FDIter last)
{
while (true)
{
// Empty list? Done.
if (first == last)
return;
// Find minimum item
FDIter minItem = std::min_element(first, last);
// Put it at the beginning
std::iter_swap(first, minItem);
// Find iterator to item after first
++first;
}
}Thus, mathematical induction is the primary form of proof used to verify facts (e.g., correctness, efficiency) about recursive algorithms and code.
Note: Making k large does not hurt anything. We could just as well have used k = 100 or 1000000. However, k must be greater than 15.
| CS 311 Fall 2007: Midterm Exam Review Problems, Part 2 / Updated: 21 Oct 2007 / Glenn G. Chappell / ffggc@uaf.edu |
|