<p>Hey guys! For those of you who don't recognize my handle, I graduated high school in 2011. During the summer before my senior year, I signed up for AP Computer Science A on Florida Virtual School on a complete whim - I had no prior programming experience before taking the class. I enjoyed the class tremendously, got a 5 on the exam, and am now a computer science major at my university. I've got a few days of downtime, so I figured I'd try to contribute something of value to the community here.</p>
<p>I personally believe the APCS exam to be one of the strongest that the College Board offers. The exam is designed such that, with the exception of properties of searches and sorts, a student cannot memorize his or her way through the material. I found that the exam rewarded critical thought and understanding, whereas other exams are criticized for promoting memorization of both facts and of teachers' opinions.</p>
<p>With that being said, the APCS curriculum is extremely limited in scope. I've found that students in my computer science classes had more experience and knowledge than I did. That is because they either took the AP Computer Science AB exam, which covered a great breadth of material, or they'd simply programmed more than I did in high school. The field of computer science is extremely interesting, and I don't doubt that there are more students out there who want to get a head start on everything.</p>
<p>Allow me to start by offering a couple of reasons why an on-the-fence student ought to make the foray into learning computer science, whether by taking the AP class, self-studying for the AP exam, or simply self-studying the field for intrinsic pleasure. If you are already sold, feel free to skip to the next section.</p>
<p>Computer science is seriously interesting. In today's day and age, almost everything we use is run by some sort of computer. Haven't you wondered how everything works? I'd found that, even after simply finishing the APCS curriculum, I had a good understanding of how real-world problems could be solved via programming. I had a good grasp on how computers affected our everyday lives.</p>
<p>Computer science is a lucrative field. A first-year programmer at Facebook earns</a> more money than a first-year investment banking analyst at a bulge bracket, while performing work that most people would find significantly more engaging and productive to society than being a banking analyst. Moreover, start-ups are being constantly funded or acquired at great profits.</p>
<p>Computer science is growing. I believe in the concept of exponential growth, commonly known as Moore's Law. We're just hitting the knee of the curve. Expect technological progress to significantly speed up in the next 5 to 10 years.</p>
<p>Computer science students are no longer stereotyped as losers. The common CS stereotype is now gone. In fact, there's been a growing [brogrammer[/url</a>] sentiment over the last year. The other CS students I know get plenty of respect from their peers.</p>
<p>Computer science makes you a better thinker. When presented with novel problems in computer science, the process of brainstorming a solution, doing it incorrectly, and fixing your mistakes truly improves your problem-solving abilities. Moreover, thinking recursively is one of the best ways to expand your mental capacities. I've noticed that I've been able to think better about problems in all subjects thanks to taking computer science. As implied, I believe that this is more because computer science requires lots of thought, which has a positive externality on your capabilities for other subjects.</p>
<p>With that being said, let us assume that you have finished the AP Computer Science A curriculum, a common starting spot for students. Let us further assume that you want to continue learning about computer science and programming. There are generally several tracks people want to go down (these tracks are not mutually exclusive) - programming hack-ish stuff for a start-up, theoretical computer science, and how computers work at the hardware level. However, there are some core points of computer science glossed over in APCS that I'm going to highlight here.</p>
<p>What should everyone know if they wish to continue?</p>
<p>Asymptotic analysis. Computers have advanced to the point where we are not concerned with the speed of a particular function. The MacBook Pro can perform something like 750 million instructions per second. This lends itself conveniently to our needs because we instead concern ourselves with the rate of growth of a method or algorithm.</p>
<p>This sounds abstract, so let us look at an example - here's some pseudocode for selection sort.</p>
<p>
let N = the length of the array
for (int j = 0; j < N - 1; j++) {
for (int k = j + 1; k < N; k++) {
if (array[j] > array[k]) {
swap array[j] and array[k]
}
}
}
</p>
<p>We can assume that the inner instruction, swapping the two array elements, takes some constant time to run. This constant varies from machine to machine and based on other factors (how many applications you have open, etc.) so there's really no point to try to pin it down.</p>
<p>However, we know that our input array is of some length N (we assigned that variable ourselves). This means that N will grow as the array grows in size. Since the size of the array essentially controls how long it will take for selection sort to sort an array, we can say that selection sort's running time is a function of its input array length.</p>
<p>Moreover, let's do a bit of math here. Leonhard Euler taught us that the sum of all integers from 1 to x equals x*(x+1)/2. Selection sort essentially sums integers from 1 to (N-1). That's because when j = 0 in the outer for loop, the inner for loop counts k = 1, 2, 3, up to N-1. When j = 1, the inner for loop counts k = 2, 3, up to N-1.</p>
<p>This means that, in the worst possible scenario, selection sort will perform (N-1)*N/2, or N^2/2 - N/2 swaps, of which each swap runs in some constant time. Since this is a second-degree polynomial, we throw away the constant and the lower terms and say that selection sort runs asymptotically in N^2 time.</p>
<p>This means that, as the size of the array increases sequentially, selection sort's running time will increase at a parabolic rate.</p>
<p>We can also say that selection sort is O(N^2). This is called Big-Oh notation. Formally, it means that there exists an N and a c, such that, for all x ≥ N, f(x) < x^2. Informally, it means that x^2 is an upper bound on the growth rate of selection sort.</p>
<p>There's a lot more to asymptotic growth. Some functions can be pretty nasty to figure out. I'd recommend studying up on Big-Oh, Big-Omega, Big-Theta, recurrence relations, recurrence trees, induction, and the telescoping method. These can all be found via simple Google searches, or in any introductory algorithms textbook.</p>
<p>Asymptotic analysis is EXTREMELY important to understand for anyone who wishes to continue in computer science because it completely governs what algorithms you choose in which situations. You can inspect code and determine why it's inefficient. (In our case, selection sort is useful if we're sorting an almost-sorted array. Insertion sort is the most useful if we want to check to see if an array is sorted. Otherwise, we might want to use quicksort, which is quicker for the average input.)</p>
<p>Data structures. The AP Computer Science A absolutely skimps on data structures that are not arrays or ArrayLists. This is shameful. It is extremely important to understand how to implement and how to use trees, heaps, stacks, queues, sets, hash tables, and graphs (for a start). Not only are these all intrinsically interesting, but they're quite useful for programming. Moreover, interviewers love to ask about trees, queues, and graphs.</p>
<p>Instead of spending time explaining why each data structure should be learned, [url="<a href="http://opendatastructures.org/%22%5DI'll">http://opendatastructures.org/"]I'll</a> let the experts do the talking](<a href="http://www.businessweek.com/articles/2012-03-01/the-rise-of-the-brogrammer%22%5Dbrogrammer%5B/url">http://www.businessweek.com/articles/2012-03-01/the-rise-of-the-brogrammer).</p>
<p>Be a code reader. Get your hands on some good code in a new language and try reading it. You become fluent in a foreign language by reading, writing, speaking, and listening. You ought to be reading even more code than you write when picking up a new language. I refuse to write in a new language before I've read a ton of code in it (I'm thinking several thousands of lines). It teaches you about the niches of that particular language, and it helps you get acclimated to the new syntax.</p>
<p>Test cases. I had no idea what a test case was until I took my first college computer science class. Test cases are independent pieces of code that you write to compare the expected output of a method to the actual output of a method. Proper programming style mandates that you write test cases for a method before wrting the method itself, and that you test all methods you write, especially helper methods.</p>
<p>Test cases are beneficial for three reasons. First of all, they let you know that any method you write works in the first place. Next, they let you check edge cases - for example, checking an empty array or a null array on a sort, negative numbers on a computational function that takes positive numbers, etc. These are generally the inputs that screw things up. Finally, if you ever have to change something your code - which happens more than we'd like to admit! - having test cases is a great way to prove to yourself that you didn't break your program. If the test cases all still pass, then you didn't screw up.</p>
<p>I want to do start-ups.</p>
<p>A lot of computer science graduates go on to found or join small start-up firms. These firms often have Internet or mobile products, meaning that you should begin jumping into web development and mobile development.</p>
<p>Web frameworks. From my knowledge, the two most popular web frameworks are Django and Ruby on Rails. Django is based in Python, and Ruby on Rails is based in Ruby (that one was obvious). While I know little Django - although I can recommend this</a> tutorial on Django and this</a> one on Python, I'm pretty good with Ruby on Rails. I can recommend the</a> official RoR guide, Why's</a> Poignant Guide to Ruby, and [Railscasts[/url</a>].</p>
<p>You'll also want to pick up HTML, CSS, Javascript, JQuery, AJAX, and who knows what else. While I'm not yet fluent in these, I know my way around all five. What I've found is that I normally will Google how to do something, find an answer close enough to my needs, and jury-rig a solution. In fact, you'll find yourself Googling a LOT of stuff when programming in Rails or Django. It's just what happens. Rails doesn't give the most helpful error messages, so get good at looking up your problems. Someone else out there has had it before.</p>
<p>Mobile frameworks. Ah, iOS and Android development. I'm ashamed to admit that I know little iOS and no Android. (I'm taking an iOS development class next semester to change this.) What I do know of iOS is that its backbone, the Model/View/Controller paradigm, is very, very similar to Ruby on Rails - it's so similar that [url="<a href="http://www.rubymotion.com/%22%5Dsomeone">http://www.rubymotion.com/"]someone</a> wrote a development kit to write iOS apps in Ruby](<a href="http://railscasts.com/%22%5DRailscasts%5B/url">http://railscasts.com/).</p>
<p>iOS development is mainly done in Objective-C, a variant on C that can easily be picked up with Java knowledge. Android apps are written in Java, so you've already done the heavy lifting there.</p>
<p>General hack knowledge. Here, I use the term "hack" as in a solution hacked together, not at all in the sense of hacking into a computer. Good start-up programmers are generally good at the first kind of hacking. You gain this through experience. Most colleges host two-day "hackathons," during which teams of people see who can come up with the best idea or product in two days of intense programming. If you don't want to do this, simply try to program something useful in a few days. Successful start-ups solve an existing problem or fill an empty niche. I'm currently working on something pretty cool and novel for my university just for the experience of it.</p>
<p>Moreover, having these sorts of projects on your resume looks great when applying for any sort of a job. In the programming world, you gain respect based on the content you've put out there. You need to have published projects in order to be taken seriously on a job application. For a job in any other industry, it shows huge initiative and diverse interests.</p>
<p>I want to learn theoretical computer science.</p>
<p>Discrete math. You should be well-versed in discrete math and number theory. This means you'll be doing some proofs. If you've never been exposed to proofs before, don't worry - you have to start somewhere. Discrete math courses generally start with the idea of b divides a. By definition, b divides a means that there exists an integer q such that a = qb. You can progress very far with only this, up to the point where you can prove that the RSA algorithm works. That's pretty cool.</p>
<p>Functional programming. Languages like Java are known as imperative languages. This means that when you write a program in Java, you're telling the computer what to do. It seems pretty natural, and it's easy to pick up. You're just writing instructions!</p>
<p>On the other hand, there exists a paradigm known as functional programming. Functional languages are based around the idea of mathematical functions. Functionl languages try to avoid variables changing their value as much as possible. In Java, you can iterate through a for loop by using a counter variable and incrementing it. In a functional language, you try to avoid this as much as possible and instead use recursion for almost everything.</p>
<p>Functional programming leads to some pretty cool features that are extremely useful. Defining data structures can often be much simpler in functional languages (after you've studied up on your data structures, compare a binary tree in Haskell to a binary tree in Java). Moreover, in functional languages, you can pass methods as inputs to methods. That's pretty cool, and you simply cannot do that in Java (although they're adding it to Java 8 because it's such a useful feature). It's a huge time and space saver, and it also adds to code comprehension. Finally, functional languages permit infinite data structures because of something called lazy evaluation.</p>
<p>I first learned functional programming in OCaml, a nifty little language that's not very widely used. More popular functional languages include Lisp, Scheme, Haskell, Scala (a derivative of Java), and F# (a derivative of C#, which means it runs on Microsoft's .NET framework). While I don't have tutorials for most of these, you can work</a> through a well-written introduction to Haskell, or you can check out my class's notes</a> and homeworks for OCaml.</p>
<p>The theory of computation. The hallmark of theoretical computer science involves topics such as Turing machines, the halting problem, finite-state machines, and P = NP. These are topics to be learned about in any basic class on automata. While I know little (I'm taking the class next semester), I can offer a link</a> to the standard textbook on computability.</p>
<p>I want to learn how computers actually work.</p>
<p>Abstraction. Hardware is an extremely interesting topic. I've found that the primary theme of how a computer work is abstraction. At the very lowest level, a computer is electrons moving around. We can abstract away individual electron motion by thinking about analog circuits with voltage and resistance. By combining resistors in specific ways, we can abstract away having to worry about specific voltages and instead think about low voltage or high voltage - binary. This takes us from thinking about circuits in the context of AP Physics (what's the current through this lightbulb) to the context of binary functions via logic gates.</p>
<p>With logic gates, we can create sequential (infinitely cycling) circuits that can store a specific bit - they can store a 0 or a 1. Having made these "flip-flops," we no longer have to consider every logic gate, but we can instead think about a flip-flop as a discrete entity. When we combine many of these together, we create what is known as an n-bit register. If we can store 16 bits, it's a 16-bit register. Combining registers in tandem allows us to store large amounts of data, which is where we get computer memory from - at which point we no longer have to worry about registers, flip-flops, logic gates, resistors, or electrons.</p>
<p>Your university should offer a class in the electrical engineering department on this.</p>
<p>Low-level languages. To understand how a computer works requires an understanding of machine code, assembly, and C. This is yet another class I'm taking next semester, so I can't comment too much on it. While I've found that the material is extremely interesting to know, it's not so useful to what I want to do in the future, so I haven't self-studied it.</p>
<p>Final Remarks</p>
<p>A pretty common question is, "Where do I go now that I've finished AP Computer Science A?" I believe that while APCS is a great introduction to programming, the class does a poor job at showing students what's next. It has great merit in teaching students strong fundamentals of the subject, and it succeeds in making students ask, "why?" However, it fails at guiding students to answer that "why?" question.</p>
<p>As I've pointed out, there are several different paths down which a student can now take. I suspect that most will want to program for web and mobile. As I said, the best way to do this is simply to have at it. Experiment around. Learn how to use Terminal. Screw up. Don't be afraid to make mistakes. Publish your products on the Internet (especially on an open-source host such as Github), even if they're not fully polished or don't fully work. As Steve Jobs said, always be thirsty.</p>
<p>One final point - there's a difference between computer science and simply programming. Anyone can pick up a language and make a product. As a computer scientist, you will understand every algorithm you use and why you picked it over an alternative. You will write concise, beautiful code. You will comment it well, format it to be readable, and write proper tests for it.</p>
<p>As you pick up a second and a third language, you'll instantly be able to see the similarities across all languages and the differences between them. These similarities and differences will be much deeper than mere syntax. In fact, the syntax of a language should be irrelevant to you. With experience, you'll be able to read a few lines of a new language and write a program in it just based on what you know of computer science, not what you know of Java or Python or Ruby. A friend and I wrote a pretty useful script in R for a probability project just by reading a few dozen lines of code in R to get the hang of the syntax. You can easily be in this same situation.</p>
<p>Computer science is beautiful because you can create something truly amazing with relatively little background experience. How long does one have to study mathematics to prove something novel? How long does one have to carefully analyze classical music to write a symphony? How long must one work at physics to be able to derive the Standard Model? In computer science, you can do powerful things very quickly. You can add true value to society with nothing but a good idea and the knowledge to program it.</p>
<p>I hope that everyone reading this finds computer science as inspiring and as useful as I do. If you have any questions about CS or programming, feel free to ask me on this thread or to private message me. I still come onto these forums a year after graduating high school because I love helping out. If I've missed anything really useful for a newly minted AP Computer Science A alumnus to learn, feel free to post about it on here.</p>