📝 Page 1: Advanced Algorithms and Data Structures

Algorithm Analysis

Algorithm analysis is the process of finding the computational complexity of an algorithm. We

primarily focus on two aspects:
●​ Time Complexity: How the runtime of an algorithm grows as the input size (n) increases.
●​ Space Complexity: How the memory usage of an algorithm grows as the input size (n)
increases.​
We use Big O notation (O) to describe the upper bound of this growth. For example,
O(n2) indicates that the runtime grows quadratically with the input size.

Advanced Data Structures

●​ Heaps: A specialized tree-based data structure that satisfies the heap property: for a
min-heap, every parent node's value is less than or equal to its children; for a max-heap,
it's greater than or equal. Heaps are used to implement priority queues.
●​ Hash Tables: A data structure that maps keys to values using a hash function. They
provide average-case O(1) time complexity for insertion, deletion, and search. However,
hash collisions (two different keys mapping to the same index) must be handled.
Common collision resolution strategies include chaining and open addressing.
●​ Graphs: A non-linear data structure consisting of vertices (nodes) and edges
(connections). Graphs are used to model networks. Key algorithms include:
○​ Dijkstra's Algorithm: Finds the shortest path between nodes in a weighted graph
with non-negative edge weights.
○​ A Search Algorithm:* An informed search algorithm that uses a heuristic to find the
shortest path, making it more efficient than Dijkstra's in many cases.
○​ Graph Traversal: Techniques like Breadth-First Search (BFS) and Depth-First
Search (DFS) are used to visit all the nodes in a graph.

📝 Page 2: Computer Architecture and Parallel Computing

Computer Architecture Fundamentals

The design and organization of a computer system, focusing on its components and how they
interact. Key concepts include:
●​ Instruction Set Architecture (ISA): The part of the computer architecture related to
programming, including the native data types, instructions, registers, and memory
organization. Examples include x86 and ARM.
●​ Pipelining: A technique that allows the processor to execute multiple instructions
simultaneously by breaking them down into stages (e.g., fetch, decode, execute,
write-back). Pipelining improves processor throughput.
●​ Caching: A hardware or software component that stores data so future requests for that
data can be served faster. Processors use multiple levels of cache (L1, L2, L3) to reduce
the time it takes to access data from main memory.
●​ Memory Hierarchy: A system that organizes computer storage into a hierarchy based on
access speed. From fastest to slowest, it typically includes CPU registers, cache, main
memory (RAM), and secondary storage (disk drives).

Parallel Computing

The use of multiple processors or cores to solve a computational problem simultaneously.

●​ Types of Parallelism:
○​ Instruction-Level Parallelism (ILP): Executing multiple instructions from a single
instruction stream in parallel (e.g., pipelining).
○​ Data Parallelism: Applying the same operation to different pieces of data
simultaneously.
○​ Task Parallelism: Decomposing a problem into a set of independent tasks that can
be executed concurrently.
●​ Amdahl's Law: A formula that gives the theoretical speedup in latency of the execution
of a task at fixed workload that can be expected from a system when only a portion of
the system is improved. It highlights the diminishing returns of adding more parallel
processors.

📝 Page 3: Operating Systems

Process and Thread Management

An operating system's primary role is to manage and allocate resources.

●​ Process: An instance of a computer program that is being executed. It's an independent
entity with its own memory space, code, data, and system resources.
●​ Thread: A lightweight process that exists within a process. Multiple threads within the
same process share the same memory and resources, making communication and
context switching faster than between processes.
 ●​ Process Scheduling: The mechanism by which the OS decides which process to run on
the CPU. Common algorithms include First-Come, First-Served (FCFS), Round Robin,
Shortest Job First (SJF), and Priority Scheduling.

Memory Management

The management of a computer's main memory, including the allocation and deallocation of
memory space to processes.
●​ Virtual Memory: A technique that allows a program to use more memory than is
physically available. It uses a portion of the hard drive (swap space) to store parts of a
program's memory that aren't currently in use, creating the illusion of a larger address
space.
●​ Paging: A memory management scheme that divides the logical address space of a
process into equal-sized blocks called pages and the physical memory into equal-sized
blocks called frames. This enables non-contiguous memory allocation.

📝 Page 4: Databases and Distributed Systems

Relational Databases
●​ Relational Model: A database model based on the concept of tables, where data is
organized into rows and columns.
●​ SQL (Structured Query Language): The standard language for managing and
manipulating relational databases. Key commands include SELECT, INSERT, UPDATE, and
DELETE.
●​ Normalization: A process of organizing data in a database to reduce data redundancy
and improve data integrity. It involves a series of normal forms (1NF, 2NF, 3NF, etc.).

Distributed Systems

A collection of autonomous computers that appear to the users as a single coherent system.
●​ Consistency, Availability, Partition Tolerance (CAP) Theorem: A fundamental
theorem in distributed systems stating that it is impossible for a distributed data store to
provide more than two of the three guarantees simultaneously.
○​ Consistency: Every read receives the most recent write or an error.
○​ Availability: Every request receives a response, without a guarantee that it contains
the most recent write.1​

○​ Partition Tolerance: The system continues to operate even if there are

communication failures between nodes.2​
●​ Distributed Conse3nsus: The process of ensuring that all nodes in a distributed system
agree on a single value or state. Algorithms like Raft and Paxos are used to solve this
problem.​

📝 Page 5: Artificial Intelligence and Machine Learning

Machine Learning Paradigms
●​ Supervised Learning: The model is trained on a labeled dataset, where the desired
output is known for each input. The goal is to learn a mapping from inputs to outputs.
Examples include regression and classification.
●​ Unsupervised Learning: The model is trained on an unlabeled dataset. The goal is to
find hidden patterns or structures in the data. Examples include clustering (e.g.,
K-Means) and dimensionality reduction.
●​ Reinforcement Learning: An agent learns to make decisions in an environment to
maximize a cumulative reward. The agent learns from trial and error, receiving feedback
in the form of rewards or penalties.

Neural Networks and Deep Learning

●​ Artificial Neural Network (ANN): A computational model inspired by the structure of
the human brain. It consists of interconnected nodes (neurons) organized in layers.
●​ Deep Learning: A subfield of machine learning that uses multi-layered neural networks
(deep neural networks) to learn complex patterns.
○​ Convolutional Neural Networks (CNNs): A type of deep learning model particularly
effective for image recognition, as they can automatically detect spatial hierarchies
of features.
○​ Recurrent Neural Networks (RNNs): A type of deep learning model designed to
process sequential data (e.g., text, time series), as they have a memory that allows
them to process sequences of arbitrary length.