Computer Science Roadmap¶

• Roadmap: https://roadmap.sh/computer-science

Deep-Dive Sections¶

• 01. Operating Systems — processes/threads, memory management, scheduling, file systems, virtual memory, system calls
• 02. Networking — TCP/IP, HTTP, DNS, TLS/SSL, OSI model
• 03. Database Internals — B-tree storage, LSM trees, MVCC, WAL, query planning
• 04. Compilers — lexer, parser, semantic analysis, optimizer, code generation
• 05. Computer Architecture — CPU, cache hierarchy, pipeline, NUMA, vectorization

Companion roadmaps: - Data Structures & Algorithms — algorithmic foundations - System Design — applying CS at the architecture level

1. Pick a Language¶

• 1.1 Python
• 1.2 Go
• 1.3 C#
• 1.4 C++
• 1.5 C
• 1.6 Java
• 1.7 Rust

2. Data Structures¶

• 2.1 Array
• 2.2 Linked List
• 2.3 Stack
• 2.4 Queue
• 2.5 Hash Table
• 2.6 Heap

2.7 Tree¶

• 2.7.1 Binary Tree
• 2.7.2 Binary Search Tree
• 2.7.3 Full Binary Tree
• 2.7.4 Complete Binary Tree
• 2.7.5 Balanced Tree
• 2.7.6 Unbalanced Tree

2.8 Graph¶

• 2.8.1 Directed Graph
• 2.8.2 Undirected Graph
• 2.8.3 Spanning Tree

2.9 Representation¶

• 2.9.1 Adjacency List
• 2.9.2 Adjacency Matrix

3. Asymptotic Notation¶

3.1 Big O¶

• 3.1.1 Constant
• 3.1.2 Logarithmic
• 3.1.3 Linear
• 3.1.4 Polynomial
• 3.1.5 Exponential
• 3.1.6 Factorial

3.2 Big-Theta¶

3.3 Big Omega¶

3.4 Common Runtimes¶

4. Common Algorithms¶

4.1 Sorting¶

• 4.1.1 Bubble Sort
• 4.1.2 Selection Sort
• 4.1.3 Insertion Sort
• 4.1.4 Heap Sort
• 4.1.5 Quick Sort
• 4.1.6 Merge Sort

4.2 Tree¶

• 4.2.1 Pre-Order Traversal
• 4.2.2 In-Order Traversal
• 4.2.3 Post Order Traversal
• 4.2.4 Breadth First Search
• 4.2.5 Depth First Search

4.3 Graphs¶

• 4.3.1 Breadth First Search
• 4.3.2 Depth First Search
• 4.3.3 Bellman Ford's Algorithm
• 4.3.4 Dijkstra's Algorithm
• 4.3.5 A* Algorithm

4.4 Recursion¶

• 4.4.1 Tail Recursion
• 4.4.2 Non-Tail Recursion

4.5 Searching¶

• 4.5.1 Binary Search
• 4.5.2 Linear Search

4.6 Caches¶

• 4.6.1 MFU Cache
• 4.6.2 LRU Cache
• 4.6.3 LFU Cache

4.7 Greedy Algorithms¶

• 4.7.1 Dijkstra's Algorithm
• 4.7.2 Huffman Coding
• 4.7.3 Kruskal's Algorithm
• 4.7.4 Ford-Fulkerson Algorithm
• 4.7.5 Prim's Algorithm

4.8 Back Tracking¶

• 4.8.1 Finding Hamiltonian Paths
• 4.8.2 Solving N Queen Problem
• 4.8.3 Maze Solving Problem
• 4.8.4 The Knight's Tour Problem
• 4.8.5 Rabin-Karp Algorithm

4.9 String Search & Manipulations¶

• 4.9.1 Search Pattern in Text
• 4.9.2 Suffix Arrays
• 4.9.3 Substring Search
• 4.9.4 Brute Force Search
• 4.9.5 Robin-Karp
• 4.9.6 Knuth-Morris Pratt
• 4.9.7 Boyer-Moore

4.10 Endianness¶

• 4.10.1 Big Endian
• 4.10.2 Little Endian

4.11 Floating Point Math¶

4.12 Unicode¶

4.13 ASCII¶

4.14 Character Encodings¶

4.15 Bitwise Operators¶

5. Common UML Diagrams¶

• 5.1 Class Diagrams
• 5.2 Usecase Diagrams
• 5.3 Activity Diagrams
• 5.4 Statemachine Diagrams
• 5.5 Sequence Diagrams

6. Design Patterns¶

• 6.1 GoF Design Patterns
• 6.2 Architectural Patterns
• 6.3 Dependency Injection
• 6.4 Null Object Pattern
• 6.5 Type Object Pattern

7. Complexity Classes¶

• 7.1 P
• 7.2 NP
• 7.3 P = NP
• 7.4 Co-NP
• 7.5 NP Hard
• 7.6 NP Complete

7.7 Travelling Salesman Problem¶

7.8 Knapsack Problem¶

7.9 Longest Path Problem¶

8. Tries¶

9. Balanced Search Trees¶

• 9.1 AVL Trees
• 9.2 Red / Black Trees
• 9.3 2-3 Search Trees
• 9.4 2-3-4 Trees
• 9.5 K-ary / M-ary Tree
• 9.6 B-Tree

9.7 K-D Trees¶

9.8 Skip Lists¶

10. Databases¶

10.1 SQL vs NoSQL Databases¶

10.2 Normalization / Denormalization¶

10.3 Entity-Relationship Model¶

10.4 DDL, DML, DQL, DCL¶

10.5 Locking¶

10.6 ACID Model¶

10.7 BASE¶

10.8 CAP Theorem¶

10.9 PACELC¶

10.10 Indexes¶

10.11 Views¶

10.12 Transactions¶

10.13 Stored Procedures¶

10.14 Database Federation¶

10.15 Replication¶

10.16 Sharding¶

11. Networking¶

• 11.1 OSI Model
• 11.2 TCP/IP Model
• 11.3 DNS
• 11.4 HTTP
• 11.5 TLS & HTTPS
• 11.6 Sockets

12. Security¶

• 12.1 Hashing / Encryption / Encoding
• 12.2 Public Key Cryptography
• 12.3 Hashing Algorithms
• 12.4 OWASP Top 10

13. How Computers Work¶

• 13.1 How CPU Executes Programs
• 13.2 Registers and RAM
• 13.3 Instructions and Programs
• 13.4 CPU Cache
• 13.5 How Computers Calculate

14. Processes and Threads¶

• 14.1 Process Forking
• 14.2 Memory Management
• 14.3 Lock / Mutex / Semaphore
• 14.4 Concurrency in Multiple Cores
• 14.5 Scheduling Algorithms
• 14.6 CPU Interrupts
• 14.7 Processes vs Threads

15. System Design¶

• 15.1 Horizontal vs Vertical Scaling
• 15.2 Load Balancing
• 15.3 Clustering
• 15.4 Caching
• 15.5 CDN
• 15.6 Proxy
• 15.7 CAP Theorem
• 15.8 Queues
• 15.9 Architectural Styles
• 15.9.1 REST
• 15.9.2 GraphQL
• 15.9.3 gRPC
• 15.10 Cloud Design Patterns
• 15.10.1 Long Polling
• 15.10.2 Short Polling
• 15.10.3 Web Sockets
• 15.10.4 SSE

15.11 Basic Math Skills¶

• 15.11.1 Probability
• 15.11.2 Combinatorics