Computer Science Fundamentals

Cheatsheet Content

Data Structures Arrays Definition: Contiguous memory block storing elements of the same type. Access: $O(1)$ by index. Insertion/Deletion: $O(N)$ in worst case (shifting elements). Example: int arr[] = {1, 2, 3}; Linked Lists Definition: Collection of nodes, each storing data and a reference (link) to the next node. Types: Singly, Doubly, Circular. Access: $O(N)$ to find an element. Insertion/Deletion: $O(1)$ if position is known, $O(N)$ otherwise. Stacks Definition: LIFO (Last In, First Out) data structure. Operations: push(item) : Add item to top. $O(1)$ pop() : Remove item from top. $O(1)$ peek() : View top item. $O(1)$ Queues Definition: FIFO (First In, First Out) data structure. Operations: enqueue(item) : Add item to rear. $O(1)$ dequeue() : Remove item from front. $O(1)$ front() : View front item. $O(1)$ Trees Definition: Hierarchical data structure with a root node, child nodes. Binary Tree: Each node has at most two children. Binary Search Tree (BST): Left child Search/Insert/Delete: $O(\log N)$ on average, $O(N)$ worst case (unbalanced). Balanced Trees (AVL, Red-Black): Self-balancing to maintain $O(\log N)$ operations. Graphs Definition: Set of vertices (nodes) and edges (connections). Types: Directed/Undirected, Weighted/Unweighted. Representation: Adjacency Matrix ($O(V^2)$), Adjacency List ($O(V+E)$). Traversal: BFS (Breadth-First Search): Explores level by level. Uses a queue. DFS (Depth-First Search): Explores as far as possible along each branch. Uses a stack (or recursion). Hash Tables Definition: Maps keys to values using a hash function. Average Operations: $O(1)$ for insert, delete, search. Worst Case: $O(N)$ due to collisions. Collision Resolution: Chaining (linked lists), Open Addressing (linear probing, quadratic probing). Algorithms Sorting Algorithms Algorithm Time Complexity (Avg) Time Complexity (Worst) Space Complexity Bubble Sort $O(N^2)$ $O(N^2)$ $O(1)$ Insertion Sort $O(N^2)$ $O(N^2)$ $O(1)$ Selection Sort $O(N^2)$ $O(N^2)$ $O(1)$ Merge Sort $O(N \log N)$ $O(N \log N)$ $O(N)$ Quick Sort $O(N \log N)$ $O(N^2)$ $O(\log N)$ Heap Sort $O(N \log N)$ $O(N \log N)$ $O(1)$ Searching Algorithms Linear Search: $O(N)$ - checks each element sequentially. Binary Search: $O(\log N)$ - requires sorted data, repeatedly divides search interval in half. Graph Algorithms Dijkstra's Algorithm: Finds shortest paths from a single source to all other nodes in a graph with non-negative edge weights. $O((V+E)\log V)$ with Fibonacci heap, $O(E \log V)$ with binary heap. Floyd-Warshall Algorithm: Finds all-pairs shortest paths in a weighted graph. $O(V^3)$. Prim's Algorithm: Finds a Minimum Spanning Tree (MST) for a weighted undirected graph. $O((V+E)\log V)$ or $O(E \log V)$. Kruskal's Algorithm: Also finds an MST. $O(E \log E)$. Dynamic Programming Principle: Solves complex problems by breaking them into simpler overlapping subproblems and storing the results to avoid recomputation (memoization or tabulation). Characteristics: Optimal substructure, overlapping subproblems. Recursion Definition: A function calling itself to solve a smaller instance of the same problem. Base Case: Essential condition to stop recursion. Recursive Step: Solves a subproblem and combines with other results. Computer Architecture CPU Components ALU (Arithmetic Logic Unit): Performs arithmetic and logical operations. Control Unit (CU): Manages and coordinates CPU operations. Registers: Small, fast storage locations within the CPU. Cache: Small, fast memory between CPU and main memory to speed up access. L1 (fastest, smallest), L2, L3. Memory Hierarchy Registers > Cache (L1, L2, L3) > Main Memory (RAM) > Secondary Storage (SSD/HDD) Fetch-Decode-Execute Cycle Fetch: Instruction fetched from memory into instruction register. Decode: Control Unit interprets the instruction. Execute: ALU performs the operation; results stored in registers/memory. Pipelining Technique to improve CPU throughput by overlapping instruction execution steps. Operating Systems Process Management Process: An instance of a program in execution. Thread: A lightweight unit of execution within a process. Process States: New, Ready, Running, Waiting, Terminated. Context Switching: Saving state of one process/thread and loading another. CPU Scheduling Algorithms FCFS (First-Come, First-Served): Non-preemptive, simple. SJF (Shortest Job First): Optimal for minimizing average waiting time but hard to implement. Can be preemptive (SRTF). Priority Scheduling: Processes with higher priority execute first. Can lead to starvation. Round Robin: Preemptive, each process gets a fixed time quantum. Good for time-sharing. Memory Management Paging: Divides physical memory into fixed-size blocks (frames) and logical memory into same-size blocks (pages). Segmentation: Divides logical memory into variable-size segments based on program structure. Virtual Memory: Allows execution of processes not entirely in physical memory, using disk as an extension of RAM. Deadlock Conditions (Coffman Conditions): Mutual Exclusion Hold and Wait No Preemption Circular Wait Handling: Prevention, Avoidance (Banker's Algorithm), Detection and Recovery. Networking OSI Model (7 Layers) Physical: Raw bit stream over physical medium (cables, Wi-Fi). Data Link: MAC addresses, error detection, flow control (Ethernet, PPP). Network: IP addressing, routing (IP, ICMP). Transport: End-to-end connection, reliability, flow control (TCP, UDP). Session: Manages sessions, synchronization. Presentation: Data encryption, compression, formatting. Application: Network services to end-user (HTTP, FTP, SMTP, DNS). TCP/IP Model (4 Layers) Application: (OSI 5-7) HTTP, FTP, DNS. Transport: (OSI 4) TCP, UDP. Internet: (OSI 3) IP. Network Access: (OSI 1-2) Ethernet, Wi-Fi. Protocols TCP (Transmission Control Protocol): Connection-oriented, reliable, ordered. UDP (User Datagram Protocol): Connectionless, unreliable, fast. IP (Internet Protocol): Addressing and routing packets. HTTP (Hypertext Transfer Protocol): Web communication. DNS (Domain Name System): Translates domain names to IP addresses. DHCP (Dynamic Host Configuration Protocol): Assigns IP addresses automatically. Databases Relational Databases Concepts: Tables (relations), rows (records/tuples), columns (attributes/fields). Primary Key: Uniquely identifies a record in a table. Foreign Key: Links two tables by referencing a primary key in another table. SQL (Structured Query Language): For managing and querying relational databases. Normalization Organizing data to reduce redundancy and improve data integrity. Normal Forms: 1NF, 2NF, 3NF, BCNF. 1NF: Atomic values, no repeating groups. 2NF: 1NF + no partial dependencies. 3NF: 2NF + no transitive dependencies. ACID Properties (Transactions) Atomicity: All or nothing. Consistency: Valid state before and after transaction. Isolation: Concurrent transactions don't interfere. Durability: Committed changes are permanent.