Traveling Salesman Problem (TSP) The Traveling Salesman Problem involves finding the shortest possible route that visits a set of cities, each exactly once, and returns to the starting city. It's a classic optimization problem with applications in logistics, planning, and manufacturing.
Two Generals' Problem The Two Generals' Problem is a thought experiment illustrating the difficulties of coordination and communication over an unreliable channel. It involves two generals who must agree on a time to attack a city but can only communicate through unreliable messengers. The problem highlights issues in achieving reliable communication in distributed systems.
The Halting Problem The Halting Problem asks whether a given program will finish running or continue to run forever. Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
P vs NP Problem This problem asks whether every problem that can be verified quickly (in polynomial time) can also be solved quickly. It’s one of the seven "Millennium Prize Problems" in mathematics with a $1 million reward for a correct solution.
Knapsack Problem The Knapsack Problem involves selecting a subset of items with given weights and values to maximize the total value without exceeding the weight limit. It's commonly used in resource allocation and optimization scenarios.
Graph Coloring Problem The Graph Coloring Problem involves coloring the vertices of a graph such that no two adjacent vertices share the same color while using the minimum number of colors. It's useful in scheduling and register allocation in compilers.
Minimum Spanning Tree (MST) The Minimum Spanning Tree problem involves finding the subset of edges in a connected, weighted graph that connects all vertices with the minimum total edge weight. Algorithms like Kruskal's and Prim's are commonly used to solve it.
Dining Philosophers Problem The Dining Philosophers Problem illustrates issues of concurrency control and resource allocation. It involves philosophers who must alternately think and eat, but only a limited number of forks (resources) are available, potentially leading to deadlock.
Dijkstra's Algorithm This algorithm finds the shortest path between nodes in a graph, which can represent, for example, road networks. It’s widely used in routing and network optimization.
-
PageRank Algorithm Developed by Google, this algorithm ranks web pages in search engine results based on their importance and relevance. It's a fundamental problem in the field of web search and information retrieval.
-
SAT Problem (Boolean Satisfiability) The SAT Problem asks whether a given Boolean formula can be satisfied, meaning there is some assignment of truth values to variables that makes the entire formula true. It's the first problem that was proven to be NP-complete.
-
Maximum Flow Problem This problem involves finding the maximum flow possible through a flow network from a source to a sink. It's used in network routing, transportation, and logistics.
-
Bin Packing Problem The Bin Packing Problem requires you to pack objects of different volumes into a finite number of bins or containers in a way that minimizes the number of bins used. It’s relevant in resource allocation and logistics.
-
Set Cover Problem The Set Cover Problem asks for the smallest subset of sets that cover all elements in a universe of elements. It has applications in resource allocation, data mining, and network design.
-
Subset Sum Problem Given a set of integers, the Subset Sum Problem asks whether there is a non-empty subset whose sum is zero. It’s a special case of the Knapsack Problem and has applications in cryptography.
-
Longest Common Subsequence (LCS) Problem The LCS Problem involves finding the longest subsequence common to two sequences. It’s used in bioinformatics for sequence alignment and in text comparison tools.
-
Hamiltonian Path Problem This problem involves finding a path in a graph that visits each vertex exactly once. If such a path exists and returns to the starting vertex, it’s called a Hamiltonian cycle. It’s used in routing and scheduling problems.
-
Vertex Cover Problem The Vertex Cover Problem involves finding the smallest set of vertices in a graph such that each edge has at least one endpoint in the set. It’s a fundamental problem in network design and biology.
-
K-Clique Problem The K-Clique Problem asks whether a graph contains a clique of size 𝑘, where a clique is a subset of vertices such that every pair of vertices is connected by an edge. It’s used in social network analysis and bioinformatics.
-
Tower of Hanoi A classic puzzle involving three rods and a number of disks of different sizes, which can be moved from one rod to another with the constraint that no disk may be placed on top of a smaller disk. It’s used to teach recursion in computer science.
-
Prisoner's Dilemma An important problem in game theory and decision theory, where two individuals must choose between cooperation and betrayal without knowing the other's choice. It highlights the conflict between individual and collective rationality.
-
Resource Allocation Problems These involve distributing resources among competing entities in a way that optimizes a certain objective. Examples include load balancing, scheduling, and budget allocation.
Dining Philosophers Problem:
Philosophers sitting around a table must share forks to eat but avoid deadlock and starvation. Significance: Classic synchronization problem in concurrent programming. Byzantine Generals Problem:
A group of generals must agree on a common plan of action, but some generals might be traitors. Significance: Foundation of fault-tolerant distributed systems and blockchain consensus algorithms.
Game Theory and Decision Making Prisoner's Dilemma:
Two prisoners must decide whether to cooperate or betray each other without knowing the other's choice. Significance: Explains concepts of trust and strategy in multi-agent systems. Minimax Problem:
Used in two-player games to minimize the possible loss for a worst-case scenario. Significance: Basis for AI in games like chess and tic-tac-toe.
- Machine Learning Optimization Problems Problems in this category include gradient descent for minimizing functions, hyperparameter tuning, and solving various types of loss functions in neural networks.
- Alan Turing - Turing Complete
- George Boole
- Breadth First vs Depth First
- Bubble Sort
Sorting and Searching
Quick Sort: Divide-and-conquer sorting algorithm with average-case O(n log n) complexity. Merge Sort: Stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) complexity. Heap Sort: Uses a heap data structure for O(n log n) sorting. Bubble Sort (and variations): Useful for understanding algorithmic basics despite inefficiency. Radix Sort: Efficient for sorting integers with O(nk) complexity (non-comparative). Searching Algorithms:
Binary Search: Efficient search for sorted arrays with O(log n) complexity. Linear Search: Basic, unsorted search with O(n) complexity.
Depth-First Search (DFS): Explore as far as possible along branches (O(V+E)). Breadth-First Search (BFS): Explore level by level in graphs (O(V+E)).
Dijkstra’s Algorithm: Finds the shortest path in a graph with non-negative weights (O(V^2) or O(E + V log V) with a priority queue). Bellman-Ford Algorithm: Handles graphs with negative weights (O(VE)). A* (A-star): Heuristic-based shortest path for pathfinding. Minimum Spanning Tree:
Kruskal’s Algorithm: Greedy approach using a union-find data structure (O(E log E)). Prim’s Algorithm: Greedy algorithm using a priority queue (O(E + V log V)). Cycle Detection:
Union-Find/Disjoint Set: Useful for detecting cycles in undirected graphs. Dynamic Programming (DP)
Knapsack Problem: Optimize value under a weight constraint. Longest Common Subsequence (LCS): Find the longest subsequence common to two sequences. Matrix Chain Multiplication: Optimize the multiplication of a sequence of matrices. Floyd-Warshall Algorithm: Find shortest paths between all pairs of nodes. Kadane’s Algorithm: Maximum subarray sum in O(n).
Bottom-up and top-down memoization strategies. Divide-and-Conquer Binary Search (also mentioned in Searching). Merge Sort and Quick Sort (also mentioned in Sorting). Strassen’s Algorithm: Matrix multiplication in O(n^2.81).
Activity Selection Problem: Select the maximum number of activities that don’t overlap. Huffman Encoding: Lossless compression using variable-length codes. Interval Scheduling: Find the optimal schedule for jobs.
String Matching: KMP (Knuth-Morris-Pratt) Algorithm: Efficient substring search. Rabin-Karp Algorithm: Uses hashing for substring search. Suffix Arrays and Trees: Efficient for pattern matching in text.
Greatest Common Divisor (GCD): Euclid’s Algorithm: Find GCD in O(log min(a, b)).
Fast modular exponentiation. Fermat’s Little Theorem (for primality testing). RSA Algorithm: Core cryptographic algorithm. Concurrency and Parallelism Producer-Consumer Problem: Synchronization with semaphores. Mutex/Locks: Handle race conditions in multi-threaded applications.
K-Means Clustering: Group similar data points. Gradient Descent: Optimize parameters in machine learning models.
Heap: Heapify: Maintain the heap property. Priority Queues: Efficient min/max retrieval. Trie: Efficient string matching and prefix searching. Balanced Trees: AVL Trees, Red-Black Trees: Self-balancing for efficient lookups and updates.
Efficient for lookups (O(1) on average). Miscellaneous
N-Queens Problem: Place N queens on an N×N chessboard. Sudoku Solver: Constraint satisfaction. Monte Carlo and Las Vegas Algorithms: Randomized algorithms for approximate or exact solutions.
Bit Manipulation: Find unique numbers, subsets, or perform arithmetic with bitwise operators.
- Bug