Final Flashcards

(28 cards)

1
Q

What is an algorithm?

A

A step-by-step procedure used to solve a problem or perform a task.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does Big-T (T(n)) represent?

A

The exact count of primitive operations an algorithm performs for input size n.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does Big-O represent?

A

An upper bound on an algorithm’s time complexity in the worst case.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a heuristic?

A

A rule of thumb or strategy guiding search to good solutions when exact methods are too slow.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is an example of a heuristic?

A

Using Manhattan distance in A* to estimate distance to the goal.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the difference between P and NP?

A

P = solvable in polynomial time. NP = verifiable in polynomial time. P ⊆ NP.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How are NP-Complete problems solved?

A

Using heuristics or approximations like GA or SA, since exact solutions are too slow.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a local minimum?

A

A solution better than its neighbours but not the best globally.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a fitness function?

A

A function that evaluates the quality of a solution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a search space?

A

All possible candidate solutions to a problem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is an invalid solution?

A

A solution that violates problem constraints.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Define Hill Climbing.

A

Greedily improves solution by exploring neighbours.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Define Random Mutation Hill Climbing (RMHC).

A

Like Hill Climbing but uses random mutation to generate neighbours.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Define Stochastic Hill Climbing (SHC).

A

Accepts worse solutions with some probability to escape local optima.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define Random Restart Hill Climbing (RRHC).

A

Runs HC multiple times from random starting points to improve results.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Define Simulated Annealing (SA).

A

Accepts worse solutions early on; cooling temperature reduces acceptance over time.

17
Q

Define Iterated Local Search (ILS).

A

Perturbs local optima and re-applies local search to escape traps.

18
Q

Define Genetic Algorithms (GA).

A

Population-based method using crossover, mutation, and selection.

19
Q

Define Evolutionary Programming (EP).

A

Similar to GA but uses mutation and tournament selection; no crossover.

20
Q

Define Particle Swarm Optimisation (PSO).

A

Particles adjust position based on personal and global best; inspired by bird flocking.

21
Q

Define Ant Colony Optimisation (ACO).

A

Ants explore paths with pheromones, leading others to good routes.

22
Q

Why use heuristics for TSP?

A

TSP has too many permutations to brute-force. Heuristics find good-enough solutions efficiently.

23
Q

Why use heuristics for Bin Packing?

A

Optimal packing is hard; heuristics give quick, decent solutions.

24
Q

What is the goal of data clustering?

A

To group similar items together based on a distance or similarity measure.

25
What is the FFD bin packing method?
Sort items decreasingly, place each in the first bin it fits. Open new bins if needed.
26
What is Genetic Programming?
An evolutionary method where entire programs are evolved using mutation and crossover.
27
What is uniform crossover?
Each gene has a 50% chance of being inherited from either parent; creates more diversity.
28
Describe K-means in words.
An algorithm that assigns data into K clusters by minimising distances to cluster centres.