flashcards (1)

Question 1

Change Making Problem

Answer 1

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

Question 2

Shortest Path Problem

Answer 2

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

Question 3

Minimum Spanning Tree

Answer 3

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

Question 4

PageRank

Answer 4

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)

Question 5

Graph Coloring

Answer 5

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

Question 6

Traveling Salesman Problem

Answer 6

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

Question 7

Knapsack Problem

Answer 7

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)

Question 8

P, NP, NP-Complete and NP-Hard

Answer 8

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

Question 9

NP-Hard Problems

Answer 9

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

Question 10

NP-Complete

Answer 10

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

Question 11

Dijkstra’s Algorithm

Answer 11

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

Question 12

Floyd-Warshall

Answer 12

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

Question 13

Bellman-Ford

Answer 13

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

Question 14

Merge Sort

Answer 14

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

Question 15

Quick Sort

Answer 15

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

Question 16

Binary Search

Answer 16

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

Question 17

Upper vs Lower Bounds

Answer 17

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

Question 18

Church-Turing Thesis

Answer 18

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

Question 19

Turing Machine

Answer 19

Components:
- Infinite tape
- Read/write head
- Finite state control
- Transition function

Properties:
- Can compute any computable function
- Universal computation model
- Basis for complexity theory

Question 20

Proof Techniques

Answer 20

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)

Question 21

Computability

Answer 21

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.

Question 22

Decidability

Answer 22

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.

Question 23

Provability

Answer 23

A statement or theorem is provable if it can be derived from axioms using formal rules of logic.

Question 24

Completeness

Answer 24

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.

Question 25

Tractability

Answer 25

Whether a problem can be solved in a reasonable (polynomial) time.

Question 26

Entscheidungsproblem

Answer 26

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.

Question 27

Stack ADT Signatures

Answer 27

push: element × stack → stack
pop: stack → stack
top: stack → element
isEmpty: stack → boolean

Question 28

Complete Graph Properties

Answer 28

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

Question 29

PageRank Implementation

Answer 29

1. Initial values: 1/N for N nodes
2. Iterative updates based on incoming links
3. Damping factor (typically 0.85)
4. Convergence to steady state
5. Application to real-world networks

Question 30

Hill Climbing vs A* Search

Answer 30

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