TABLE OF CONTENTS
- Your Learning Curve
- The Most Important Strategy: Get Started
- Be Part of a Community
- The Mentor
- The Peer
- The Mentee
- How to Find Answers
- Using Your Problem Solving Toolkit
- Ask a Peer
- Ask a Mentor
- Deliberate Practice and Application
- The Best Tool: Get Your Hands Dirty
- Simplification of the Problem
- Simplification of the Examples
- Other Tactics
- A Coherent Meta-Example
- The Roadmap
- Semester 1 – Practical Programming
- Semester 2 – Data Structures & Discrete Mathematics
Learning computer science is one of the most enjoyable experiences in human life, also one of the most frustrating. You came across this page because either you want to learn about computer science, want to learn computer science, or want a computer science job. Whatever your motivation, computer science may seem like witchery to you. Geeks use overly complicated jargon to explain concepts to you. A friend of mine, Michelle Bu (who has an amazing anecdote about being a novice programmer by the way), noted that “programmers have a perpetual competition to see who can claim the most things as ‘simple.’”
You want to join the club, but you don’t know how to get there. Joining the world is like trying to take down a castle with a butter knife. I remember my first lessons in computer science. I tried to learn how to program by googling “How to Program.” In hindsight, it was futile as each search result was either too encompassing and vague, or too technical and detailed. I went to ask my computer science friend. It went something like this:
Me: “I want to learn how to program. Can you teach me how to program?”
Friend: “Sure. Let’s start with variables. A variable stores a value. There are different types of variables. A int variable stores an integer, a long variable stores a larger integer, a boolean….”
Me: “Hold up. What? Back up. What’s the difference between an int and a long?”
Friend: “One stores a 32-bit integer and one stores a 64 bit one.”
Me: “What does ‘store’ mean?”
Friend: “It puts the value in a memory location.”
Me: “What’s a memory location?”
Friend: “The memory location is where the information is stored.”
Me: “That doesn’t help, where the memory location? And how does it decide where to store it?”
Friend: “Well, when the compiler of the program runs, it creates a memory address in the memory. When you have a variable name that references a values. The compiler will look into that memory address.”
Me: “Huh? What’s a compiler?”
Friend: “Don’t worry about it. Just remember that a int stores a 32 bit integer and a long stores a 64 bit integer.”
That was unhelpful. Asking a simple question like “What’s the difference between ints and longs” unravels 3 others questions about computer science. It’s like trying to behead a hydra. Chop one head off, and it’ll come back with 3 heads. Before you know it, your instructor’s trying to stitch the heads back on just so you would shut up.
I don’t want anyone to be scared off by an experience like this. Some aren’t so fortunate to have the support I’ve had when I was learning computer science and have long shied away from it. Computer science is fun. In my opinion, it’s one of the truest expression of self. It has the best ability to innovate and create. It’s like playing God. Sure, you’ll mess up a bunch of times (it’s part of the excitement), but whatever you create, you’ll own.
This guide is lengthy, but you can really just break it down into several manageable parts to read it, or come back to it often when you feel lost or get stuck. It’s meant to be comprehensible, and it’s my intention to bestow as much knowledge as I can on you.
Note to “expert” programmers: A lot of the things I say are crude and may not be 100% accurate, but for the simplicity of understanding concepts and computer science terms, I chose to appeal to the laymen. If vocabulary could be taught by reading the dictionary, we wouldn’t need elementary school. Likewise, it wouldn’t help a beginner much to hand him a manual and say “Read this.” Thank you for your infinite patience. Message me if anything bothers you.
To learn computer science, you must break down the process of learning into three hierarchical forms of learning from the abstraction to the fine tuning. Many guides (if any) only focus on one of these aspect without giving an overarching understanding or fine tune implementation. Your learning, learning objectives, are broken down into general strategies, helpful tactics, and tool acquisition.
Strategies are overarching principles in studying computer science. In this section I’ll be covering the necessary infrastructure for learning. These concepts cover topics like how to seek help, how to ask questions, how to set up an environment for learning, and how to debug.
Tactics are strategies for tackling computer science problems. Problems are different from exercises in the sense that you don’t know how to go about solving a problem. An exercise would be something like 82 to the power of 32. Even though it’s a difficult exercise, you would know exactly how to solve it.
A problem, on the other hand, have an ambiguous presentation. You may see a problem and not know how to solve it. It creates mystery and a sense of helplessness in many, but it also creates wonder and excitement in those who like challenges. Of course, everyone has different boundaries of what they define as a problem or exercise. Some may consider a question a problem whereas others would consider it an exercise.
Learning tactics is building an arsenal of tools for tackling new problems. Computer science is filled with fun and challenging problems to take on. In this section I will teach you some of my favorite methods to tackle new challenges.
Tools are the kinds of things most people think about when they think about computer science. “Knowing Ruby” and understanding “How to design greedy algorithms” are things we consider to be tools. Tools help you do things in computer science. You will learn tools in your journey in computer science.
Learning tools and tackling problems use slightly different approaches when it comes to learning, but they both share a lot in common in terms of learning. Tools entail syntax of languages, data structures, and anything that is a concrete understanding of something. Often, once you’ve solved a problem, you’ve acquired a tool to solve similar problems. Maybe it’s a hash table or recursion (don’t worry if you don’t understand these terms right now) you learned about in your studies. Tools are the least important concept of all three because no matter how many tools you acquire, if you don’t know strategy or tactics, then you won’t know how to improvise, and will forever stay a novice.
As you may see, strategies are the most important topic in learning computer science, followed by tactics, followed by tools. In fact, I will put very little emphasis on tools. I will point out which tools to acquire and how to acquire them, but I won’t go too much into the material itself.
Your Learning Curve
Everyone will have their moment of self doubt in their journey towards learning computer science. It’s okay! It’s completely natural to feel this way at times. To help you counter your journey, we must understand the journey before us. Here is a map:
There are three stages of understanding that is used to model our learning paths. At the beginning, everyone is what we call an apprentice. The main role of the apprentice is to mimic. They copy the masters and do as the masters do, sometimes without much questioning. During this stage of learning, as most beginners do, you will learn by following exercises and doing what the teacher tells you (“teacher” is a flexible entity that could be a book, a tutorial, or an actual teacher). If the teachers throw all the material at you and said “learn this,” you’ll flounder and sink like a rock. You’ll be overwhelmed by the material and discouraged by the monumental challenge. So instead, you are to learn through structure. However, after a bit of time, you’ll feel comfortable in the material, well, sort of. You’ll feel comfortable in this tiny realm of mimicry.
Apprentices learn at a fairly quick rate until they hit the first peak. Afterwards, they graduate to be an artisan. Instead of following “best practices,” artisans have to learn to improvise. All of the sudden, there is no template to copy off of anymore. Sometimes, there isn’t even a “correct” solution. The training wheels that were once a safety net are now gone and it creates a sense of frustration and loss. Good programmers get themselves out of these trenches. They struggle tremendously through late night obsession, lack of sleep, minor depression, and rigor. The push past their ceiling until they are out of the trenches.
Then they plateau. They either become comfortable or they continue to hone their skill, sometimes believe they are not getting anywhere. In some considerable time, they become a master.
Like the learning path, this guide is broken into those three stages. Tools are the main approach used in the apprentice phase, tactics then take over the dominant role of learning in the artisan phase. Strategies, although cannot guarantees mastery, are essential parts to helping you reach there. This path is fractal in nature as well, as it describes not only the general learning path, but also the learning path to learning each new C.S. concept as well.
Understand where you are in the journey can ease some anxiety and nervousness about your initial failures. If you ever feel down about your journey. Don’t give up, just remember that frustration is currency of progress and dedication in price you pay to be a successful student.
Let’s talk strategies. Many people are afraid of learning how to program because they don’t know how to go about learning computer science strategically. They don’t know where to start, where to go, what language to pick, or what they don’t know (not knowing what they don’t know). Knowing how to tackle new learning endeavors strategically means a more directed effort towards your learning goal.
The Most Important Strategy: Get Started
I think if you could only take away one lesson from this guide about learning, it would be to get started as early as possible. It doesn’t matter if you learn in a less inefficient manner or don’t know where you’re going. As long as you know whatever it is you’re doing is heading in the right direction, it is the best option to go about it.
If you still have a lot of unanswered question about computer science like “what programming language should I start learning?” or “What tutorials are the best for learning X?”, you should push aside those questions for now and just get started. Many of the answers you will find along the way. People tend to fall into analysis paralysis. They read up about computer science, purchase programming books, and read guides (like this one) to formulate a lifelong plans about how to study computer science but they never write a single line of code.
If you ever find yourself in a state of analysis paralysis, find an actionable step to take in the direction of your goal and take it. I’ll even do it for you if you can’t make a decision, just follow The Roadmap on the bottom. It won’t be the best, but it will get you to your destination. Your first priority, like every beginner’s first priority, is to take the first step.
So jump! Come join the world of computer science and have fun being lost. Author Tim Cahill of the book “Jaguars Ripped My Flesh” once quoted, “The explorer is the person who is lost.”
Be Part of a Community
I’m a big fan of online learning. I take online courses on Coursera, Udacity, and Edx all the time. As much as I would love to urge everyone to sign up for these classes and do away with people, being a part of a community is important to grasping and understanding computer science. Not only is collaboration important for learning computer science, it is crucial for when you work in the industry, as everyone in the computer science industry collaborates with one another.
I think it’s important to have at least one figure in each of the following roles to have a complete and satisfying learning journey. Forming a community is beyond just once-a-lifetime encounters. It is regularly seeing, meeting, and interacting with these people. Having a strong community (not necessarily large) will make your learning journey much easier, directed, and frankly, fun.
Have a mentor. You want someone who is better at computer science than you to explain and answer any questions you may have. Having this person on call is extremely important because there will be times in which trying to find answers online and through books will not be fruitful. You will be frustrated and you will be angry, and then you will feel helpless and self-loathing. You need someone’s help. You need someone who can listen to your problems and answer your questions, someone who’s been in your shoes before and understands the hardships you’ve been through. Not only can they answer technical questions, they can also answer broader questions like “I want to build a robot that can drive itself, what should I study?” or “I’m not quite sure what I should learn next.” Their experience is not to provide a curriculum, but rather to provide directions and insight.
Really do try to find a patient and understanding teacher. It’s better to find someone who has a poorer mastery of a subject who can explain his understanding clearly than it is to find someone who is a computer genius who would just scoff at your dumb questions. This is crucial. I’ve seen many ambitious computer science beginners give up their pursuit of computer science because they met someone who not only does not answer their questions, they demean their mentees for asking such dumb questions as to extinguish their flames of curiosity. Find someone who brings out the best in you and whom you can really trust for their wisdom.
Also it is preferably to find someone who you know in person and can meet up in person. Best case scenario is that your mentor’s already your friend. Worst case is that you lack friends who know computer science. If you know an acquaintance (or even a stranger), ask them for help, they will be flattered. If you’re in school, look for the teacher assistants of the class. If you’re still fruitless, check to see if there are any local programming groups at your local university or MeetUp.com. If all is hopeless, check out StackOverflow and other forums for learning computer science. Often, you’ll find a wide and supporting community (although never paramount to person-to-person meetings). If you are a UC Berkeley student and don’t have a mentor, message me.
Another important person in your learning community is finding someone who is around your level of expertise. I find that the process of discussing computer science concepts with another human being to be extremely rewarding both in terms of building a meaningful relationship and learning computer science. Your peer will teach you, encourage you, and help you more effectively than you can yourself. I know many travelers who give up learning because they become too uncomfortable being lost in the world of computer science. Having a fellow nomad with you will make your journey speedier and more pleasant.
A peer will help you tackle problems. Although it may seem like you’re slacking to divvy up the work, the learning from such interactions will increase exponentially. Interacting with your peers will help you discuss different perspectives and problem solving tactics to a particular problem. In many academic subjects, especially computer science, there will be different approaches to tackling a problem. By exposing yourself to different approaches and methods of understanding a concept or solving an exercise, you understand the material at hand more thoroughly.
Vocalization of your own thoughts will also help you solve problems, even if both of you are lost. In computer science, it’s often called “The Rubber Ducky Debugging Tool,” which is a debugging methodology where you explain your bug or problem to a rubber duck, thereby understanding the problem a bit better. Why use a rubber duck when humans, understanding and responsive humans, are so much better?
Beyond the realm of problem sets, peers will also bring the culture of the classroom into your everyday life, which is more important than one would think. Often, I remark a humorous computer science joke during normal conversations, only to have it help me understand concepts a lot better.
If you are of the competitive nature (like I am), then you will understand how having a peer will keep you on track to progressing your own individual goals. They will challenge you to perform your best, they will encourage you if you fall behind (you are their peer as well), and they will make damn sure that you are a worthy competitor so that you can challenge them as well.
Find a learning peer who you work well with. Being friends is important, but don’t let it become distracting when you guys have to study or work together. Find someone who is as driven to learn computer science as you are, but who is still patient with you when they are ahead (like helping you with your problem set even if they finish before you). Availability is very crucial for learning buddies, as you are expected to meet regularly with your peers.
Although not strictly necessary, if you really want to solidify your understanding of concepts (generally closing the 10-15% gap of understanding), find someone who is worse at computer science than you. By being able to explain your ideas clearly and simply, you truly demonstrate, to the world and to yourself, that you understand the concept. You also give back to the community that has helped you in your journey.
Having a community that consist of people who fulfill these roles is important and is often the first failure point for beginners. Without the right type of support, students will struggle through unnecessary hardships.
How to Find Answers
The chain of command I follow when it comes to answering questions goes in the following:
- Use your problem solving toolkit
- Google It
- Ask a Peer
- Ask a Mentor
Using Your Problem Solving Toolkit
Before I look for any help anywhere, I tend to try to exhaust my problem solving toolkit and tools. I look at each of my tools and tactics (which I will teach some to you in Tactics) and see if the tool or tactic will solve it. I explore a path through a tactic, evaluate my current standing, and try a different path. I don’t move on to the next chain of command until I’ve exhausted all possibilities and all my tools. Finding answers without trying to answer the question yourself will rob you of your insight. You’ll have trouble remembering the context of the problem, the nature of which the problem is constructed, what you do or don’t understand, and naturally, you’ll lack a complete understanding of the solution.
After I come fruitless with trying to solve the problem myself, I leverage the help of the internet. I google it. StackOverflow is the best website for answering programming questions. I try to come clean to the right terminology and read through several search results to try to find what I’m looking for. I can’t give you much advice. Many people know how to Google, and the expertise comes with practice, or deliberate practice.
Ask a Peer
Now if you’re lost, usually because you don’t know the right terminology or have an obscure question, find a peer to pool together your insights. If you’re afraid of bothering people (like I still am), just remember that your peer will benefit from solving this problem just as much as you will, so asking questions is a win-win situation (consider this as well when people ask you for help). Working on a problem with a peer will create a sounding board for your insights. It will cumulative collective knowledge and the power of collaboration. It will help tremendously.
I always ask for help by presenting the problem as accurately and as easy as possible, state what exactly is getting me stuck, and the approaches I’ve taken so far in tackling the issue. It will facilitate open communication and common understanding in the problem.
Ask them to voice their thoughts out loud. Their interpretation of the problem, their initial reactions and thoughts on it. Then ask them how they plan on extracting more information from the problem, if not solve it. Take their thoughts, which will be a jumbled mess if they are just as confused as you, and rephrase it back to them so both you and them understand what’s going on. Point out the obstacle, and discuss how to get around it.
Ask a Mentor
If you’re still lost at this point, it’s time to go ask a mentor. To maintain a good relationship with your mentor, regularly meet up with them, even if you don’t have specific questions. Mentors, all and all, should still be your friend who you can talk to. It is also equally important to not be too big of a burden to your mentor. Everyone’s patience is finite, and if you rely on your mentor to carry you all the way, you will soon find yourself mentor-less.
Ask questions, but ask questions with context. There are no dumb questions, but there are prepared questions and unprepared questions. An example of a prepared question (although may be dumb) is “How do variables in Python work? I’m trying to understand how lists are stored in memory. I tried Googling it and read some articles about loosely-interpreted languages, but I still don’t quite understand what that means.” Asking questions with context demonstrates several points to your mentor:
- I have a specific question with particular purpose.
- I have tried to seek out a solution through other means without trying to bother you.
- Here’s what I understand so far, let me know what I’m missing
Asking good questions will help sustain a good relationship with your mentor. Make sure to thank your mentor every time he helps you.
Before I take on any new learning endeavor, my first strategy is always try to find some cheap way to do experiments. Richard Feynman, Nobel Prize winner for Physics, always advocated for the opportunity to “play,” or experiment with the things you are learning. In computer science, it means writing code and subsequently debugging. Having debugging tools allows us to better peer into the program and see what’s going on. If you don’t know how to debug code, or don’t know the tools in order to do so, you’re robbing yourself of a great tool and teacher.
If you’re wondering what “debugging tools” means, you’re asking the right questions. In any programming language I learn or class I take, I seek to answer 3 questions right off the bat:
How easy is it to write and run code? Where do I do it and how? Let’s say you’re taking an algorithms class, but instead of writing the code for the algorithms, you just learned the theory. No way of testing whether it works out or not. How confident would you be to write the same algorithms you learned in class at your internship? Therefore, learning anything, the first question should be “how can I verify what I’m being taught is true?” In chemistry, you have labs with test tubes, in mathematics, you have proofs. In computer science, you have a computer and code. Setting up your computer to write and run code is like setting up a chemistry lab to run experiments. You’ll need the right equipment, the right litmus tests, the right ingredients. You’ll perhaps have to download certain software and editors. Whatever you’re learning, try to find a convenient way to be able to write and test code. Get a text editor (I started out with Notepad++ actually, then switched to TextMate when I got a Macbook). Now, you’re going have many different factions of programmers telling you what’s best for you. They’ll tell you that Vim is the best, or to stay true to Emacs. Whatever they say, ignore them for now. Having any functional editor and method is around 80-90% optimality, so please, please, do not let this “best editor” decision prevent you from writing code. That’s probably the stupidest failure point in one’s journey in learning computer science. Pick one that has syntax highlighting and move on. You can always switch later.
How are errors in my code handled? Find out how errors are handled in the code. Different programming languages have different ways of handling errors. Some programming languages are silent about their errors, others tell you exactly where you have fucked up. Sometimes errors are ignored, and other times they break down your whole program, or even crash your computer. Knowing how to know errors are being produced will help you know what’s going on, being that if you don’t know you’ve messed up, you can’t fix your problem and learn from it. Ask your mentor about this if you get stuck, just say “What will my program do if I have a bug? How can I know whether I have a bug or not?”
Deliberate Practice and Application
Computer science, out of most educational subjects, requires the most deliberate practice and application. It needs both the practice and application to get the most of your computer science education. Deliberate practice includes doing problem sets and homework. It is the process that solidifies your understanding of a particular concept or tool. Application, on the other hand, solidifies your connections to solving problems. In deliberate practice, you have the problem, and you’re seeking the solution. In application, you have the solution, and you’re preparing for the right problem to come up.
Let me demonstrate what this means through an example.
Let’s say you’re trying to learn recursion in your intro to computer science class. Your instructor gives you an assignment, maybe even a project, to help you solidify your understanding of recursion. It involves calculating the factorial of a number, among other problems (recursion is difficult!). You complete the assignment and you hi-five yourself “Yes, I just learned recursion!”
Yes, you have learned recursion. You’ll know enough to pass the test, because you know it’ll be tested. But how do you know whether recursion could help you solve a problem you encounter at your summer internship? You don’t, at least it’s not easily conceivable. If someone gave you this question 6 months later, “How can I count the number of ways to make a dollar with so and so coins?”, would you know recursion is the right way to go? Well, we can’t be sure, and it doesn’t occur to many beginners that the answer is “YES!”.
That’s why I believe that seeking out problems to solve once you learned a concept would strengthen your understanding of the concept as well as put in the right connections and cues that would trigger “Recursion! Recursion! You can solve this through recursion!” in your head.
Well, how would systematically go about applying their understanding? There are several ways. The first is finding personal projects. Find problems you need solving, and ask yourself (as often as possible), “Can I solve this using this concept I just learned?” If so, tackle it. Make it second nature to recognize when a tool is useful. At the club I’m involved in, Hackers@Berkeley, we use the concepts we learn in class, in our workshops, and online, to tackle challenges we always wanted to solve. Hence, we produce some of the best computer science students, ones that join Y-Combinator, ones that become Thiel Fellows, and land fantastic jobs and internships at great companies.
Metacognition is the other. After you complete your problem set, take a minute or two to examine the nature in which the problem was presented. Ask yourself, “Usually in what form are these problems presented in?” Find patterns that occur among problems you’ve encountered in the past. For recursion, you might think “Well, recursion problems are presented as the act of building up complexity from simple rules.” Therefore, when you see a problem that seem “grand” in nature, you’ll know to think about recursion.
Developing this “hunch” is greatly helpful in problem solving and really keeping your computer science education past the shelf-life of the class.
That’s all I really have for strategies. Building a community, being able to find answers, and developing the right habits is really 95% of the things you need to be a great computer scientist. You just have to make a commitment and DO IT.
Tactics are methods of tackling new problems. The difference between great problem solvers and the normal students is that even though both parties are stuck in a new problem, great problem solvers rarely idle and stare at the problem. Usually they are making some form of discovery or testing some form of conjecture. They always have an avenue to discover new concepts behind the problem, new patterns. Always discovering, always progressing. Having good tactics for solving problems will not only help you learn faster, it will also give you an edge in tackling new problems.
The Best Tool: Get Your Hands Dirty
There is an inherent appeal to computer science in that your curiosity can always be fulfilled. Unlike other subjects like biology and chemistry, where you need a lab, or financial accounting, where you need years of experience before management lets you handle any money, in computer science all you need to discover something new is a laptop.
That’s why the mother of all tools is getting your hands dirty. Experimentation will always yield some fruitful result in your understanding of computer science.
I’ll explain the concept of Getting Your Hands Dirty (GYHD) using a famous example used in Paul Zeitz’s book and video course The Art and Craft of Problem Solving:
Q: A census-taker knocks on a door, and asks the woman inside how many children she has and how old they are.
“I have three daughters, their ages are whole numbers, and the product of the ages is 36,” says the mother.
“That’s not enough information,” responds the census-taker.
“I’d tell you the sum of their ages, but you’d still be stumped.”
“I wish you’d tell me something more.”
“Okay, my older daughter Annie likes dogs.”
Of course when you first look at it, you would be stumped too. “What?!” I first thought, “There is no way I could extract any new information from this.” I decided to give up, only to regret that I should have paid more attention or spent more time trying to solve it for myself. I should have gotten my hands dirty.
A: Some of you may have picked up on the hint to get your hands dirty. Well, let’s do so. Let’s list out all the products which have a product of 36. They are listed as such:
Many of you would still be stumped, but let’s take GYHD a step further and list out the sums, at the very least we know the answer’s one of the 8 choices. You will quickly find that two of the options, (1,6,6) and (2,2,9), have the same sum. Those two are the only two pairs in which ambiguity can exist. If the woman had daughters of any other age, her telling the sum would NOT have stumped the census taker, but those two possibilities will. As a bonus treat to the riddle, to figure out which answer is correct, you have to notice that the mother says “Older daughter Annie.”, which means that there exists an “oldest daughter.” The ages of the daughters must be 2, 2 and 9 then.
We would have never arrived at the answer nor know there was a possible solution from the outset. We would never know until you dug a little deeper, explored a little further, to see what other information the current information can provide.
In computer science, particularly on tests and technical interviews, you are often asked to solve a problem quickly (uses less time) and efficiently (uses less memory). A tip from Cracking the Coding Interview by Gayle Laakmann suggests that before you come up with your best solution, come up with a less than ideal solution. Why? Because often questions are difficult enough such that you cannot see the best answer right away. Having a stepping stone, a less ideal solution, is crucial to reaching your final destination. Many questions have a series of stepping stones. Usually the most easiest to conceive is called “Brute Force.” Let’s do an example to demonstrate thought processes that can go into solving a question. I modified the problem to make it understandable for CS beginners.
Q: If you are given 100 tiles numbered from 1 to 100, shuffled in a bag, with 1 duplicate number in the bag that’s between 1 and 100 (giving you 101 numbers), how do you find the duplicate number efficiently?
For the sake of people to understand what time complexity and space complexity is, I’ll simplify the objectives of the question to be.
Time Complexity: How many mathematical operations must you do.
Space Complexity: How many tiles will be remembered at any give point? Let’s say you remember a tile if you lay it out on the table.
A1: Well, let’s try a brute-force styled answer. Well, by definition, duplicate means “already occurring”. Let’s take the letters out one by one, and for each one we take out, we compare it to the tiles that are laid out on the table, and then lay it out on the table. If we find the duplicate, we stop.
A1 Analysis: Although this solves the problem correctly (it will always give us the correct answer), the task of finding the duplicate is very inefficient. Every tile we take out, we have to do 1 more comparisons than the last one. If the duplicate is the last time, we would have done 4951 comparisons, taking up 100 spaces. Let’s try to do better. For any bag of number tiles from 1 to N, with a duplicate, you will be making N(N+1)/2 comparisons and N spaces.
A2: You notice that since each number only occurs once except for the duplicate, there must be one space for each number tile. So you draw a 10 by 10 square grid on your table, and for each tile you take out, you place exactly where the tile should be. 64 means the 6th column and 4th row. So on, so forth. You stop when you place a tile onto an already-occupied square.
A2 Analysis: Now you always take up 100 spaces to place your tiles, but you are guaranteed to find your solution by the 100th try. Let’s see if we can do even better.
A3: Now you see if there’s anything special about 1 to 100. Well, you can notice that the sum will always stay the same no matter what or how it’s scrambled — it will always add up to 5050. Whatever, the duplicate is, it will be 5050 plus the duplicate number. So, you take out a piece of paper. Every time you take out a tile, you add the tile’s number to the number on your paper. Then you chuck the tile away. Do this for all of the tiles, and you’re left with a number. Subtract 5050 from this number and you’ll be given the duplicate you want.
A3 Analysis: Since you don’t even care about order anymore, now that you relied on your sum, you only have to remember one number at a time, the sum of the numbers. The number of computations will always be the number of numbers, but that saves a whole lot of space without having to keep track of so many numbers.
It is very hard to see the perfect solution from the get go. Nothing would have prompted anyone (inexperienced) to add everything up and subtract 5050 from that. Only by using stepping stone solutions and getting your hands dirty could you have reached a satisfactory point.
So get your hands dirty. Do so by providing examples, examples that succeed and examples that fail. Provide solutions, solutions that fail to solve the problem, solutions that solve the problem, and solutions that solve the problem effectively. Learn from all your attempts.
Simplification comes in two forms: simplification of the problem and simplification of the examples. Simplification is a method of edging closer to the solution and finding tangible patterns for the problem itself. Actionable simplification will help you come up with good patterns to help problem solve.
Simplification of the Problem
I had a fantastic professor of discrete mathematics (Shoutout to Professor Sahai of UCB) who gave us very difficult questions to solve, but instead of being that of a harsh and resentful type of professor, he rewarded partial credit to students who solve a simplified form of his questions. He once said in lecture:
“If you can’t solve a problem, try taking some of the conditions away from the original problem and solve the easier one. Once you have solved that, start adding back the conditions back in to see what fails, and you can examine why the things that fail, fail.”
Brilliant concept to practice and this type of problem solve is used all the time in engineering. “If we can’t go 100% of the way there, let’s go to 60%, or 70% and then re-evaluate and see if we can go further.”
Here’s an example of simplification of the problem (taken from the final of my discrete mathematics class).
Q: While ﬁghting GLaDOS, Chell starts at the origin in the (x,y) plane, and every second moves a distance of exactly 1 meter in a uniformly-at-random direction. The direction is independently chosen every second. After n seconds, if R is Chell’s distance from the origin, what is E[R2]? (E[R2] is the expected value of the distance square, also known as the variance of the distribution).
When I first saw this problem, I panicked. I didn’t know how to start and where to go. However, I resorted to simplifying the problem, and it helped me made significant progress.
Sub-Solution: Let’s suppose instead of choosing a uniform direction at random, we could only choose 4 directions — North, East, South, and West. Let’s solve for the expected distance from the original after n seconds.
To do so, we break down the choices into change in x and change in y. Either it’s going to move in the x direction or move in the y direction, both by precisely 1 meter. So our expected distance in the x direction is 0 in one sec, and our variance is ½ (Var(X) = E[X2]+E[X]2=½ +0=½). In a similar fashion, the variance of the y distance per second is also ½. Since we want variance of the distance to the origin, x2+y2, we also have to add the variance, which results in n2/2, the expected value is then .
I then realized that North, East, South, West, were special cases of the equation:
X=cos(Θ) and Y=sin(Θ) (Interestingly enough, X2 +Y2 =1) with uniform distribution of Θ in [0,2]
(just think of the unit circle of trigonometry).
Therefore, using linearity of expectation, we have
It’s ok if you don’t understand the explanation, it’s a lot of discrete mathematics that you’ll learn someday. Just remember that simplifying the problem in my case helped me understand the question more coherently because I took away some conditions, solved an easier problem, and see if that helped me solve the more complicated version of it.
Simplification of the Examples
Q: What is the expected number of Facebook friends you should have such that you have a birthday on every single day of the year? For simplicity’s sake, we’ll assume there are no leap years and we’ll assume that all your friends have an equal probability distribution to land on any given date. (Expected number is this case is restate like this: Assuming you have X number of friends. There is a 50% chance that your X friends have occupied every day of the calendar and 50% chance that they have not. Find X).
Well isn’t that a tough problem to tackle? Where do you even start? Usually people think of the bottom line, there’s got to be at least 365 people right? One for every day, but where do I go from there?! What if it never lands on a particular date? Do I have to calculate the chances of that as well? Gahhh.
A: The answer only becomes clear when you simplify the example. Let’s say you only have one day a year and you want to know how many friends it takes to occupy your year. One of course! Well now, how about 2? Well, the first person could occupy any day he wants as long as the second person does not occupy the day the first person does. That makes it a ½ chance of landing in the correct date. From the geometric series lesson (don’t worry if you don’t know what this is), the expected outcome that it takes to each successful outcome is 1/p, where p is the probability of the desired outcome. Since there is a ½ chance that the second person is different from the first, it is as if I was flipping a coin, the expected outcome is 1 over ½, or 2. So if it takes one person to occupy date 1 and on average 2 people to occupy day 2, then the total expected outcome is 3.
See where this is going? With 3 days a year you only have to calculate each successive expected value. The first person has a 100% of landing on a date no one has landed before, so his expected outcome is 1, the second filled date has a ⅔ chance of landing on a square that hasn’t been landed on before, so his expected outcome is 3/2. The last vacant date needs on average 3 friends to fill it. So as you build each inductive step, you notice a pattern, and therefore a way to simplify it.
It seems that if there are n days, the first day is n/n=1, the second is 1/((n-1)/n)=n/n-1, third is n/(n-2)… all the way up to n/1=n. So your solution is the summation of those terms, with n = 365, which in our example, turns out to be 2365 friends.
Often, tackling a problem head on is overwhelming. It’s often easier to break the problem down into smaller problems, solve the smaller problems independently, and stitch them back together, either gracefully by recognizing a pattern among the various solutions or by using conditional statements. Here’s an example problem I’ve encountered on a phone interview (I messed up badly on the phone interview, but I went back several months later with a problem solving mindset to solve it).
Q: Given a list of intervals of which a mathematical function is defined and another interval called the target interval, return the list of intervals that intersect the target interval.
Here’s an example
—–[ ]—-[ ]—-[ ]————-[ ]—–
I want intervals in the target interval:
It should return:
——–[ ]—-[ ]—[ ]———————-
Really we’re only interested in the brackets and the space inside the brackets. We’re trying to find the intersection of the first and second line of brackets (the given intervals and the target interval). On the phone interview. I treated every given interval as the same. I tried to test each one of them to see if it was in the target interval, out of it, or partly in it. I messed up really badly because of this. I made it overly complicated and therefore my program failed.
Here’s a proposed insight and answer.
A: Not all brackets are the same. There are brackets that are inside the target interval, and there are the two edge brackets which we have to test to see if they are partly in the target interval. Moving from left to right, we will always have the unaffected intervals in the middle be part of the result, no questions. Therefore, we just take all the intervals that are completely inside the target interval, then test the intervals that are the direct edges of the encompassed intervals to see if they partially intersect the target interval.
Here is pseudocode written to solve the problem:
For each interval in the list of intervals:
if it is completely between the target interval, add it to the list of answers.
otherwise, if it intersects the lower bound of the target interval, add the interval
[lower number of the target interval, upper number of the given interval]
otherwise, if it intersects the upper bound of the target interval, add the interval
[lower number of the given interval, upper number of the target interval]
otherwise, it’s not in the interval or touching it,
Leave it out of the answers
return the list of answers
There. Done. I broke each interval down into four cases, and handled each case separately.
Some tools that come in handy that I won’t provide examples for. By knowing these tactics, you’ll recognize them when they show up and strengthen them in your toolkit.
Related Problem: When I’m stuck, I ask myself if the problem is similar to any problems I’ve solved before. I look at these similar problems and reflect on how I’ve solved them. I use the insights required to solved the previously solved problem to solve the new one.
Wishful Thinking: Sometimes I think backwards and start with the solution. I think about this elusive variable that is the solution, and manipulate it to fit the conditions of the problem.
Of course there are many, many more problem solving tactics out there. I just named a few of my favorites, and the most common ones used in computer science. You will acquire more. Some day you’ll face a problem that you can’t tackle. You’ll learn how to solve it, and it doing so, you’ll reflect on how you solved it, and you’ll realize, “Hey, I just found a new approach to a problem!” And you’ll find joy, the joy resulting in knowing that you not only have a better understanding of a problem, but that you’ll have a better understanding of future problems as well. Give yourself a pat on the back.
Note: There is a giant list of problem solving tactics found in George Polya’s book “How to Solve It” that I highly recommend people read. Even though the book is designed to help with mathematical problem solving, the tactics easily apply to computer science problems. There are tactics like “Wishful Thinking”, “Auxiliary Element”, and “Analogy” that help with any kind of problem solving.
Learning tools are often the topic most focus on but often with the least efficiency of acquisition. My framework of acquire tools is an adaptation and simplification of several different sources of information. Each resource has its tradeoffs, most notably between the level of mastery and the amount of time commitment.
Here are my two objectives in relations to computer science that justify the methodology I use.
- Get an A- or better in a computer science class relating to the particular tool
- Get enough working knowledge to be able to apply what you learn in your code and projects
Since our focus in on computer science, I’ll be focusing on adjusting learning styles to take advantages of two things that are unique to computer science: abstraction and testability. Abstraction of computer science means that many computer science concepts and terminologies can be abstracted and used in metaphors. It’s a very intuitive subject and easy to pick up (which could explain why it’s so popular). The other beauty about computer science is that it is extremely testable. Have a question about computer science? 80% of the time you can easily test it out.
Therefore, my main focus in learning tools is through Scott H. Young’s methodology in Holistic Learning. Scott has taken 4 years’ worth of MIT computer science courses in one year, and passed. Through his experiences, he’s developed a framework for learning anything. I’ve adapted this and appended some of my own commentary, some taken from personal experience, some taken from other frameworks for learning.
The focus of his approach, as outlined in his book Holistic Learning, Young breaks down the learning process into 3 distinct steps.
The first step is called visceralization. Visceralization is the process of taking something that feels unfamiliar and becoming familiar with it. Every new concept we learn we start with an unfamiliar relationship with the concept. It is mysterious, almost arbitrary and poorly understood. To achieve mastery of the concept, you must shed light on it. Tim Ferris, author of Four Hour Chef, would consider this stage “Decompression.”
If the concept is too hard to grasp, try using several different problem solving tactics in simplification. The extreme principle helps significantly. See what happens when you take the concept to the limit. If it’s recursion, try working backwards, to the end state of the problem. If it’s an equation or some form of algorithm, trying plugging in extreme values like 0 or a really large number and seeing what happens. The extreme principle, as Paul Zeitz in “The Art and Craft of Problem Solving” would put it, “reduces the degrees of freedom a problem has.” It helps a lot when you limit what the concept can do, so you take it in bit by bit. Of course, this application of the extreme principle is just a form of the tactic Getting Your Hands Dirty, which should always be used to learn new tools. If it’s a mathematical proof, follow the proof until you understand how the proof was derive. If it’s a certain concept like recursion, understand it visually. Use diagrams, pictures, sounds, gestures, whatever it takes to get an intuitive feel for it. Claw at it, get frustrated at it, discuss it, mull over it, maybe cry in desperation, sleep on top of it, and usually in some time, it’ll feel natural to you.
Afterwards, you build models or metaphors. In other words, you take what you know to explain the things you don’t. In computer science, it’s really easy to make metaphors for things.
Before we take the right approach, let’s check out the wrong approach. Let’s check out the “formal” definition of a variable that Wikipedia has defined:
“A variable is a storage location and an associated symbolic name (an identifier) which contains some known or unknown quantity or information, a value.”
It might make sense to the average computer scientist, but to a novice, it means NOTHING. WTF is a storage location? Is it on a hard drive? A CD-ROM? Symbolic name? WTF? Are we talking hieroglyphics here? “Unknown quantity”? What does that mean?
There’s no coherency to adhere to. Nothing for the mind to stick. It’s accurate, sure, but it’s going to take serious effort for people to figure it out.
Now try this explanation. “A variable is like a named box where you can put information in.” Before all the technical geeks jump on my throat, please bear with me, at least past the “Exploration” section (then I’ll have a 200 yard headstart, just kidding). The explanation continues, “You can have a box named ‘myName’ and put the word ‘James’ in it by writing ‘myName=”James”’.” Now the explanation makes much more sense. “Ohhhh… so a variable is like a box you can store information in. That makes sense.”
Having these metaphors not only strengthen our understanding of a concept, it makes it more fun. It’s the novel relationship that brings about an easy understanding. Instead of saying a “A stack (it’s a type of data structure) is First In Last Out. First in last out. FIFO, FIFO,” trying to drill it in your head, you can just remember “A stack is like a pancake stack.” You can’t get to the bottom pancake until you eat the top ones. If you want to extend your box analogy, just imagine a stack of boxes. You certainly can’t open the bottom box until you take off all the top ones. That’s actually how a data structure stack works. You can’t access a variable on the bottom of a stack until you “pop” all the other ones off.
Metaphors are fun. They help us remember. You know why Reddit’s subreddit, ExplainLikeImFive and ExplainLikeIAmA, are so popular? It’s because through metaphors, concepts are more accessible, digestible, and easy to remember. Almost every ELI5 explanation involves a metaphor, every ELIAMA IS a metaphor. Browse it sometime to check out how creative some people are with explaining concepts, and how easy it is to remember certain things because of how well things fit.
Of course your metaphor isn’t perfect. It doesn’t even have to be good. That’s where exploration comes in. In the exploration stage, you test your model. You poke you model a bit, see what happens. Does it collapse? Does it stand up to your tests? Where are do your metaphors fall through? Where do they shine?
The most common method of exploration is doing problem sets. You take your beliefs about a certain concept, and use it to answer questions. There, you’ll find exceptions to what you thought was the rule. You’ll find rules to things you thought were exceptions. You’ll find inconsistencies in your model, and you’ll learn to fix your model until it’s as sturdy as a fort.
After you do problem sets, or maybe while doing problem sets, you should do some self-directed exploration. Feed your curiosity. If you followed my analogy earlier of using a box to represent a variable, ask yourself some of these questions (I’ve provided some methods to test them out and find out the answers. They are not exhaustive. There are other ways to answer and explore these questions, and of course, come up with new ones):
How big is the box? Is there a limit on the amount of things you can put in it? You can find out by putting in a really large number into your variable. You can ask someone what would happen. You can have many of boxes and check your computer memory space. You can google it. Preferably, you’d ask a friend.
What happens if I put another item in the box? Does it take out the original item and put in a new one? Does it store both items? Try assigning variable names to different things and printing them out on your computer. Do you have the original item, or do you have the new one? Do you have both? Then ask yourself this question: “Is this true for all items you put in?” What if you put a rope that’s tied to another box? I won’t answer that right now, it has to do with pointers and references.
What would happen if I put a box in a box? Is the box big enough? You can try to answer this by assigning two variables, A and B, to 1 and 2 respectively. If we say that “=” means putting a thing in another box, by metaphor, “=” means “put box B in box A.” See what happens when you print a, does it print out “B,” “1,” “2,” or “ERROR”? Just for this question, I’ll tell you that it’ll print out “2.” Then you’ll ask yourself, “Well, in that case, is box B in box A or not?” and “Did box B transfer its 2 to box A?” Then you’ll print out box B’s content. “2.” Phew, it seems like box didn’t transfer its content to box A. The first question you may not be able to answer by conventional programming, you’ll have to Google it or ask someone.
There are so many more questions to ask about the metaphor of boxes to describe variables. Jumping back to metaphors for a second, a student would not have conceived of these questions beforehand if he had not imagined and visualized variables as named boxes. The student would have fumbled around with figuring out what a variable exactly is without allowing his curiosity to guide his exploration. These example questions are legitimate questions about variables, whether they are in the form of formal terminology and language, or by metaphors. They are not “dumb” questions. If a metaphor helps the student to understand the concept and think about it better, by all means he should use the metaphor. By the end (if there is one) of the questions, you’ll have a pretty special type of box for a metaphor, and at one point, in which you’ve encapsulated and understand the subject enough, you won’t need the metaphor anymore.
Use this opportunity to create some of your favorite metaphors. Your metaphors are yours to keep. It’s like having an inside joke with yourself. You’ll be able to see the concepts you’re learning much clearer. You’ll be able to enjoy constructing a sound metaphor that is bulletproof. Then you’ll be able tell your friend (your peer), “Hey, I just realized that arrays are like vending machines.” while provide a reasonable argument for it.
A Coherent Meta-Example
All right, all right. I’m about to drop some wisdom in here. Since you’re reading my guide and you’re trying to learn this methodology, I’ll use my (really Scott Young’s) system to teach you the system.
Ok, ok. Learning a concept is like playing Pokemon. First you have to catch a Pokemon. The process of catching a pokemon is the process of visceralization. You see it, you claw at it, you poke it, you deconstruct it, then you encapsulate it into a pokeball. Once it’s yours, you have a basic model. You take your pokemon and you train it and nurture it. You feed it and scoop up its poop and despite that fact you might still take it to bed with you in your sleeping bag. You learn its skills, its shortcomings, and its stats. You work on it and spend time with it. Ok ok, now you take your pokemon up for the test. In a tribute to the 1st generation pokemon, it’s the Pewter Gym, or Brock’s gym. Then you say “Go Pikachu! Fight Onix!” If you defeat the leader, great! You’ve earned your badge, and you’ve mastered the concept. If not, you train your pokemon some more and try again. If your pokemon, or model, fails too many times, maybe it’s time to let it go. Maybe it took you 5 tries to realize that Onix is impervious to electric type Pokemons. So you let go of your Pikachu, pick up a new pokemon, preferably Squirtle, and try again. By the time you defeat the gym leader, you’ll have a fantastic new Pokemon, and a neat badge to show how awesome you are (online courses are all about badges these days. They probably caught on by now).
Below is a roadmap based on my personal computer science learning journey and UC Berkeley’s computer science curriculum. It’s based on “semesters,” but that really doesn’t mean much besides a general chronological order to things
Semester 1 – Practical Programming
You will learn how basic programming concepts as well as dip your feet in the world of programming. I find “Learn Python the Hard Way” the best at teaching semester 1.
Use this checklist to make sure you learn all the concepts. Don’t move on until you mastered all of these concepts:
- For Loops
- Lists and Arrays
- Dictionaries or Hash Tables
- Debugging methods
- Classes and Objects
- Basic Recursion
Semester 2 – Data Structures & Discrete Mathematics
Python is too encapsulated to learn about data structures. Java is a better way to go about it. I find UC Berkeley’s CS61B Course Page the best way to go about it. You’ll find resources, materials, and exercise about the class. You’ll implement the things you take for granted from Semester 1 in Java. Email me and I’ll even try to get you into the Piazza group, which will have a live support community of UCB students taking the class (it’s super duper helpful when other people are keeping you on track).
Here’s semester 2’s checklist:
- Objects and Arrays in Java
- Hash Tables in Java
- Trees (Binary Trees and Binary Search Trees)
- Stacks and Queues
- Sorting (QuickSort, MergeSort, SelectionSort, and InsertionSort are the most important ones)
- Time and Space complexity
Also there’s discrete math, which provides a mathematical backing to your computer science education. Also not really necessary, I find it helpful in building your repertoire of problem solving tools and tactics.
Class and Checklist:
- Probability and Counting
- Load balancing
- RSA and Cryptography
- Computability and Self Reference
With the knowledge you have by the end of your second semester, you could probably score a basic internship for the summer or the time being. If you were lost to where you are suppose to go in semester 1 and 2, you should have a general sense of which step to take next by now. So I won’t give you any more roadmap, you can proudly call yourself a “computer scientist” now. You also have the license to tell corny computer science jokes, like,
Q: How did the programmer die in the shower?
A: He read the shampoo bottle instructions: Lather. Rinse. Repeat.
If you don’t get this now, come back to this after semester 1 as a treat to yourself, you’ll enjoy it :)
I hope this guide has been helpful for you. Now I must warn you, this guide is not “the secret” to learning computer science. It is not just sunshines and rainbows here on out just because I’ve taught you “insider tricks to navigating away all the difficulties”. You WILL have hardship. You WILL have frustration. You’ll have a moment where you look everywhere for help, even here, and not be able to find it. This guide is not meant to teach you how to avoid pain and take “the easy path,” it’s meant for you to take the hard path but enjoy the adventure while you’re there. One night, probably at 4 or 5 or 6am in the morning, when you’re stuck in the library, or your dorm room doing a problem set that’s due the next day. You’ll be tired, hungry and gross, and you’ll feel lost and hopeless. But then you’ll think back to this guide, think about this warning, the warning I’ve made, “You WILL have hardship,” and you’ll tell yourself, “Hey, it’s ok that I’m frustrated, it’s ok that I’m lost. I was prepared for this difficulty to happen when I began my journey as a computer scientist, and I am prepared for it now.” Good luck to you all. You will all succeed if you believe you will.
I’ve spent 30+ hours writing this guide, not including countless hours reading books, watching videos, and experimenting with learning styles and techniques, all while being a computer science intern this summer. If you’ve enjoyed it, feel free to drop me a line saying thanks. The best emails are the ones who are fundamentally impacted by what I write, for, it is the only reason I write. If you have questions, comments, or concerns, reach out to me and I’ll try my best to help you out, if not direct you to someone who can.
My email: firstname.lastname@example.org
My Phone Number (My friend said this would be a good idea): 650-388-0628
References listed in a poorly, non-MLA format. Starred references are materials I recommend you read if want to further explore the strategies for accelerated learning.
Four Hour Chef by Tim Ferris
Mastery by Robert Greene
Holistic Learning by Scott H Young*
Accelerated Learning by Brian Tracy
Art and Craft of Problem Solving by Paul Zeitz*
Inner Game of Tennis by Timothy Gallwey*
Do Grad Students Remember Everything They Were Taught? answered by Mark Eichenlaub*
The User Illusion by Tor Norrentranders
Cracking the Coding Interview by Gayle Laakmann
How to Solve It by George Polya*
Harvard 1504: Positive Psychology by Tal Ben-Sharar (Used his concepts to write my conclusion)
Fun Programming Challenges on ProjectEuler.net