Contents
1. Crystal Etching Problem
2. [Prezi] A Chaotic Assortment of Notes and Reminders
3. What's next?
4. Exercises
Crystal Etching Problem
We started class today with the crystal etching problem and a challenge: Now that you've reached the end of 106B, 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;
}
[Prezi] A Chaotic Assortment of Notes and Reminders
Here's the Prezi I went through at the end of class with various announcements, reminders, and notes about some of the topics we've covered this quarter:
What's next?
On Friday, Julie, Clinton, and I will host an AMA where we'll field any questions you might have for us.
Your final exam is next Monday from 8:30 - 11:30 AM. For details, see: https://web.stanford.edu/class/cs106b/exams/2-endquarter/
Good luck with your final preparations, and thank you for working so hard and being so positive, supportive, and curious throughout the quarter!
Exercises
1. As an exercise, you could try coding a solution to the crystal etching problem from scratch. However, that problem won't make an appearance on the final exam. :) We covered that mostly for funsies, but also to tackle a problem we can solve now that we wouldn't have been able to solve efficiently at the end of CS106A.