Compsci Unit 5 - Algorithms

Algorithm

a finite set of instructions to accomplish a task

sequencing

following steps in order (order of lines of code)

selection

making decisions on which step to execute next (if statement)

iteration

repeating some steps (loops)

problem

task that we want to do

• some problems can be solved with an algorithm, and some can’t

decidable problem

a decision problem for which an algorithm cna be written to produce a correct output for all inputs or instances

undecidable problem

a problem for which no algorithm can be constructed that is always capable of providing a correct yes or no answer

• may have some instances, but cannot solve ALL instances

searching

looking for a value or information within a collection of data

linear/sequential search

check each element of a list, in order, until the desired value is found or all elements in the list have been checked

1. use a loop, traverse the list

2. compare each value to what you are searching for within an if statement

3. add other program code based on the problem you are solving

binary search

only works on sorted data

runs in logramithic time

1. checks middle value to find out if too high or low

2. eliminated half the values

3. chooses the new middle

4. and repeats until found or eliminated all values

selection sort

1. travers the list and select what should be at index 0

2. swap whats there with what should be there

3. repeat for subsequent indexes

insertion sort

1. traverse the list and compare each value with the value that comes immediately before

2. move each value left until it is “Inserted” in the correct location

3. repeat for subsequent indexes

can be faster than selection sort

efficiency

a measure of how many steps are needed to complete an algorithm in the worst case scenario

linear time

given liat size n, alrogirthm will run a max of n times

insertion and selection sort run how many times?

in the worst case scenario, given a list size of in it will run max (n²-n)/2 times — polynomial time

exponential efficiency

given list of size n, 2^n subsets to be found (unreasonable)

brute force algorithm

calculate the distance of every possible route and identify the shortest one

given a list of n cities, will run n! times — factorial time (unreasonable)

decision problem

a problem with a yes/no answer

optimization problem

a problem with the goal of finding the “best” solution among many

heuristic

an algorithm used that is “good enough” and runs in reasonable time is when an exact algorithm is either impossible or impractical