CLRS: First Exercises
09/23/14
So, I've made a tiny, tiny amount of time to read some CLRS. I got to the first, very simple exercises and haven't opened it since then.
I want to do all the exercises in CLRS.
All of them.
Now, it would be much faster to just read through CLRS, and I'd probably get a lot out of it, and either way I'm not using the book as it's expected to be used.
CLRS is not meant to be read cover-to-cover. It's reference material. Pick a chapter of specific interest, and read that chapter start-to-end, maybe.
Though, after reading up to the first exercises, I think maybe I shouldn't read it cover-to-cover.... I think I should skip to the exercises and refer to the text only when necessary.
Yeah!
Anyways, the problems:
1.1-1: Give a real-world example that requires sorting or a real-world example that requires computing a convex hull.
Real-world sorting:
- library-books
- person line-up (by alphabetical order)
- timing of (historical) events
- Order of operations
- Representations of data (plots and graphs)
Real-world... convex hull? Wassat again?
Rereading.... Hmmm... they might not have defined it yet. Checking index.... Oh, yep, there it is, defined in an example problem given.
The convex hull is the smallest convex polygon containing n points in a plane.
Real-world convex hull:
- ....
You know, I have no idea.
Another good link on real-world uses.
Some ones I found particularly interesting:
- Ideal mixing of two liquids based on various reasons
- Collision-detection
- GIS data
1.1-2: Other than speed, what other measures of efficiency might one use in a real-world setting?
- Memory
- Power
- Correctness
1.1-3: Select a dataset you've seen previously, and discuss its strengths and limitations.
Binary search trees. I suppose they're kinda like a jack of all trades, if you think about it. They don't do anything in constant time as far as I know, but they do most everything in in log(n) time, which is pretty close until n gets really large.
Answering this question is making me think I don't think about this as much as I should.
1.1-4: How are the shortest-path and traveling-salesman problem [...] similar? How are they different?
Both problems are trying to minimize distance-travelled while still reaching their goals. The shortest route problem has multiple potential paths to one goal, while the travelling salesmen problem has multiple goals that can be visiting in various orders.
1.1-5: Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is "approximately" the best is good enough.
This is taking me a lot longer than I think it should....
Approximity good enough: stock-market portfolio.
Best solution necesary.... This is a "you're right or you're wrong" sort of problem. Hmmmm.... Phone number look up?
Let's go with phone number look up. (I'm must be trying too hard, this can't be very difficult to come up with answers to....).
First set of problems done! Actually had me thinking, which I feel shouldn't be happening so soon.... Oh, well, hopefully it means I'm learning.