Data Structures and Algorithms: Key Concepts
Data Structures
Arrays: Fixed-size, sequentially stored elements. Efficient for index-based access.
Linked Lists: Elements (nodes) linked using pointers. Efficient for insertions/deletions.
Stacks (LIFO): Operations: push(e), pop(), top(), is_empty(), len().
Queues (FIFO): Operations: enqueue(e), dequeue(), first(), is_empty(), len().
Binary Trees: Each node has at most two children (left and right).
- Binary Search Trees (BST): Nodes follow left < root < right rule.
- AVL Trees: Self-balancing BSTs with rotations to maintain balance.
- Red-Black Trees: Self-balancing BSTs with color properties for balancing.
Heaps (Priority Queues)
- Max-Heap: Root node is the maximum element.
- Min-Heap: Root node is the minimum element.
Graphs: Nodes (Vertices) and Edges.
Types: Directed, Undirected, Weighted, Unweighted.
Graph Traversal
Depth First Search (DFS) – Stack
- In-order: Left, Root, Right.
- Post-order: Left, Right, Root.
Graphs: Explore as far as possible along each branch before backtracking. Use: Solving mazes
Breadth First Search (BFS) – Queues
- Trees: Level by level.
- Graphs: Visit all neighbors before moving to the next level.
Finding shortest path in unweighted graphs.
Shortest Path Algorithms
Dijkstra’s Algorithm (non-negative weights)
Purpose: Find the shortest path in weighted graphs.
1. Find the cheapest unprocessed node. 2. Update costs of its neighbors. 3. Repeat until all nodes are processed. 4. Calculate the final path.
Bellman-Ford Algorithm (negative weights and detects negative cycles)
Purpose: Find shortest paths in graphs with negative weights.
1) Initialize distances. 2) Relax all edges V-1 times. 3) Check for negative-weight cycles.
Time Complexity
DFS/BFS: O(V + E).
Dijkstra: O((E + V) log V) with a heap.
Bellman-Ford: O(V * E).
Algorithm Design Paradigms
Brute Force: Tests all possible solutions. Ex: Simple search, Selection Sort. Use: When no better approach is known.
Divide and Conquer: Breaks problem into sub-problems, solves recursively. Ex: Quicksort, Binary Search, Fibonacci sequence
Greedy Method: Makes the optimal choice at each step. Use: Optimization problems (e.g., classroom scheduling). Limitations: May not always produce the optimal solution (e.g., knapsack problem).
Dynamic Programming: Solves complex problems by breaking them into simpler sub-problems and storing their solutions.
Techniques:
- Memoization: Stores results of expensive function calls.
- Tabulation: Uses a table to solve sub-problems iteratively.
Use: Problems with overlapping sub-problems and optimal substructure (e.g., knapsack problem).
NP Problems: No polynomial-time solution is known. Examples: Set covering problem, traveling salesperson problem.
Approaches: Greedy method for approximations, Dynamic Programming for optimal solutions.
Key Concepts
Optimization Problems: Require finding the best solution among feasible solutions.
Overlapping Subproblems: Subproblems recur multiple times.
Optimal Substructure: Optimal solution can be constructed from optimal solutions of subproblems.
Comparison: Greedy vs. Dynamic Programming:
Greedy: Easier and faster but may not always be optimal. Dynamic Programming: More complex but guarantees optimal solutions for problems with overlapping subproblems and optimal substructure.
Data Structure Comparison
Arrays: Fixed-size, contiguous collection of items.
Read/Access: O(1) – Constant time.
Insert/Delete: Best case (end): O(1) O(n).
–Efficient for index-based access.
Linked Lists: Collection of nodes with data and a reference to the next node.:
Read/Access: First item: O(1). Last item: O(n).
Insert/Delete: O(1) – Constant time.
–Flexible size, no need for contiguous memory.
-Efficient for insertions/deletions.
Hash Tables: Maps keys to values using a hash function.
Operations: average O(1) worst O(n)
Hash Function: Maps keys to array indices.
Array: Stores values at indices returned by the hash function.
Challenges:
Collisions: Multiple keys map to the same index.
Resizing: Increase array size when load factor exceeds 0.7.
Python Implementations
Associative Arrays (Dictionaries): Built-in, implemented as hash tables.
Comparison of Arrays and Linked Lists
Arrays: Best for read/access operations, costly for insertions/deletions.
Linked Lists: Best for insertions/deletions, costly for read/access operations.
Recursion and OOP
Recursion: Calls itself to solve a problem.
Base Case: Recursion stops.
Recursive Case: Function calls itself.
Call Stack: Keeps track of function calls, pushing and popping functions as they are called and return.
Divide and Conquer: A strategy to solve problems by breaking them into smaller sub-problems, solving each recursively, and combining their results.
Object-Oriented Programming (OOP)
Class: A blueprint for creating objects (instances). Object: An instance of a class.
Attributes: Characteristics of an object.
Methods: Functions defined within a class that operate on its attributes.
Special Methods: init: Initializes an object’s attributes. repr: Provides the official string representation of an object. str: Provides the informal (readable) string representation of an object.
Inheritance: Base Class: The class being inherited from. Derived Class: The class that inherits from the base class. Allows derived classes to inherit attributes and methods from base classes, promoting code reuse.
Functional Programming: Functions and variables as the main elements of code.
Object-Oriented Programming: Focuses on creating objects and methods, making them the main elements of code.
Big O Notation
O(1), O(log n), O(n), O(n log n), O(n²).
Searching Algorithms
Simple Search
- Finding an element in an unordered list.
- How It Works: Iterates through the list until the desired element is found.
- Runtime: O(n) in the worst case.
Binary Search
- Finding an element in an ordered list.
- How It Works: Repeatedly divides the list in half, comparing the middle element to the target.
- Runtime: O(log n) in the worst case.
Sorting Algorithms
Selection Sort
- Use Case: Sorting small lists.
- How It Works: Repeatedly finds the minimum or maximum element and moves it to the sorted portion of the list.
- Runtime: O(n^2) in the worst case.
Quicksort
- Use Case: Efficiently sorting large lists.
- How It Works: Uses a pivot to partition the list into smaller sublists, then recursively sorts the sublists.
- Runtime: O(n^2) in the worst case, but O(n log n) on average and in the best case.