CompSci Unit 5 - Algorithms

5.1

  • algorithm - a finite set of instructions to accomplish a task

    • all algorithms are made up of:

    • sequencing - following stpes in order

    • selection - making decisions on which steps ot execute next (if statements)

    • iteration - repeating sme steps (loops)

  • problem is a task, something we want to do. they can smetimes be solved with algorthms. an instance of a problem includes specific input

  • standard algorithms that utilize list traversals

  • decidable problem - a decision problem for which an algorthim can be written to produce a correct output for all inputs/instances

  • undecidable - a problem or which no algorthim can be constructed that is always capable of prviding a correct yes/no answer

5.2

  • earching - looking for a value within a collection of data

    • linear/sequential search - checks each element of a list in order until desired value is found, or all elements in list have been checked (ex: has12)

    • binary search - checks hte middle value and eliminates half values an chooses new midddle until it chooses the correct number.

      • only works on sorted data

5.3

  • selection sort - select what should be at index wap whats there with what should be there found by going through whole list, repeat for every other index until in order

  • insertion sort - traverse list and compare each value with teh value that comes immediately before, moves each value left until its inserted into teh correct location, repeats for other indexes

    • can be faster than selection

5.5

  • efficiency - a measure og how many steps are needed to complete an algorithm in the worst case scenaio

    • linear efficiency - given list size n will run n times — runs in linear time

    • binary efficiency - given list size of n algorthim will run max log2n times — logarithmic time

    • insertion/selecion efficiency (worst case) - runs max (n2 - n)/2 times — polynomial time (n2) — unreasonable

    • exponential efficiency - list size n has 2n subsets to be found — exponential time

  • brute force algorthm - calculates the distance of every possible route and identify the shortes one

    • fiven list of n cities, find n! routes — factorial time — unreasonable

5.6

  • decision problem - problem with a yes/no answer

  • optimization problem - problem wiht goal of finding best solution

  • heuristic - an algrthim used that is good enough and runs in reasonable time

    • when algorthim is: inpossible (undecidable) or impractical (unreasonable time)