Studied by 1933 peopleComputer science
The study of algorithms. Includes:
Their hardware realization
Their software realization
Their formal and mathematical properties
Their real world applications
Found in lecture Chapter 1 - Alg 1
pseudocode
a flexible notation that lies between the two extremes of natural language and real code
it should be clear, effectively computable, and unambiguous
Found in lecture Chapter 1 - Alg 1
algorithm
step-by-step instructions for solving a problem
Found in lecture Chapter 1 - Alg 1 and zyBook Section 5.1
analysis of algorithms
the study of the efficiency of algorithms
Found in lecture Chapter 1 - Alg 2
sequential search
search algorithm where we linearly look at each element in the list until we find what we are searching for or reach end of list Complexity: best = O(1) [first item in list], avg/worst = O(n) [have to go through entire list]
Found in lecture Chapter 1 - Alg 2
Big O
used to describe an algorithm's performance/execution time as input grows to infinity
Found in lecture Chapter 1 - Alg 2
binary search
Used with a SORTED list. Look at middle element and compare to what we are searching for. If not the middle, repeat with the half of the list our element will be in. If the list is not sorted, try sequential/linear search instead. Complexity: best = O(1), [middle element] avg/worst = O(log n)
Found in lecture Chapter 1 - Alg 2
selection sort
Sorting algorithm that searches through list for max/min value. Place element in correct location and repeat for the rest of list. Complexity: O(n^2) in best, avg, and worst cases
Found in lecture Chapter 1 - Alg 3
desirable properties of an algorithm
Easy to use
Elegance
Efficiency
Correctness
goals for purchasing a car = algorithm desirable properties
Found in lecture Chapter 1 - Alg 3
time efficiency
the amount of time an algorithm takes to execute
Found in lecture Chapter 1 - Alg 4
space efficiency
the amount of information an algorithm must store to execute
Found in lecture Chapter 1 - Alg 4
Note
Flashcard