Computer Science for All: The Foundations
We understand that there are a lot of enthusiastic programmers out there, who might not be Computer Science majors, but greatly interested in this field. This blog is partly in response to the requests of those who e-mailed us, asking for tutorials and guidance about how Non-CS majors could get started with Programming and Computer Science.
We’d like HackerRank to be a zone which can be a significant component of your self-learning experience. We’d also like to make suggestions and guide you as you explore Computer Science and Programming. This is very easy in this age of online courses, its equally easy to get lost and confused since the problem at hand is one of too much choice. Effective programming isn’t just about cranking out code, it also involves a strong understanding of Computer Science fundamentals, and for anyone aspiring to excel in this field, here are a few topics and subjects which you must know.
Data Structures and Algorithms
This is the foundation for much of Computer Science.
- The use of routine Data Structures such as Arrays, Lists, Stacks, Queues, Trees and Graphs.
- Basic Algorithms for common tasks such as sorting and searching.
- Tweaking around and building more complex data structures, as required. It is unlikely that a complex task can be solved using just one simple data structure.
- This might be difficult, but given that we currently live in an era of parallelism and multi-cores, a good understanding of parallel data structures and algorithms is important. The standard 1-Processor algorithm should be understood as the base case of these parallel algorithms.
- Designing and analyzing algorithms, their complexity and their lower and upper bounds.
- Different algorithmic approaches: Divide and Conquer, Dynamic Programming, Greedy Algorithms
Online Courses and Material:
Introduction to Algorithms at Udacity is a great starting point.
After that you could move on to the Coursera Design and Analysis of Algorithms courses, Part 1 and Part 2, which are a bit more rigorous on the Theory front.
At that point you might be able to enjoy and appreciate our own Algorithmic challenges at HackerRank. We have a large number of enjoyable problems related to sorting, searching, graph theory and NP Complete Problems. Trying these out, will help you apply your knowledge and sharpen your skills. We have memory limits and time limits in place, which will help you exercise your Algorithm Design skills to develop optimal or near-optimal solutions.
Theoretical Foundations of Computing: Discrete Mathematics and Automata Theory
Unlike traditional branches of engineering such as Electrical, Chemical or Mechanical Engineering, where much of the Mathematics involved is continuous domain in nature, i.e. Calculus based, Computer Science is heavily dependent on Discrete Mathematics and Discrete Structures. Number Theory, Sets, Recurrence Relations, Permutations and Combinations, Integer Properties, Graphs and Logic: these are some of the important sub-topics in Discrete Mathematics.
Automata is the study of States and State Machines. An Automata course will typically include State Machines, Deterministic and Non-Deterministic Finite Automata, Regular Languages, Regular Expressions, Grammars and Parsing, Turing Machines (the model of computing on which most programming languages are based) and Complexity Classes.
It is often tempting to dismiss these theoretical topics and topics which have little or no relation to the real world and industry, but that is very different from the truth. The construction of Programming Languages or the automated (partial) understanding of Natural Language would never have been possible without this theoretical knowledge.
Michael Sisper’s Introduction to the Theory of Computation is a great foundation book for Theory.
As far as Online Courses are concerned, Udacity’s Introduction to Theoretical Computer Science, Coursera’s Automata taught by Jeff Ullman, author of one of the most famous books in this field.
Once you have a decent understanding of various complexity classes, take a look at some of our NP Complete Challenges with a clearer understanding of why they don’t have polynomial time solutions.
Programming Languages: Creating a Compiler or an Interpreter, or both
A great starting point would be to build a basic recursive descent interpreter for a toy language. After that, you could move into deeper waters, and towards Compilers.
Quoting from an answer I wrote a while back on Quora
The thing about understanding Compiler Design; or by writing at least a small interpreter or a compiler is, that you gain a broad and reusable set of knowledge and skills across various areas of Computer Science and programming, which can be extended to many different areas. In some ways, writing a programming language is a quick and efficient top-down introduction to Computer Science.
You apply Automata, Regular Expressions, Context Free Grammars, Parsing Algorithms. You learn how to build a semantic checker, which teaches you how different languages with different scoping techniques work. You learn to put your knowledge of Data Structures into action. You finally learn how to generate machine code, which compels you to learn about the underlying system, Assembly Language, basic Computer Architecture, the execution cycle with which the OS runs a Computer Program. You get to apply your knowledge across a spectrum of areas and create something which requires a substantial amount of non-trivial programming. You might never have to build a Compiler after this, but you will often use one or more of the principles which you learnt while creating one.
For someone who is interested in getting started with Computer Science, just starting off with these three topics and picking them up well, will help you develop strong foundations in the subject, and will also make you confident. After that, you could move on to other critical topics such as Computer Architecture, Operating Systems, Networks and Databases.
I’d also like to add that there are many different ways in one might chart out a plan of action to “self-learn” Computer Science. There is no perfect answer to this. The above is just one recommended approach and one which I personally felt comfortable with. You might be more comfortable (or interested) in studying Computer Architecture or Operating Systems first. There are likely to be many amazing approaches and you should definitely choose the one which you feel most comfortable and enthusiastic about.