## 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.

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.

- 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
- 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.
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.

- 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.

- Synthesis (15%)
- I identified (in this case singular) the most important core principle underlying the content of the course. This principle is as follows;
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.*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 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*

- I identified (in this case singular) the most important core principle underlying the content of the course. This principle is as follows;

**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.. 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.*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*

- 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