Final Flashcards
(28 cards)
What is an algorithm?
A step-by-step procedure used to solve a problem or perform a task.
What does Big-T (T(n)) represent?
The exact count of primitive operations an algorithm performs for input size n.
What does Big-O represent?
An upper bound on an algorithm’s time complexity in the worst case.
What is a heuristic?
A rule of thumb or strategy guiding search to good solutions when exact methods are too slow.
What is an example of a heuristic?
Using Manhattan distance in A* to estimate distance to the goal.
What is the difference between P and NP?
P = solvable in polynomial time. NP = verifiable in polynomial time. P ⊆ NP.
How are NP-Complete problems solved?
Using heuristics or approximations like GA or SA, since exact solutions are too slow.
What is a local minimum?
A solution better than its neighbours but not the best globally.
What is a fitness function?
A function that evaluates the quality of a solution.
What is a search space?
All possible candidate solutions to a problem.
What is an invalid solution?
A solution that violates problem constraints.
Define Hill Climbing.
Greedily improves solution by exploring neighbours.
Define Random Mutation Hill Climbing (RMHC).
Like Hill Climbing but uses random mutation to generate neighbours.
Define Stochastic Hill Climbing (SHC).
Accepts worse solutions with some probability to escape local optima.
Define Random Restart Hill Climbing (RRHC).
Runs HC multiple times from random starting points to improve results.
Define Simulated Annealing (SA).
Accepts worse solutions early on; cooling temperature reduces acceptance over time.
Define Iterated Local Search (ILS).
Perturbs local optima and re-applies local search to escape traps.
Define Genetic Algorithms (GA).
Population-based method using crossover, mutation, and selection.
Define Evolutionary Programming (EP).
Similar to GA but uses mutation and tournament selection; no crossover.
Define Particle Swarm Optimisation (PSO).
Particles adjust position based on personal and global best; inspired by bird flocking.
Define Ant Colony Optimisation (ACO).
Ants explore paths with pheromones, leading others to good routes.
Why use heuristics for TSP?
TSP has too many permutations to brute-force. Heuristics find good-enough solutions efficiently.
Why use heuristics for Bin Packing?
Optimal packing is hard; heuristics give quick, decent solutions.
What is the goal of data clustering?
To group similar items together based on a distance or similarity measure.