Chapters 1 & 5 (Algorithms)
4.6(47)
Studied by 1934 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
FlashcardsCard Sorting
1/10
Earn XP
Description and Tags
Last updated 3:47 PM on 10/3/22
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
11 Terms
1
New cards
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
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
2
New cards
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
it should be clear, effectively computable, and unambiguous
Found in lecture Chapter 1 - Alg 1
3
New cards
algorithm
step-by-step instructions for solving a problem
Found in lecture Chapter 1 - Alg 1 and zyBook Section 5.1
Found in lecture Chapter 1 - Alg 1 and zyBook Section 5.1
4
New cards
analysis of algorithms
the study of the efficiency of algorithms
Found in lecture Chapter 1 - Alg 2
Found in lecture Chapter 1 - Alg 2
5
New cards
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
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
6
New cards
Big O
used to describe an algorithm's performance/execution time as input grows to infinity
Found in lecture Chapter 1 - Alg 2
Found in lecture Chapter 1 - Alg 2
7
New cards
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
Complexity:
best = O(1), [middle element]
avg/worst = O(log n)
Found in lecture Chapter 1 - Alg 2
8
New cards
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
Complexity: O(n^2) in best, avg, and worst cases
Found in lecture Chapter 1 - Alg 3
9
New cards
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
- Elegance
- Efficiency
- Correctness
goals for purchasing a car = algorithm desirable properties
Found in lecture Chapter 1 - Alg 3
10
New cards
time efficiency
the amount of time an algorithm takes to execute
Found in lecture Chapter 1 - Alg 4
Found in lecture Chapter 1 - Alg 4
11
New cards
space efficiency
the amount of information an algorithm must store to execute
Found in lecture Chapter 1 - Alg 4
Found in lecture Chapter 1 - Alg 4
