Algorithm - ANSWER-A systemic and unambiguous procedure that produces (in a finite
number of steps) the answer to a problem
-Understandable to both humans and computers
-Must have a clear input that satisfies specific conditions
What do algorithms produce? - ANSWER-Output- solution to the problem
-Also have clear conditions
What do good algorithms have? - ANSWER-1. Correctness- returns the right solution
2. Speed- time it takes to solve a problem- cannot be too long
3. Space- amount of memory used- cannot take up too much memory
4. Simplicity- easy to understand and analyze, easy to implement, easy to debug,
modify, implement
Running time - ANSWER-Speed of an algorithm/program
What does running time depend on? - ANSWER-1. Size of input- longer when input is
larger
2. Content of input- instance of the problem
Running time n - ANSWER-n = set of numbers at the number n- n numbers
Cases of running time - ANSWER-1. Best case- easiest input (like an in-order list) so
the time is shortest- meaningless since this rarely happens
2. Worst case- hardest input (out-of-order list) so the time is longest- means the most
because this is what the Big O is judged on and what you calculate to make the overall
algorithm shorter
3. Average case- time of average case, hard to find
Languages for describing algorithms - ANSWER-1. English prose- paragraph- human
readable but too vague/verbose
2. Binary language- precise but not human readable
3. Programming language- precise, human readable, needs knowledge of language and
implementation
, Pseudo-code - ANSWER-Universal language to describe algorithms to humans- not any
specific language like programming language
Assignments - ANSWER-x <- x + 1
Conditions - ANSWER-If (x = 0) then...
Loops - ANSWER-For i <- 0 to n do...
Objects/function calls - ANSWER-triangle.getArea()
Mathematical notiation - ANSWER-x <- [y^3/2]
Blocks - ANSWER-Indentation
Sorting - ANSWER-Getting numbers in a random order and sorting them in increasing
or decreasing order
Runtime of bubble sort, selection sort, insertion sort - ANSWER-O(n^2)
Runtime of merge sort, heap sort, quick sort - ANSWER-O(nlogn)
Bubble sort - ANSWER-Loop/iterate through the list many times; for each iteration
through the list, if 2 neighboring elements are in the wrong order, swap them
Swapping variables - ANSWER-Use a temporary variable:
tmp = y;
y = x;
x = tmp;
Pseudocode for bubble sort - ANSWER-for ct = 0 to n - 1{
for i = 0 to n - 2 - ct{
if list[i] > list[i + 1]
swap(list[i], list[i + 1])
}
}
ct - ANSWER-Counter- makes bubble sort go through the list of numbers n-1 times and
sort it each time
n - ANSWER-Number of elements in the list
n - 1 - ANSWER-Number of elements in array because array starts at 0
n - 2 - ct - ANSWER-Removing the numbers you just did when you go through the list-
since the last element will be in place at the end of the list after each time you do it, so
you can ignore doing the last space
-n - 2 because you don't have to do the last place in the first place, as well as that the
array starts at 0
Selection sort - ANSWER-List is divided into parts- the sorted list and the rest of the
elements
The sorted list is empty and all the elements are in the second list
Repeated n times: find the smallest number in the list and add it to the empty sorted list
Add numbers to the sorted list, which is just the beginning of the old list, by swapping
the smallest elements with the elements whose places you're replacing
Selection sort image - ANSWER-
Selection sort pseudo code - ANSWER-for i to n - 2{
tmpIndex = i //first element of the list
tmpMinValue = list[i] //makes the i (first) element of the list the minimum value
for k = i + 1 to n - 1{
if (list[k] < tmpMinValue){ //if each element after i is smaller than the tmpMin make it the
new tmpMin
number of steps) the answer to a problem
-Understandable to both humans and computers
-Must have a clear input that satisfies specific conditions
What do algorithms produce? - ANSWER-Output- solution to the problem
-Also have clear conditions
What do good algorithms have? - ANSWER-1. Correctness- returns the right solution
2. Speed- time it takes to solve a problem- cannot be too long
3. Space- amount of memory used- cannot take up too much memory
4. Simplicity- easy to understand and analyze, easy to implement, easy to debug,
modify, implement
Running time - ANSWER-Speed of an algorithm/program
What does running time depend on? - ANSWER-1. Size of input- longer when input is
larger
2. Content of input- instance of the problem
Running time n - ANSWER-n = set of numbers at the number n- n numbers
Cases of running time - ANSWER-1. Best case- easiest input (like an in-order list) so
the time is shortest- meaningless since this rarely happens
2. Worst case- hardest input (out-of-order list) so the time is longest- means the most
because this is what the Big O is judged on and what you calculate to make the overall
algorithm shorter
3. Average case- time of average case, hard to find
Languages for describing algorithms - ANSWER-1. English prose- paragraph- human
readable but too vague/verbose
2. Binary language- precise but not human readable
3. Programming language- precise, human readable, needs knowledge of language and
implementation
, Pseudo-code - ANSWER-Universal language to describe algorithms to humans- not any
specific language like programming language
Assignments - ANSWER-x <- x + 1
Conditions - ANSWER-If (x = 0) then...
Loops - ANSWER-For i <- 0 to n do...
Objects/function calls - ANSWER-triangle.getArea()
Mathematical notiation - ANSWER-x <- [y^3/2]
Blocks - ANSWER-Indentation
Sorting - ANSWER-Getting numbers in a random order and sorting them in increasing
or decreasing order
Runtime of bubble sort, selection sort, insertion sort - ANSWER-O(n^2)
Runtime of merge sort, heap sort, quick sort - ANSWER-O(nlogn)
Bubble sort - ANSWER-Loop/iterate through the list many times; for each iteration
through the list, if 2 neighboring elements are in the wrong order, swap them
Swapping variables - ANSWER-Use a temporary variable:
tmp = y;
y = x;
x = tmp;
Pseudocode for bubble sort - ANSWER-for ct = 0 to n - 1{
for i = 0 to n - 2 - ct{
if list[i] > list[i + 1]
swap(list[i], list[i + 1])
}
}
ct - ANSWER-Counter- makes bubble sort go through the list of numbers n-1 times and
sort it each time
n - ANSWER-Number of elements in the list
n - 1 - ANSWER-Number of elements in array because array starts at 0
n - 2 - ct - ANSWER-Removing the numbers you just did when you go through the list-
since the last element will be in place at the end of the list after each time you do it, so
you can ignore doing the last space
-n - 2 because you don't have to do the last place in the first place, as well as that the
array starts at 0
Selection sort - ANSWER-List is divided into parts- the sorted list and the rest of the
elements
The sorted list is empty and all the elements are in the second list
Repeated n times: find the smallest number in the list and add it to the empty sorted list
Add numbers to the sorted list, which is just the beginning of the old list, by swapping
the smallest elements with the elements whose places you're replacing
Selection sort image - ANSWER-
Selection sort pseudo code - ANSWER-for i to n - 2{
tmpIndex = i //first element of the list
tmpMinValue = list[i] //makes the i (first) element of the list the minimum value
for k = i + 1 to n - 1{
if (list[k] < tmpMinValue){ //if each element after i is smaller than the tmpMin make it the
new tmpMin
