- RAM (Random Access Memory):
- Definition: Volatile memory used for temporary storage while the computer is running.
- Purpose: Stores data that is actively being used or processed by the CPU.
- Characteristics: Fast read and write speeds, but data is lost when the power is turned off.
- Example Use: Running applications, open files, and active processes.
- ROM (Read-Only Memory):
- Definition: Non-volatile memory used for permanent storage.
- Purpose: Stores firmware and essential system programs that do not change frequently.
- Characteristics: Data is retained even when the power is turned off, typically not writable or only writable under specific conditions.
- Example Use: BIOS or UEFI firmware in computers, embedded systems.
- Stack:
- Definition: Memory allocated for automatic variables and function call management.
- Structure: Operates in a last-in, first-out (LIFO) manner.
- Purpose: Used for static memory allocation, such as local variables and function call management.
- Characteristics: Fast access, but limited in size and scope.
- Example Use: Local variables in functions, function call stack.
- Heap:
- Definition: Memory allocated dynamically during runtime.
- Structure: Managed by the programmer or garbage collector, not structured like the stack.
- Purpose: Used for dynamic memory allocation, such as objects and data that need to persist beyond a single function call.
- Characteristics: Larger size compared to stack, but slower access due to more complex management.
- Example Use: Objects created with
newormalloc, dynamic data structures like linked lists.
- Fetch-Decode-Execute Cycle:
- Fetch: The CPU retrieves an instruction from the program memory.
- Decode: The instruction is translated into signals that control other parts of the CPU.
- Execute: The CPU performs the operation defined by the instruction.
- Registers:
- Definition: Small, fast storage locations within the CPU.
- Purpose: Temporarily hold data and instructions that are being used or processed.
- Types: General-purpose registers (for arithmetic and data storage) and special-purpose registers (for specific tasks like instruction pointers).
- Cache:
- Definition: A small, high-speed memory located inside or very close to the CPU.
- Purpose: Stores frequently accessed data and instructions to speed up processing.
- Levels: Typically organized in levels (L1, L2, L3) with L1 being the fastest and smallest.
- Parallel Processing:
- Definition: The ability to perform many operations simultaneously.
- Purpose: Handles tasks that can be divided into smaller, parallel tasks, such as rendering graphics and performing complex mathematical calculations.
- Differences between CPU and GPU:
- CPU: Optimized for single-threaded performance and general-purpose tasks.
- GPU: Optimized for multi-threaded performance and tasks that require parallel processing.
- Bus Architecture:
- Definition: A communication system that transfers data between components inside a computer.
- Types: Address bus (carries memory addresses), data bus (carries data), and control bus (carries control signals).
- Data Transfer Methods:
- Direct Memory Access (DMA): Allows peripherals to directly read/write memory without CPU intervention, speeding up data transfer.
- Memory-Mapped I/O: Uses the same address space for memory and I/O devices, allowing the CPU to interact with hardware using standard read/write operations.
- Source Code to Machine Code:
- Definition: The process of translating high-level programming code into machine code that the CPU can execute.
- Lexical Analysis:
- Definition: The first phase of compilation where the source code is converted into tokens.
- Purpose: Simplifies the syntax analysis by breaking down the source code into manageable pieces.
- Example: Keywords, operators, identifiers.
- Syntax Analysis:
- Definition: The second phase where the tokens are arranged into a tree structure called a syntax tree.
- Purpose: Ensures that the tokens form valid statements according to the language’s grammar.
- Semantic Analysis:
- Definition: The phase where the compiler adds semantic meaning to the syntax tree.
- Purpose: Checks for semantic errors such as type mismatches and undefined variables.
- Code Optimization:
- Definition: The process of improving the intermediate code to make it run more efficiently.
- Purpose: Enhances the performance and reduces the resource consumption of the compiled code.
- Code Generation:
- Definition: The final phase where the optimized intermediate code is translated into machine code.
- Purpose: Produces the final executable program that can run on the target machine.
- Static Linking:
- Definition: The process of combining all the program’s object files into a single executable file during compilation.
- Purpose: Produces an executable that includes all necessary code and libraries.
- Characteristics: Larger executable size, no dependencies on external libraries at runtime.
- Dynamic Linking:
- Definition: The process of linking the program to external libraries at runtime rather than during compilation.
- Purpose: Reduces the executable size and allows multiple programs to share the same library code.
- Characteristics: Smaller executable size, dependencies on external libraries at runtime.
- Linker Responsibilities:
- Symbol Resolution: Matches function calls with the correct function definitions.
- Relocation: Adjusts the addresses of symbols in the code to their final locations in memory.
- Definition: A paradigm based on the concept of procedure calls, where statements are structured into procedures (also known as routines, subroutines, or functions).
- Key Features: Sequential execution, use of loops and conditionals, modularity.
- Examples: C, Pascal.
- Classes:
- Definition: Blueprints for creating objects, encapsulating data and methods.
- Objects:
- Definition: Instances of classes that interact with one another.
- Inheritance:
- Definition: A mechanism where one class can inherit traits (properties and methods) from another class.
- Polymorphism:
- Definition: The ability of different classes to be treated as instances of the same class through inheritance.
- Types: Compile-time (method overloading) and runtime (method overriding).
- Encapsulation:
- Definition: The bundling of data with methods that operate on the data, restricting direct access to some of the object’s components.
- Abstraction:
- Definition: The concept of hiding complex implementation details and showing only the necessary features of an object.
- Pure Functions:
- Definition: Functions that have no side effects and return the same result given the same input.
- Immutability:
- Definition: Data cannot be modified after it is created.
- Higher-Order Functions:
- Definition: Functions that take other functions as arguments or return them as results.
- Definition: A paradigm where the flow of the program is determined by events such as user actions (mouse clicks, key presses), sensor outputs, or message passing.
- Key Features: Event handlers, event loops, callbacks.
- Examples: JavaScript (with DOM events), Node.js, GUI applications.
- Variables:
- Definition: Named storage locations in memory for holding data.
- Example:
int age = 25;
- Data Types:
- Primitive Types: Integer, float, double, char, boolean.
- Composite Types: Arrays, structs, objects.
- Example:
int, float, char, boolean.
- Arithmetic Operators:
- Definition: Perform mathematical operations.
- Example:
+ (addition), - (subtraction), * (multiplication), / (division), % (modulus)
- Comparison Operators:
- Definition: Compare two values.
- Example:
== (equal to), != (not equal to), > (greater than), < (less than), >= (greater than or equal to), <= (less than or equal to)
- Logical Operators:
- Definition: Perform logical operations.
- Example:
&& (logical AND), || (logical OR), ! (logical NOT)
- Assignment Operators:
- Definition: Assign values to variables.
- Example:
= (assignment), += (addition assignment), -= (subtraction assignment), *= (multiplication assignment), /= (division assignment)
If Statements:
- Definition: Execute a block of code if a specified condition is true.
C++:
if (condition) {
// code to be executed if condition is true
}
Python:
if condition:
# code to be executed if condition is true
Loops:
- For Loop:
- Definition: Repeats a block of code a specified number of times.
C++:
for (int i = 0; i < 10; i++) {
// code to be executed
}
Python:
for i in range(10):
# code to be executed
- While Loop:
- Definition: Repeats a block of code as long as a specified condition is true.
C++:
while (condition) {
// code to be executed
}
Python:
while condition:
# code to be executed
- Do-While Loop:
- Definition: Similar to the while loop, but checks the condition after executing the block of code.
C++:
do {
// code to be executed
} while (condition);
Python: Python does not have a built-in do-while loop. You can simulate it using a while loop with a break condition:
while True:
# code to be executed
if not condition:
break
- Switch-Case:
- Definition: Selects one of many code blocks to be executed.
C++:
switch (expression) {
case value1:
// code to be executed if expression == value1
break;
case value2:
// code to be executed if expression == value2
break;
default:
// code to be executed if expression doesn't match any case
}
Python: Python does not have a built-in switch-case statement. You can use if-elif-else statements to achieve similar functionality:
if expression == value1:
# code to be executed if expression == value1
elif expression == value2:
# code to be executed if expression == value2
else:
# code to be executed if expression doesn't match any case
Functions/Methods
- Definition: Blocks of code that perform a specific task, can be called upon to execute when needed.
- Purpose: Promote code reusability and modularity.
C++:
int add(int a, int b) {
return a + b;
}
Python:
def add(a, b):
return a + b
Arrays:
- Definition: A collection of elements, all of the same type, stored in contiguous memory locations.
- Characteristics: Fixed size, direct access by index.
C++:
int numbers[5] = {1, 2, 3, 4, 5};
Python:
numbers = [1, 2, 3, 4, 5]
Lists:
- Definition: A collection of elements that can be of any type and are dynamically sized.
- Characteristics: Flexible size, often implemented using linked structures.
Stacks:
- Definition: A collection of elements that follows the Last In, First Out (LIFO) principle.
- Operations: Push (add an element), Pop (remove the top element), Peek (view the top element).
C++:
#include <stack>
std::stack<int> stack;
stack.push(1); // Push
stack.pop(); // Pop
Python:
stack = []
stack.append(1) # Push
stack.pop() # Pop
Queues:
- Definition: A collection of elements that follows the First In, First Out (FIFO) principle.
- Operations: Enqueue (add an element), Dequeue (remove the front element), Peek (view the front element).
C++:
#include <queue>
std::queue<int> queue;
queue.push(1); // Enqueue
queue.pop(); // Dequeue
Python:
from collections import deque
queue = deque()
queue.append(1) # Enqueue
queue.popleft() # Dequeue
Singly Linked Lists:
- Definition: A collection of nodes where each node contains data and a reference to the next node in the sequence.
- Characteristics: Allows dynamic memory allocation, efficient insertion, and deletion.
C++:
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedList {
public:
Node* head;
LinkedList() : head(nullptr) {}
};
Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
Doubly Linked Lists:
- Definition: Similar to singly linked lists, but each node also contains a reference to the previous node.
- Characteristics: Allows traversal in both directions.
C++:
struct Node {
int data;
Node* next;
Node* prev;
Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
};
Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
Binary Tree:
- Definition: A tree data structure where each node has at most two children (left and right).
- Characteristics: Hierarchical structure, efficient searching and sorting.
C++:
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
Python:
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
Binary Search Tree:
- Definition: A binary tree where the left child of a node contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than the parent node.
- Characteristics: Efficient searching, insertion, and deletion.
AVL Tree:
- Definition: A self-balancing binary search tree where the difference in heights between the left and right subtrees cannot be more than one for all nodes.
- Characteristics: Ensures O(log n) time complexity for search, insertion, and deletion.
Graphs:
- Definition: A collection of nodes (vertices) and edges connecting pairs of nodes.
- Types: Directed, undirected, weighted, unweighted.
Hash Tables
- Definition: A data structure that maps keys to values for highly efficient lookup.
- Characteristics: Utilizes a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
C++:
#include <unordered_map>
std::unordered_map<std::string, std::string> hash_table;
hash_table["key"] = "value";
Python:
hash_table = {}
hash_table['key'] = 'value'
C++:
Linear Search:
- Definition: Iterates through each element in a list until the target element is found or the list ends.
- Characteristics: Simple but inefficient for large datasets (O(n) time complexity).
C++:
int linear_search(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
Python:
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
Binary Search:
- Definition: Efficiently searches a sorted list by repeatedly dividing the search interval in half.
- Characteristics: Requires sorted input, O(log n) time complexity.
C++:
int binary_search(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Python:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Bubble Sort:
- Definition: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
- Characteristics: Simple but inefficient for large datasets (O(n^2) time complexity).
C++:
void bubble_sort(int arr[], int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
Selection Sort:
- Definition: Divides the list into a sorted and an unsorted region, repeatedly selects the smallest element from the unsorted region, and moves it to the end of the sorted region.
- Characteristics: Inefficient for large datasets (O(n^2) time complexity).
C++:
void selection_sort(int arr[], int size) {
for (int i = 0; i < size; i++) {
int min_index = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
std::swap(arr[i], arr[min_index]);
}
}
Python:
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
Insertion Sort:
- Definition: Builds the final sorted list one item at a time by repeatedly inserting the next item into the correct position.
- Characteristics: Efficient for small datasets or nearly sorted lists (O(n^2) time complexity in the worst case, O(n) in the best case).
C++:
void insertion_sort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Python:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
Quicksort:
- Definition: Divides the list into two smaller sub-lists, the low elements and the high elements, and then recursively sorts the sub-lists.
- Characteristics: Efficient for large datasets (average O(n log n) time complexity).
C++:
#include <vector>
std::vector<int> quicksort(std::vector<int>& arr) {
if (arr.size() <= 1) {
return arr;
}
int pivot = arr[arr.size() / 2];
std::vector<int> left, middle, right;
for (int x : arr) {
if (x < pivot) {
left.push_back(x);
} else if (x == pivot) {
middle.push_back(x);
} else {
right.push_back(x);
}
}
std::vector<int> sorted_left = quicksort(left);
std::vector<int> sorted_right = quicksort(right);
sorted_left.insert(sorted_left.end(), middle.begin(), middle.end());
sorted_left.insert(sorted_left.end(), sorted_right.begin(), sorted_right.end());
return sorted_left;
}
Python:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
Mergesort:
- Definition: Divides the list into two halves, recursively sorts each half, and then merges the two sorted halves.
- Characteristics: Stable sort with O(n log n) time complexity, uses additional memory for merging.
C++:
#include <vector>
std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
std::vector<int> result;
size_t i = 0, j = 0;
while (i < left.size() && j < right.size()) {
if (left[i] < right[j]) {
result.push_back(left[i]);
i++;
} else {
result.push_back(right[j]);
j++;
}
}
while (i < left.size()) {
result.push_back(left[i]);
i++;
}
while (j < right.size()) {
result.push_back(right[j]);
j++;
}
return result;
}
std::vector<int> merge_sort(const std::vector<int>& arr) {
if (arr.size() <= 1) {
return arr;
}
size_t mid = arr.size() / 2;
std::vector<int> left(arr.begin(), arr.begin() + mid);
std::vector<int> right(arr.begin() + mid, arr.end());
return merge(merge_sort(left), merge_sort(right));
}
Python:
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
Recursion
- Definition: A process where a function calls itself as a subroutine.
- Purpose: Useful for tasks that can be divided into similar subtasks.
- Characteristics: Must have a base case to avoid infinite recursion.
C++:
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
Python:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
Dynamic Programming
- Definition: A method for solving complex problems by breaking them down into simpler subproblems and storing the results of subproblems to avoid redundant computations.
- Purpose: Optimizes recursive algorithms by storing intermediate results.
- Characteristics: Uses a table to store results of subproblems.
C++:
#include <unordered_map>
int fibonacci(int n, std::unordered_map<int, int>& memo) {
if (memo.find(n) != memo.end()) {
return memo[n];
}
if (n <= 1) {
return n;
}
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
int fibonacci(int n) {
std::unordered_map<int, int> memo;
return fibonacci(n, memo);
}
Python:
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
Exceptions
- Definition: Events that occur during the execution of a program that disrupt the normal flow of instructions.
- Types of Exceptions:
- Syntax Errors: Errors in the structure of the code, detected at compile time.
- Runtime Errors: Errors that occur during program execution, such as division by zero or file not found.
- Logical Errors: Errors in the logic of the program that produce incorrect results but do not stop the program from running.
- Handling Exceptions:
- Try-Except Block: Code that might raise an exception is placed in a
tryblock, and code to handle the exception is placed in anexceptblock.
- Try-Except Block: Code that might raise an exception is placed in a
C++:
Note: C++ does not throw an exception for division by zero in integers; it causes undefined behavior. you might need to explicitly check for zero and throw an exception manually.
#include <iostream>
#include <stdexcept>
int main() {
try {
int denominator = 0;
if (denominator == 0) {
throw std::runtime_error("Cannot divide by zero!");
}
int result = 10 / denominator;
} catch (const std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
return 0;
}
Python:
try:
result = 10 / 0
except ZeroDivisionError:
print("Cannot divide by zero!")
Try-Except-Else Block: The else block executes if no exceptions are raised.
C++:
#include <iostream>
#include <stdexcept>
int main() {
try {
int denominator = 2;
if (denominator == 0) {
throw std::runtime_error("Cannot divide by zero!");
}
int result = 10 / denominator;
std::cout << "Division successful: " << result << std::endl;
} catch (const std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
return 0;
}
Python:
try:
result = 10 / 2
except ZeroDivisionError:
print("Cannot divide by zero!")
else:
print("Division successful:", result)
Try-Except-Finally Block: The finally block executes regardless of whether an exception was raised or not.
C++ does not have a finally block.
Python:
try:
file = open("test.txt", "r")
content = file.read()
except FileNotFoundError:
print("File not found!")
finally:
file.close()
- Definition: The process of identifying, analyzing, and removing errors in a program.
- Common Debugging Techniques:
- Print Statements: Inserting print statements to output variable values and program flow to the console.
C++:
#include <iostream>
int add(int a, int b) {
std::cout << "a: " << a << ", b: " << b << std::endl;
return a + b;
}
Python:
def add(a, b):
print(f"a: {a}, b: {b}")
return a + b
- Using a Debugger: A tool that allows step-by-step execution of a program, inspection of variable values, and setting breakpoints.
- Example: Debuggers in IDEs like Visual Studio, PyCharm, or Eclipse.
- Code Reviews: Having peers review your code to catch errors and improve code quality.
- Unit Testing: Writing tests for individual units of code to ensure they work as expected.
C++:
#include <iostream>
#include <cassert>
int add(int a, int b) {
std::cout << "a: " << a << ", b: " << b << std::endl;
return a + b;
}
void test_add() {
assert(add(2, 3) == 5);
assert(add(-1, 1) == 0);
std::cout << "All tests passed!" << std::endl;
}
int main() {
test_add();
return 0;
}
Python:
def test_add():
assert add(2, 3) == 5
assert add(-1, 1) == 0
