Studied by 2 people
how does selection sort work?
finds the minimum element from unsorted part of the array and puts it at the beginning (i = 1)
repeats (searches i+1 → n values since you don’t need to check the front values) until the whole list is sorted
what is the code for a bubble sort?
how can the code for a bubble sort be improved?
reduce the list size at each iteration
n - 2 - i
what algorithms are needed for a quick sort?
QuickSort(list,first,last)
PivotList(list,first,last)
what is the code for a QuickSort?
what is the code for a PivotList?
how does radix sort work?
first sort by the least significant bit
the input is split into different sets based on the bit
for binary: 2 sets (digit is 0 or digit is 1)
for integer: 10 sets (0,1,2,3,4,5,6,7,8,9) → or,, int values need to be converted to a binary digit????
the ordering of the data as they are put into the sets must be maintained
going from left to right, take out the values in each set to reform the list (eg. each set is a queue, clear queue 0 first, then queue 1)
repeat the process by looking at the next least significant bit
continue until we run out of bits to analyse
what is the code for a depth first search?
what is the code for an exhaustive search?
how does a breadth first search work?
uses a heuristic (improved process) to decide which node is explored next eg. expanded in order of lowest cost
how does an A* search work?
2 estimates must be made
G the cost of the partial path (from the start to the node we are currently at)
H estimated cost of how far is left from the current path node [NOT START] to the goal state - underestimate used/ lower bound on how far to travel
select the start
select the partial path point
do g + h = f for each neighbour
choose the path with the lowest f value (eg. A chosen instead of B)
repeat the steps until the end goal is reached
what is the code for Prims Algorithm for MST
Example of Prims Algorithm
what is the code for Dijstra’s Algorithm?
implemented with 3 stacks
what is the code for the Floyd-Warshall algorithm?
what is the code for the fitness function for the scales problem?
what is the code for Random Mutation Hill Climbing?
what is needed for RMHC?
random start point → start solution (binary string)
small change operator → modify the current solution
number of iterations we want to run the algorithm for
what is the code for the RandomStart algorithm for RMHC?
used to generate a random start solution to the scales problem/ random binary string
what is the code for the SmallChange algorithm for RMHC?
used to choose a random weight and reverse the side it is on for the scales problem
how does random restart hill climbing work?
variation of random hill climbing
run normal RMHC n times and get the best fitness
we start off in different sections of the search space
For example we might run it 10 times for 100 iterations rather than once for 1,000 iterations
how does stochastic hill climbing work?
improvement on random hill climbing
allows us to accept worse fitness functions in order to avoid getting stuck at local optimas
uses acceptance function to determine if we accept a solution during the search- based on how bad the change in fitness is
current fitness - next fitness = change in fitness
very bad change = small chance of acceptance
slightly bad change = more often accepted
relies on a decision function
how does simulated annealing work?
improvement on random hill climbing
accepts worst solutions to circumnavigate local maximums
annealing - chance of accepting worse solution reduces as algorithm progresses
annealing process is simulated through maintaining a slow decreasing temperature
This temperature should reach zero at the end of the algorithm’s run
If temperature is very high: the algorithm is more likely to accept worst solutions
If temperature is zero: the algorithm behaves like HC – accepts better solutions
Note that the parameters T0 (starting temperature) and λ (cooling rate) need defining, along with the acceptance function PR
what is the code for simulated annealing?
what is the code for Holland’s GA Algorithm?
what is the code for the evolutionary programming algorithm?
what is the code for the K-Means Algorithm?
what algroithms are needed to solve the TSP?
RandomPerm - creates a random permutation of cities where each city is in the perm only once
Swap - makes a small change, swaps the position of 2 cities in the permutation
what is the code for the RandomPermutation algorithm?
what is the code for the Swap algorithm?
![<p>2 estimates must be made</p><ul><li><p><mark data-color="red">G</mark> the cost of the partial path (from the start to the node we are currently at)</p></li><li><p><mark data-color="red">H</mark> estimated cost of how far is left from the current path node [NOT START] to the goal state - underestimate used/ lower bound on how far to travel</p></li></ul><p></p><ol><li><p>select the start</p></li><li><p>select the partial path point</p></li><li><p>do g + h = f for each neighbour</p></li><li><p>choose the path with the lowest f value (eg. A chosen instead of B)</p></li><li><p>repeat the steps until the end goal is reached</p></li></ol>](https://knowt-user-attachments.s3.amazonaws.com/b37e333451c744b4a11bb24e4e896816.jpeg)
Note 
Flashcard (79)