We explored an efficient solution to a novel problem today with a focus on runtime efficiency, saw an additional example of a backtracking problem, and discussed midterm exam logistics.
Contents
1. Crystal Etching Problem
2. River-Crossing Problem
3. Exam Logistics and Open Q&A
4. What's next?
5. Practice Exam Problems
Crystal Etching Problem
We started class today with the crystal etching problem and a challenge: Now that we've covered a big chunk of CS106B content, how could you solve this problem efficiently? What tool(s) do we have at our disposal that we wouldn't have had in CS106A? Can we do better than brute force? See attachment:
- etch.pdf - A write-up of the crystal etching problem from one of my former colleagues, Arup Guha.
We solved this problem by performing a binary search over a function parameter. The algorithm we used had an interesting twist compared to previous implementations of binary search that we've seen this semester: instead of integer values of hi and lo, which can be decremented or incremented (respectively) until they cross over, we used floating point values for hi, lo, and their midpoint. So, hi and lo kept getting closer and closer to one another over the course of execution of the program. For our terminating condition, we stopped when hi - lo was less than some tiny value, EPSILON.
We then briefly discussed the runtime for this solution, which was O(log(r/EPSILON)), where r is the full range of possible values for t -- in this case, 0 through 1,000,000.
(Important take-away!) Note that binary search only works for this because the right-hand side of the equation is increasing as t increases. If the function were not strictly increasing (i.e., if it oscillated up and down as t increased), then binary search would be useless to us. (Can you see why?)
Here is our final solution to the problem (although I went back and peppered it with some incantations that ensure we only print our results with two decimal places of precision):
#include <cmath> // for exp()
#include <iomanip> // for decimal precision
#include <iostream>
#include "console.h"
using namespace std;
#define EPSILON 0.000001
double solveForT(double f1, double f2, double a, double b, double c)
{
// Possible range for t values is defined in problem statement.
double lo = 0.0;
double hi = 1000000.0;
// We are attempting to solve for t. This will be our "mid."
double t;
// The left-hand side of the equation never changes, the RHS does.
double lhs = (f2 - f1) / (f2 * f1);
double rhs;
// With the way we adjust lhs and rhs, they'll never actually cross
// over, so our traditional looping condition (lo <= hi) is insufficient.
// Instead, we stop when they get sufficiently close to one another.
while (hi - lo > EPSILON)
{
// Find midpoint and new value for right-hand side of equation.
// Note that exp(k) raises e (Euler's number) to the power of k.
t = lo + (hi - lo) / 2.0;
rhs = a * t + b * (1.0 - exp(-1.0 * c * t));
// Since we're not dealing strictly with integers, we must use
// hi = t and lo = t below instead of hi = t - 1.0 and lo = 1 - 1.0
// to avoid potentially skipping over the solution.
if (lhs < rhs)
{
hi = t;
}
else if (lhs > rhs)
{
lo = t;
}
else
{
return t;
}
}
// We will have modified either lo or hi in our final iteration of the
// loop above, so we recalculate our mid before returning. By the way,
// Having this formula repeated in two different places in this function
// is a questionable life choice.
return lo + (hi - lo) / 2.0;
}
int main()
{
// Incantations to print only to the nearest hundredth.
cout << fixed;
cout << setprecision(2);
// Expected result (from PDF): 0.57
cout << solveForT(500.0, 1000.0, 0.001, 0.001, 1.0) << endl;
// Expected result (from PDF): 1.00
cout << solveForT(1000.0, 2000.0, 0.00025, 0.0005, 0.6931472) << endl;
return 0;
}
River-Crossing Problem
We then briefly covered the Farmer, Fox, Goose, and Bag of Beans problem, which is a classical backtracking problem that belongs to a broader class of river-crossing problems. See the Prezi below. Along the way, we discussed a few ideas for representing states and avoiding the generation of duplicate states. In particular, we discussed the idea of storing previously seen states in a Set to enable fast lookup of whether any given state had already been explored.
Exam Logistics and Open Q&A
We ended with a few notes about midterm exam logistics and an open Q&A about exam expectations. Be sure to thoroughly review all the information on the midterm exam page as you prepare for the exam, as I don't want you to encounter any surprises on Friday.
What's next?
We have no class tomorrow (Thursday), and your midterm exam is Friday. Best of luck with your preparations. The entire course staff is rooting for your success!
Practice Exam Problems
1. As an exercise, you could try coding a solution to the crystal etching problem from scratch. However, that problem won't make a direct appearance on the midterm exam. We covered it partly to gain additional exposure to the kind of creative problem solving that goes into the application of some of the material we've been learning this quarter, as well as to tackle a problem we can now solve that we wouldn't have been able to solve efficiently at the end of a class like CS106A.
2. Code up a function to solve the river crossing problem we went over today. Have it print the list of moves it finds that will get everyone safely across the river.