MIT Course 6.006: Introduction to Algorithms

What I did:

I successfully completed all the readings, lectures, homework assignments, and projects for MIT’s Introduction to Algorithms (the fall 2011 version of 6.006) course. I’ve included examples and brief explanations of my work below to give an idea of the types of things I’ve learned. All of my programming work and my final solutions to the homework assignments can be found on my GitHub.

I’ve included some examples of my work below:

Code I wrote for content aware resizing of images. The basic idea here is you can resize images without cropping or losing content. The code shows my bottom-up dynamic programing implementation of deciding which seam (vertical path from the bottom to the top, example shown in red), would be the least noticeable if removed.

original image

image being resized via my algorithm

resized image

This program uses data from the National Highway Planning Network to find the shortest path from a source to a destination in the form of driving directions. This is similar to how Google Maps and other navigation software products work. Here is the code I wrote to implement Dijkstra’s algorithm, which performs the search and returns the results very quickly, as one must sort though a large amount of data to find the shortest path for a cross country trip.

Here I implemented interval subsequence hashing using a modified python dictionary I wrote to quickly compare DNA sequences (represented as series of letters). Included are my results, comparing the DNA sequences of two humans, a human and a chimp, and a human and a dog.

I dramatically improved the speed of image decryption software written for a theoretical extreme multi-core chip that is limited to only performing arithmetic operations on 8-bit or 16-bit unsigned integers. I’ve shown my straight forward arithmetic operations which perform better than that prewritten asymptotically efficient algorithms when inputs are 64 digits or less. I’ve also included an example of the type of extremely sensitive data that can be decrypted using this technology.

This is my implementation of a bidirectional search which provides the fastest (smallest number of moves) solution to an arbitrarily arranged 2×2 Rubik’s Cube (pocket cube) in <5 seconds.

This is a selected example of the written portion of a problem set, and my (neatly typed up) solutions. Although it is much easier to show and understand the value of some of the software projects I worked on in this course, it’s important to demonstrate that 6.006 is a very theory heavy course, and foundational understanding is emphasized much more than practical programming skills. I enjoy theory and figuring out creative proofs to (seemingly) difficult problems was one of my favorite parts of this course.

Here is a theory heavy problem that I found to be particularly difficult. The problem assumes that you are a newly hired employee at a competitor of Facebook and asks for an algorithm for suggesting potential friends. More specifically it requests that the algorithm find the strength (computed as the product of all edge-ranks, within users that are less than k degrees of separation apart), between a given user s and every other user v to whom s is connected, in O(kE+V) time (this is a graph theory problem). This solution required the creativity to recognize that maximizing a sum (the strength) of a product (the edge ranks) is equivalent to minimizing the sum over the log of 1/(the product). This converts the problem to be a shortest path problem for all paths shorter than k in length.

What I just described is technical, but the reason I chose this problem is to demonstrate that this MIT course teaches students to think creatively and challenges students to think outside of the box. A cookie cutter application of an algorithm from our algorithms textbook doesn’t suffice. The course teaches more about how to reframe real world problems so we can map them to previously solved problems and apply the solutions, which I believe is the most valuable skill one can learn in almost any domain.

This is another example of a proof that I found to be particularly valuable, but also built on the most important skill of this course, reframing problems and modifying solutions so you can use resources of previously solved problems (in this field these are called algorithms) and apply them to novel problems. In this particular problem I am writing pseudocode to develop more basic arithmetic operations for the theoretical chip from the image decryption problem.

How I did it:

Before I analyze what I did, I’ll give a raw explanation of what I actually did. I completed this MIT Course in my free time by using an evolving version of the learning method I developed and found success with in college. The method breaks learning a college course into three phases, which are listed below, along with the actions I took to complete those phases.

  • Coverage (5%)
    • I listened to all the lectures at 3x speed, speed read the assigned reading (chapters of the textbook and additional reading assignments) for the course (in <5 hours) (here is how I did it). The purpose of this section is to see the forest before I start investigating individual trees. The entire course material is covered up front for multiple reasons. First, because textbooks are used primarily as (incredibly valuable) reference tools, and it is much easier to find what you’re searching for if you’ve seen it before, even if you didn’t realize what you were initially looking at. Covering the course in full without any deep dives emphasizes the scope of the course more than the details. When learning anything it’s important to understand what’s actually important so it can receive the appropriate attention. If I stopped when I struggled to understand each algorithm (the majority of the readings and lectures), I may have wasted hours memorizing them, but after completing my coverage phase and standing back from the course I realized that the purpose was not to teach us specific algorithms, but to teach us how to reframe problems so that we can use algorithms that others before us have developed. This clarity helps me focus on the important details of the course instead of all of them, ensuring that my time is spent more effectively. Also, reading and listening are forms of passive learning, which can only take you so far. My experiences have convinced me that real skill building, deep understanding, and internalization comes from active learning (phases 2 and 3). Since I find passive learning to be somewhat shallow, but still helpful in the initial phases, I feel that it is important to give it a sense of closure early so I don’t waste extra hours rereading paragraphs and re-listening to lectures because I don’t feel I fully “understand” them. The truth is I can only gain a false sense of understanding, (which is more dangerous than knowing you don’t know) from anything other than the actual application of the knowledge. Instead I quickly move through this section, capping the time, with the expectation that I will understand almost nothing, but that the exercise will give me a sense of what’s out there, what I haven’t learned yet, and what I can expect to gain a deeper understanding of through my active, intensive, next phase.
  • Practice (80%)
    • I completed every problem set and project sequentially using my adaptive set method. I wrote down every problem set number on a different line of a piece of paper (my mega adaptive set), and beside each problem set number I wrote down the number of each problem on the associated problem set.

      my mega adaptive set

      I started on the first problem set, attempting each problem and subproblem individually and discretely to the best of my ability, and providing a falsifiable answer, which I then immediately compared to the official course solutions. If my solution was correct I crossed the problem number off my mega adaptive set, and neatly wrote up my solution to be used as an “official solution”. If my solution was incorrect I circled the problem on my mega adaptive set, compared my attempted solution with the official solution line-by-line, identifying where exactly I went wrong, correcting my mistakes, and completing my incorrect solution using the official solution as a guide. Then I threw away my corrected, attempted solution, and moved on to the next problem on my set. Once I reach the end of the problem set (I call each of these a run-through) I circle the problem set number if there are circled problems remaining on the problem set. I then attempt another run-though of the problem set, where I repeat the process described above, but only for the circled problems. It is important to note that I do not attempt a circled problem within 24 hours of circling (unsuccessfully attempting) it. This is to ensure that solutions are not memorized and that I’ve actually learned the important concepts and tools necessary for solving the problem. Once all the problems have been crossed off a certain problem set, I cross of the problem set number and move on to the next one. Since this is an algorithms course, I thought it would be fun to rewrite my practice set method in algorithm form.

  • Synthesis (15%)
    • I identified (in this case singular) the most important core principle underlying the content of the course. This principle is as follows; To solve a non-trivial problem, reframe it such that it resembles a previously solved or trivial problem (although this reframing is typically non-trivial), and apply the known solution. I believe that statement, an algorithm resource (the course textbook or the internet), and practice solving problems using the stated method forms a basis for this course.
    • I went through my coursework and selected the solutions and projects I felt were most representative of what I accomplished and what I learned throughout the course. I paired these solutions with brief descriptions, so readers of all technical backgrounds can very quickly gain an insight into what I actually did. I believe it is important to show your work in a way such that it is beneficial to you. An A on a transcript can only communicate one point of information. It is important to take ownership of your work so that it takes it from something you did for a course, to something you made and can be proud of. This creates a virtuous cycle, because knowing you want something to display, whether as a selected project on your resumé, an item in your portfolio, or as a part of an article on your learning blog ;), motivates you to make something special, something you can be proud of. This nicely presented work helps you feel better about your work, and the experience with your learning project, which motivates you to do more, build more, and make more presentable and interesting projects in the future. I am in the process of learning this first hand, despite preaching about the importance of showing your work so that you can take credit and benefit from it for the past few years. The selected projects on this page are more visual and understandable than on my last course write-up, which was a major step up from me completely skipping this phase on my last two MIT courses. During a recent job search I had official offers for Software Development positions extended to me because of my last synthesis article, and how it showed my knowledge of the field, my learning methods, and my ambition. I did not expect my last article to help me get a job. If I did, I would have sent it to potential employers. Instead I just left a link to my blog on my resumé because I believe it is an important part of my personality, and hiring managers later told me how my Graduate Unschool articles strongly influenced their decisions to extend offers to me. I’m not writing these to get a special job, or prove anything to anyone else, I’m writing these synthesis articles to complete my learning process. Everything else is a free bonus for showing my work in public.
    • The purpose of the synthesis phase is to teach the material of the course in a way that is helpful and more concise than the original course material. This is how knowledge progresses, somebody learns something, then represents it publicly in a way that is easier to understand. Imagine how long it would take to complete a simple high school math test if you had to derive everything from fundamental axioms. Imagine if every time you wanted to use a computer you had to invent it from scratch without any sort of guide. When Newton talks about standing on the shoulders of giants this is what he means. Our ancestors built the intellectual world around us though absorbing, mastering, and representing knowledge in a form that is easier/faster to learn. Your duty is to do the same. You don’t need to discover a useful math theorem or invent a piece of technology to be a part of this process, all you need to do is learn something, synthesize it, and make your synthesis publicly available. Read a book and share what you learned from it, write a how to article on something you can do whether it’s simple or complicated, help those that you know and those that you will never meet learn what you know faster than you did. That’s the real secret to accelerated learning, we can all accelerate each other’s learning.

What I learned about learning:

  • If you have two goals, it is simpler and faster to complete them sequentially and discretely, rather than simultaneously
  • This learning method applies to the application of this learning method.
    • Right now I recognize that the synthesis phase is a major weakness for me, but re-covering my old synthesis section notes, practicing writing the last two articles, and showing others how to write a synthesis article is helping me evolve the synthesis phase, as well as improving my skills at it.
  • It makes sense to pause one goal for the completion of another, if you think it improves the sequencing.
    • I paused this course twice, once for 6.0042j (which I was closer to finishing) and once for the web developer bootcamp (whose completion was more urgent).
  • Start with a naive solution, then iterate towards improvement/Ignore the temptation of the ideal solution
  • Make your synthesis articles visually appealing
    • You can feel more proud of your work
    • Visually appealing articles are much more easily and quickly communicated. With a visual representation an outsider can gain a much better understanding of what you did in 30 seconds than if you just left a giant block of text with a few complicated math problems sprinkled in.
  • One doesn’t count to 1000
    • I had to make the transition from counting my hours to making this a major part of my lifestyle. At first I was tallying off every hour I completed towards my 1000 hour goal. I made mini goals to hit so many hours a day, week, month, but I was always behind. Once I decided that this was important to me and dedicated sacred hours to this, I stopped counting completely and realized that I would easily overshoot my goal. If you hope to make significant progress on a big project you need to stop counting away the minutes to completion and make it a part of your life. Take detours here and there, fall in love, but make it a part of your lifestyle, that way you won’t need to count or remember. Instead you use the habits, taught and synthesized from your past self, to propel you current self forward.

What I’ve Learned about Learning in Six Months in a Neuroscience PhD Program: Guest Post by Raymond Sanchez

I didn’t start this website because I felt a need to be heard, or that people should necessarily be listening to (or even interested in) what I have to say.  I started this website, and the projects on this website for one simple reason, because I’d spent years searching for something like it, and it didn’t exist.  One day, I decided to take ownership of my desires, and started creating the things I had spent years longing for.

When people ask me about my involvement with something I do, whether it’s degree program, a company, a hobby, a subject matter, or a sport, I often find myself saying “It’s a thing for me, not the thing“.  Learning, however, is the thing for me, and is exactly what I try to build my life around.  After I read Raymond’s blog and had a few conversations with him about the learning process and neuroscience, I realized that he could become a valuable learning mentor for me.  So, somewhere between our first and second podcast episodes, I asked Raymond if he had any interest in writing an article titled what I learned about learning in my first six months in a neuroscience PhD program.  I told him I didn’t want to give any inputs other than the title, so that I could hear what he had to say about the topic, unfiltered, and without any anticipation of what direction he should go.  I did this because trust his judgement and wanted to hear his independent ideas expressed clearly.  The post below was not what I expected Raymond to say, but is surprisingly consistent with many of the ideas I’ve had around how we learn from my recent first-hand learning experiences.

Raymond is an incredibly smart, knowledgable, introspective, analytical, articulate, and genuine guy, and if you have any interest in my writing you’ll probably enjoy his as well.  If you like this article, check out his blog MangoRaySanchez.com.  If you want to learn as much as possible from this article, don’t just read it, live it, experiment with it, try it!  It’s what Raymond himself recommends. 😉 ~ Charlie

What I’ve Learned (about learning) During My First 6 Months in a Neuroscience PhD Program

By Raymond Sanchez

As you’re all well aware, Charlie has been doing a fantastic job of writing and sharing blog posts full of thoughtful reflection and actionable advice. The quality of his posts and our mutual interest in writing have been catalysts in pushing my own blog forward, so when he asked me to write this guest post, I was happy for the chance to contribute.

For those of you who don’t know me, I started a PhD in Neuroscience at the University of Washington in Seattle about 6 months ago. When Charlie first suggested I write about what I’ve learned (about learning) since I started, I had absolutely no idea where to begin. I’ve studied topics ranging from movement control and visual processing, to cell biology and pharmacology. I’ve been fortunate enough to have opportunities to conduct research addressing the neural mechanisms of sleep, circadian rhythms, learning and memory. Basically, I’ve learned more about the brain than I ever thought I’d care to know.

I could spend this entire post regaling you with amazing stories of how this gelatinous, three-pound lump of flesh occupying our skulls makes us human. I could even write about some practical daily applications of neuroscience, like how to get on a better sleep schedule or how understanding basic motor neurophysiology can help you improve your physical intelligence. But I’m not going to talk about any of that.

The gelatinous, three pound lump of flesh that makes us human.

The gelatinous, three pound lump of flesh that makes us human.

Instead, I’m going to discuss two broader and far more important lessons I’ve taken away from the last six months: the importance of learning by doing; and the power that comes with the ability to adapt in the face of change.

Now, these ideas likely won’t be new to any of you (especially if you’re interested in the topics Charlie typically discusses), and they certainly weren’t new to me. Still, they became much more real to me as I transitioned from my relatively cushy life as a college student in my hometown to a much different environment in a huge new city. The serendipitous coincidence of this tough transition and some fundamental shifts in perspective about what sorts of things I’d like to accomplish, both in grad school and outside of it, forced me to re-evaluate how effectively I’ve actually been implementing these lessons in my own life.

Life in Graduate School

The goal of a doctoral program (assuming it’s research-based) is to move away from the didactic methods of classroom lecturing, and towards a more practical, hands-on approach to learning. After spending the majority of my last four years in college sitting in a desk and listening to someone talk at me all day, I was excited by the idea of taking more ownership of my learning process.

Of course, like most neuroscience PhD programs, the first year or two (out of five total) include a fair bit of lecture-based coursework. I knew this going in, but figured they wouldn’t take too much of my attention away from time spent in the lab. Imagine my frustration, then, when I found myself spending a majority of my time listening to lectures and stressing out about homework assignments.

In the classroom, we were forced to consider questions like: what physical properties of the cell membrane allow it to conduct electricity over long distances? Or, how do these properties change in response to different genetic mutations? Rather than flip through textbooks or frantically copy down notes from slideshows, the lab I worked in was studying the same problems by actually making chemical and electrical alterations to real-life neurons, and listening in on the “conversations” they were having with one another. Unsurprisingly, I learned far more about the firing habits of neurons by sticking electrodes in them and tinkering than I did sitting in lecture.

In fact, the goal of my most recent research project was to characterize how a certain genetic mutation resulted in defective communication between neurons, and how this translated into deficits in the ability to learn and remember. The science of learning and memory fascinates me – in a recent blog post, I discussed how better understanding the mechanisms underlying the learning process can have implications for everything from our education system to the political process. Naturally, I was pretty excited by this project.

Weeks passed. While I learned a lot about how this particular mutation affected learning, I became increasingly aware that what I was spending the majority of my time doing was extremely esoteric, and unlikely to have much impact on how people learn, even in the long-term.

Thinking vs. Doing

It was around the time I came to this realization that I began reading the book Antifragile by Nassim Nicholas Taleb, a Wall Street trader turned philosophical essayist (note from Charlie: I see Taleb as a mathematician.  All of his work is centered around analysis, and most of his work, from books to hedge funds, analyzes patterns and uncertainty in complex systems). The book is overstuffed with valuable insight, but Taleb’s core message is that some things benefit and grow when exposed to stress, randomness and disorder. Anything that possesses these qualities is called antifragile, and some examples include: evolution, culture, political systems, technological innovation, and bacterial resistance. Everything else is fragile, and that which is fragile can only be transitory. Taleb argues that the rigid “publish-or-perish” nature of academic research is especially rife with fragility, and that the great leaps forward in technology and medicine are the result of stochastic tinkering and maverick innovators, rather than theories from theorizing theoreticians published in exclusive journals. Simply put, we humans are much better at doing than we are at thinking.

As you might imagine, this realization was not a particularly productive one to have halfway through one of the most challenging periods of school I’ve had in my life. To be blunt, in the last six months I’ve learned that I’m pretty frustrated by the indirect, slow and esoteric nature of most basic academic science (to say nothing of the ugly political brown-nosing and begging required to even stay above the poverty line, much less relevant, in this game (Note from Charlie: the start-up world has some scary parallels to what Raymond expressed in his parenthetical)).

Still, this isn’t to say I don’t love doing science and that graduate school hasn’t been an awesome and enlightening experience – I have just been reevaluating what I want to accomplish as a scientist, and the kinds of contributions I want to make to society both within in science and without.

Honesty about my feelings towards my work and readiness to reevaluate is both deeply and fundamentally important. Too often in life, people have changes of heart over their work, hobbies, goals and relationships, and ignore them in favor of the “safe route” – putting their heads down and settling for that secure (but soulless) 9-5 job or comfortable (but passionless) relationship.

The cherry blossoms on campus, where I imagine Raymond takes his Talebian "thought-walks". Photo by Raymond

The cherry blossoms at UW, where I imagine Raymond takes his Talebian “thought-walks”. Photo by Raymond

For many people, any disruptions to normal life, both internal and external, can be completely derailing. Indeed, my own realizations about thinking versus doing could very well have derailed my experiences and attitudes towards grad school, and at the very least made the next 4-5 years a complete and total drag (note from Charlie: and potentially a waste of time). Instead, I’m exercising my ability to adapt in the face of internal change, changing course and setting the following goals for myself:

  • Engage in scientific research that aims to have a direct impact in the lives of real people. Starting in April, I’ll be working at Seattle Children’s Hospital studying Dravet Syndrome, a severe form of childhood epilepsy and autism.
  • Making innovations in STEM less esoteric and more accessible to the general public. I’ll work towards this by blogging semi-weekly on my website and open source journals like PLOS One about topics in science and their practical applications.
  • Working with some close friends to turn a couple of ideas for startup businesses into a reality (Taleb argues that entrepreneurship and writing are among the most antifragile professions there are, and I’d tend to agree).
  • Re-engaging with some personal learning-by-doing experiments that have long been sitting on the backburner, like learning French and electronic music production
  • • Most importantly, never sacrificing my own happiness for the sake of a “career”.

If you get nothing else out of this article, take it as an impetus to look for the own fragilities in your life, whether they’re in work, school or relationships. If you want a change, don’t be afraid to act on it and deal with the consequences as you go along. Most importantly, take ownership of your own learning, and don’t forget that your greatest advances, both personal and beyond, will come only as the result of taking chances.

(Note from Charlie: I often find that the greatest risk is not taking enough risks, because, as Taleb argues, capping the downsides often caps the upsides.  When you protect yourself from heartbreak you prevent yourself from fully experiencing love.  I’ve found this this applies to almost everything from my first-hand experience).