Chapters 1 & 5 (Algorithms)

Computer science

The study of algorithms. Includes:
1) Their hardware realization
2) Their software realization
3) Their formal and mathematical properties
4) 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