flashcards (1)
Change Making Problem
Goal: Find minimum number of coins to make a given amount
Properties:
- Dynamic programming problem
- Greedy approach works for some currency systems but not all
- Can be solved optimally with DP in O(nW) time, n is number of coins, W is target amount
Example: Making 30¢ with [25,10,5,1] coins → [25,5] is optimal
Shortest Path Problem
Goal: Find minimum weight path between nodes in weighted graph
Key Algorithms:
- Dijkstra’s (no negative weights) O(nlogn)
- Bellman-Ford (handles negative weights) O(n*e)
Properties:
- Fundamental graph problem
- Many variations (single-source, all-pairs)
- Core component in navigation systems
Minimum Spanning Tree
Goal: Connect all vertices with minimum total edge weight
Key Algorithms:
- Prim’s (builds tree from single vertex)
Properties:
- Time complexity O(E log V)
- Tree has exactly V-1 edges
- No cycles permitted
PageRank
Goal: Measure importance of nodes based on incoming connections
Properties:
- Used in Google’s search algorithm
- Accounts for both quantity and quality of links
- Uses random surfer model with damping factor
Implementation:
- Iterative matrix multiplication algorithm
- Converges to steady state
- Time complexity O(E) per iteration
- Number of iterations for convergence depends on:
• Desired precision
• Graph structure
• Damping factor (typically 0.85)
Graph Coloring
Goal: Color vertices so no adjacent vertices share colors
Properties:
- NP-complete
- Minimum colors needed is chromatic number
Applications:
- Scheduling problems
- Register allocation
- Map coloring
Traveling Salesman Problem
Goal: Find shortest route visiting each city exactly once
Properties:
- NP-hard optimization problem
- No known polynomial time solution
- Small instances solvable exactly (<20 cities)
Approaches:
- Branch and bound for exact solution
- Approximation algorithms
- Heuristics like simulated annealing
Knapsack Problem
Goal: Select items maximizing value while respecting weight limit
Types:
- 0/1 Knapsack (take item or not)
- Fractional Knapsack (can take portions)
Properties:
- NP-complete (0/1 version)
- Greedy solution works for fractional version
- Dynamic programming pseudo-polynomial solution, making it o(nW)
P, NP, NP-Complete and NP-Hard
P: Problems solvable in polynomial time (like sorting)
NP: Problems whose solutions can be verified in polynomial time (like Sudoku)
NP-Complete: Problems that are both NP and if solved in polynomial, would solve all NP problems (like Boolean Satisfiability/SAT)
NP-Hard: Problems at least as hard as NP-Complete problems but might not be in NP (like Halting Problem)
P ⊆ NP ⊆ NP-Complete ⊆ NP-Hard
NP-Hard Problems
Definition: At least as hard as hardest NP problems
Properties:
- May not be in NP
- No polynomial time solution known
- Reducing any NP problem to it is possible
Examples:
- TSP optimization
- Halting problem
- Graph isomorphism
NP-Complete
Definition: Both NP-hard and in NP
Properties:
- Hardest problems in NP
- All NP-complete problems reducible to each other
- Finding polynomial solution proves P = NP
Famous Examples:
- Boolean satisfiability (SAT)
- Hamiltonian cycle
- Graph coloring
Dijkstra’s Algorithm
Goal: Find shortest paths from source to all vertices
Properties:
- Cannot handle negative weights
- Greedy approach
- Uses priority queue
Complexity:
- O(V²) basic implementation
- O(E log V) with binary heap
- O(E + V log V) with Fibonacci heap
Floyd-Warshall
Goal: Find shortest paths between all pairs of vertices
Properties:
- Dynamic programming approach
- Can handle negative weights
- Cannot handle negative cycles
- Simple to implement
Complexity: O(V³) time
Bellman-Ford
Goal: Single-source shortest paths with negative weights
Properties:
- Can detect negative cycles
- Simpler than Dijkstra’s
- Uses edge relaxation
Complexity:
- O(VE) time
- Requires V-1 iterations to find paths
Merge Sort
Strategy: Divide and conquer sorting
Properties:
- Stable sort
- O(n log n) time complexity
- Requires O(n) extra space
Steps:
1. Split array in half
2. Recursively sort halves
3. Merge sorted halves
Quick Sort
Strategy: Divide and conquer sorting using pivots
Properties:
- In-place but not stable
- Average O(n log n)
- Worst case O(n²)
Steps:
1. Choose pivot
2. Partition around pivot
3. Recursively sort partitions
Binary Search
Strategy: Repeatedly divide search space in half
Properties:
- Requires sorted input
- O(log n) time complexity
- Optimal for searching sorted array
Steps:
1. Check middle element
2. Eliminate half of remaining elements
3. Repeat until found
Upper vs Lower Bounds
Upper Bound (Big O):
- Growth rate ceiling
- f(n) ≤ cg(n) for large n
Lower Bound (Big Ω):
- Growth rate floor
- f(n) ≥ cg(n) for large n
Tight Bound (Big Θ):
- Exact growth rate
- Both upper and lower bound
Church-Turing Thesis
Statement: Anything computable can be computed by a Turing machine
Implications:
- Defines limits of mechanical computation
- All reasonable models equally powerful
- Foundation for computer science
Note: Cannot be mathematically proven
Turing Machine
Components:
- Infinite tape
- Read/write head
- Finite state control
- Transition function
Properties:
- Can compute any computable function
- Universal computation model
- Basis for complexity theory
Proof Techniques
Contradiction:
1. Assume statement false
2. Show this leads to contradiction
3. Therefore statement must be true
Induction:
1. Prove base case
2. Prove inductive step
3. Conclude true for all cases
Example: √2 irrational (contradiction)
Example: Sum of first n numbers (induction)
Computability
The field of study concerning which problems can be solved by a computer or algorithm.
The problem of determining whether a given number is prime is computable, as there exists an algorithm to solve it.
Decidability
A property of a problem that implies there is an algorithm that can decide the solution (yes/no answer) for every input within finite time.”,”The halting problem (determining if a program halts) is undecidable; there’s no algorithm that works for all possible inputs.
Provability
A statement or theorem is provable if it can be derived from axioms using formal rules of logic.
Completeness
A logical system is complete if every statement that is true within its model is also provable within the system.
Gödel’s incompleteness theorem shows that arithmetic is not complete, as there are true statements that are unprovable within the system.
Tractability
Whether a problem can be solved in a reasonable (polynomial) time.
Entscheidungsproblem
A question posed by David Hilbert asking if an algorithm exists to decide the truth of any mathematical statement. Proven undecidable by Turing and Church, showing limits of computational problem-solving.
Stack ADT Signatures
push: element × stack → stack
pop: stack → stack
top: stack → element
isEmpty: stack → boolean
Complete Graph Properties
Definition: Graph where every vertex is connected to every other vertex
Properties:
- n vertices have n(n-1)/2 edges
- Always contains Hamiltonian cycle
- Chromatic number equals n
- Every vertex has degree n-1
PageRank Implementation
- Initial values: 1/N for N nodes
- Iterative updates based on incoming links
- Damping factor (typically 0.85)
- Convergence to steady state
- Application to real-world networks
Hill Climbing vs A* Search
Hill Climbing:
- Moves to best neighboring state
- Can get stuck in local optima
- Memory efficient
A* Search:
- Uses heuristic + path cost
- Guaranteed optimal path if admissible
- More memory intensive
- Better for maze/path finding
