Twitter
Facebook
Flickr
RSSI like to look at CS 170 as one exponentially large graph search problem.
We have a plethora of information given to us to guide our way (as a
search heuristic) to the goal node, which is achieving algorithmic zen. In
the end, we should eat, sleep, and breathe big O notation. We should
cringe at exponentials of any form. Our hearts should skip a beat when we
read the words "constant time", yet remain brave when staring down an
NP-hard problem. We should be so lucky to have committed to memory all
algorithms we've learned, yet never assume that our machines can commit
much to memory at all. Once you have reached this land, you are in the
enlightened world of efficiency, problem solving, and babes. Well, maybe
not the last part, but you'll still be really, really cool in my books.
Now, assuming that we began at the same start node of basic 61b algorithm
knowledge, we want to find this path to our shangri-la in as short a time
as possible. If not solely because we are excited to get there, then at
least because you'll do well on tests if you achieve enlightenment
faster. Given these requirements, what better method than to call upon
the prophet Dijkstra who has graced us with his algorithm? Hence, we
must follow the path of Dijkstra through this land of unintelligible
mathematics and weird newsgroup posts at 3 am on a Saturday. Now, I
cannot give you his specific commandments, as any man delivering
commandments has to have a sweet beard. I do not have a
sweet beard, though not for lack of trying, and thus I can only provide
my worldly wisdom as to the way of Dijkstra.
The most important secret to this course is the practice of writing
and analyzing algorithms. As any good kung-fu movie shows us, you need
to have a painful training montage if you are to achieve your goal.
Though, since we are only beginners, we must learn proof techniques from
the masters Rao and Papadimitrou. In the chapter, the problem at hand is
always presented first, and then the algorithm is given. You never
get to experience the frustration and thought put into discovering what
is presented. As an example, have you ever seen master Sinclair smile?
No, for he is tortured by the demons he must wrestle. To really get a
grasp of this learning process, try to write your own algorithm before it
is presented to you in the book. Yes, your answer is nowhere near as good
Papadimitrou's, but you can now compare the approach of an apprentice
to that of a master. To know where you are headed, you must know where
you came from and where you are.
In that vein, approach your homework as if it were a baby lion. It is
relatively small and beautiful creature, yet it grows to be a dangerous
beast that will eat your entrails if not tamed. Come prepared with reams
of paper and sit in your favorite library for at least 3 hours attacking
the problems by yourself. During this time, you must try every possible
sneaky way of snatching the solutions from the jaws of ignorance. Do not
rush, do not cry, do not leave your seat, just write. If the answer does
not come to you immediately, write a slow inefficient answer. You can
always recycle the paper later. Thomas Edison was famous claiming "I
have not failed. I've just found 10,000 ways that don't work." He
was an amateur. You should have at least O(100!) ways that don't work
efficiently.
If one of your many explorations of this solution space
does not grant you the solution master Rao seeks, then you must go to
the hours of the office. Though our professors and GSI's do their best
to schedule them at the same time as our classes, this is only done to
to ward off the freeloading answer seekers who are not pure in their
persuit of algorithmic zen. Fret not, for they will meet a negative
cycle in the graph of life from which they will never escape. It is
here that you may ask for guidance AND ONLY GUIDANCE to the one true
solution.
When you have reached the coveted solution you will realize the
reward of algorithmic glory. Do not worry if your perspiration
increases along with your heart rate, this is normal. You will quake
with excitement as your pen graciously rounds the curves of a paren,
and stabs sharply with the joint of a sigma. It is this feeling that
keeps us going forward. For you not only know the answer, but you
know the dangerous turns to avoid, having taken them yourself.
May your base cases always be defined,
May your code always elude perplexity,
May your run times always be confined
to the lowest asymptotic complexity.
http://groups.google.com/group/ucb.class.cs170/browse_thread/thread/1f2cc705af705560?pli=1
