This post is for a guide for understanding Core Computer Science topics
The best way to master Computer Science is to read few good books on the topic. Programmers Don’t Read Books — But You Should These are some of the books you can start with
- Cormen’s Introduction to Algorithms
- Data structures and Algorithms – Aho, Hopcroft, Ullman
- Programming Pearls – Bentley
- How to solve it by computer – Dromey
Cormen’s book is simply brilliant, it makes you understand every details of Algorithms. In addition to this book I strongly recommend you to see the video lectures from MIT. The lectures are given by Liesersonand Erik demaine. The lectures are absolutely brilliant.
Quick Intro to various topics
Hands on tutorials
Internals : Gustavo Duarte explains in detail about various topics
Linux is a well designed sytem and learning some internals linux will help a lot in understanding how systems are designed in real world
(Thanks to Vijay D’Silva’s brilliant answer incstheory.stackexchange.com . Thanks to The Phrygian Capfor summarizing)
Links based on linux 2.6:
- Linked lists, doubly linked lists, lock-free linked lists.
- B+ Trees with comments telling you what you can’t find in the textbooks.
- Priority sorted lists used for mutexes, drivers, etc.
- Red-Black trees are used are used for scheduling, virtual memory management, to track file descriptors and directory entries, etc.
- Interval trees.
- Radix trees, are used for memory management, NFS related lookups and networking related functionality.
- Priority heap, which is literally, a textbook implementation, used in the control group system.
- Hash functions, with a reference to Knuth and to a paper.
- Some parts of the code, such as this driver, implement their own hash function.
- Hash tables used to implement inodes, file system integrity checks, etc.
- Bit arrays, which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4.
- Semaphores and spin locks.
- Binary search is used for interrupt handling, register cache lookup, etc.
- Binary search with B-trees.
- Depth first search and variant used in directory configuration.
- Breadth first search is used to check correctness of locking at runtime.
- Merge sort on linked lists is used for garbage collection,file system management, etc.
- Bubble sort is amazingly implemented too, in a driver library.
- Knuth-Morris-Pratt string matching.
- Boyer-Moore pattern matching with references and recommendations for when to prefer the alternative.
- Computer Architecture – A Quantitative Approach – Hennessy and Patterson
- Advanced Computer Architecture – A design space Approach – by Sima , Fountain, Kacsuk
- Computer Architecture – William Stallings
- Computer Systems – A programmers perspective Randal E. Bryant / David R. O’Hallaron
Databases and File Systems
- Database Systems – Jeff. Ullman
- File Structures – Michael Folk et.al
- Computer Networks – Larie L Peterson , Bruce Davie
Coding Interview Prepartion
Books like “Programming Interviews Exposed” and “Cracking the Coding Interview” are best. There are also many good blogs on the subject.
- Programming Contests – Codesprints – Interviewstreet
- Programming Interviews
- Exercises in the area of design and analysis of Algorithms
- World of Seven – Methods to Solve – Volume 1
- LemonSquash: Puzzles
You can signup for courses offered by Coursera and watch video lectures.
Most people find the task of reading books, courses to be daunting and don’t take the first step. To keep yourself motivated to take that first step, you can follow few blogs such as paulgraham, joelonsoftware and also technical people e.g thegeekstuff (thegeekstuff) on Twitter. But blogs are just first steps. The most helpful method is to have a motivating project at hand and to learn the necessary stuff required for that. There are lot of good projects.You can also participate in forums, discussion groups and meetups to interact with fellow tech enthusiasts. For CS topics, we have a tech forum on Facebook, with around 18,000 members, and lot of people from research and academics. I originally started this forum, but now it has taken life on its own with lot of prominent people like PhD scholars and book authors contributing.
Most people find difficult to read entire books or watch video lectures, they just have time in chunks say 2-3 hours. Unless the course is well structured, it is difficult to complete the course by breaking it up. Learning new skills is time consuming because currently there are no good websites that help in adaptive learning or structure the course according to specific needs of the user. Most of the current websites are good, if you already know some basics about the topic, but what is missing is the perspective from a newbie. At NalandaU, we give a good plan for learning a particular topic. We manually aggregate the best content on the web for a particular topic. We validate our contents by asking feedback from freshers – if they could follow our lesson plan. We believe this kind of adaptive learning can shorten the time taken to learn new skills. Courses are structured using hyperlinks of concepts rather than bookish linear way
This list is meant to be a both a quick guide and reference for further research into these topics. It’s basically a summary of that comp sci course you never took or forgot about, so there’s no way it can cover everything in depth. It also will be available as a gist on Github for everyone to edit and add to.
Computer Science for the self taught programmer
Great Ideas of Computer Science
Talk by Director of Microsoft Research. Gives a good analogy about Cryptography and Diffie Hellman key exchange