Comp 250 Midterm Review

studied byStudied by 0 people
get a hint


1 / 167

encourage image

There's no tags or description

Looks like no one added any tags here yet for you.

168 Terms



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

New cards

What do algorithms produce?

Output- solution to the problem

-Also have clear conditions

New cards

What do good algorithms have?

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

New cards

Running time

Speed of an algorithm/program

New cards

What does running time depend on?

1. Size of input- longer when input is larger

2. Content of input- instance of the problem

New cards

Running time n

n = set of numbers at the number n- n numbers

New cards

Cases of running time

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

New cards

Languages for describing algorithms

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

New cards


Universal language to describe algorithms to humans- not any specific language like programming language

New cards



New cards


If (x = 0) then...

New cards


For i

New cards

Objects/function calls


New cards

Mathematical notiation


New cards



New cards


Getting numbers in a random order and sorting them in increasing or decreasing order

New cards

Runtime of bubble sort, selection sort, insertion sort


New cards

Runtime of merge sort, heap sort, quick sort


New cards

Bubble sort

Loop/iterate through the list many times; for each iteration through the list, if 2 neighboring elements are in the wrong order, swap them

New cards

Swapping variables

Use a temporary variable:

tmp = y;

y = x;

x = tmp;

New cards

Pseudocode for bubble sort

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])



New cards


Counter- makes bubble sort go through the list of numbers n-1 times and sort it each time

New cards


Number of elements in the list

New cards

n - 1

Number of elements in array because array starts at 0

New cards

n - 2 - ct

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

New cards

Selection sort

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

New cards

Selection sort image

New cards

Selection sort pseudo code

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

tmpIndex = k

tmpMinValue = list[k]



if (tmpIndex != i){ //if tmpIndex is smaller, swap

swap(list[i], list[tmpIndex])



New cards

for i to n-2

repeat n times

New cards

Selection sort passes

for i to n - 2

for k = i + 1 to n - 1

2 for loops

New cards

How many passes are there for the inner for loop?

n(n - 1)/2

New cards

Insertion sort

For k = 1 to n - 1; insert list element at index k into its correct position with respect to the elements at indices 0 to k - 1

Essentially, there is a sublist in the beginning that is sorted. As we go through every element, the current element we have is checked against every element in the sorted sublist and shift the greater numbers to the right. When it is compared to a smaller number, then the current element is inserted in the blank space

New cards

Insertion sort image

New cards

Insertion sort explaination

Essentially, for every pass through, it sorts the n number of elements. ex. if its the third (n = 3), then the first 3 elements of the list will be sorted with each other and the rest of the list will be untouched

New cards

Insertion sort pseudo code

for k = 1 to n - 1{

elementk = list[k]

i = k

while (i > 0) and list([i - 1] > elementK){

list[i] = list[i - 1] //copy to next

i = i - 1 //move over


list[i] = elementK //past in space


New cards

Best case of insertion sort

O(n) if list is sorted- terminates immediately after 1 pass

New cards

Worst case for insertion sort

O(n^2) if list is sorted backwards

1 + 2 + 3 + ... + n - 1 = n(n - 1)/2

New cards

Comparison of runtime of three methods

Depends on data and implementation (how swap is done, what type of lists are used, etc)

New cards

Iterative algorithm

Algorithm where a problem is solved by iterating (going step-by-step) through a set of commands, often using loops

New cards

Power algorithm

product = 1

for i = 1 to n do

product = product * a

Multiplies a to itself for n times to create a^n

New cards

Recursive algorithm

Algorithm is recursive if in the process it calls itself one or more times

New cards

Power algorithm using recursion

power(a, n)

if n = 0 return 1 //base case


previous = power(a, n-1) //keeps calling itself until n = 1

return previous * a //saves previous every time power is called and adds it to itself


New cards

Example: 7^4





n = 1

previous1 = 1*7 = 7

previous2 = 7*7 = 49

previous3 = 49*7 = 343

previous4 = 343*7 = 2401

New cards

Base case

Case that is easiest to solve, the "base" of a problem

-Write recursive algorithms to get to the base case and then work backwards

New cards

Recursive binary search

Returns 'key' if it is in the list using an array, a start/stop for a region to search, and the key to be found

Narrow the start/stop until you find the key

-Base case- once start/stop, start = key or if key is not there, return -1

-Recursion: create a mid in the start and stop- if the key = mid, return that

If the mid > key, key = binarySearch() using the mid as the stop

If the mid < key, key = binarySearch() using the mid as the start

New cards

Fibonacci sequence

Sequence of numbers where each number is the sum of the previous 2 that precede it

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

New cards

Fibonacci algorithm


n is the input of a normal number, fib(n) is the Fibonacci number at the nth position

Base cases- if n = 0 or 1, return 0 or 1

previous = 0 //store previous number

current = 1 //store current number

fori = 2 to n do{

tmpCurrent = current

current = current + previous

previous = tmpCurrent


return current

New cards

Recursive algorithm framework

1. Divide problem into subproblems

2. Conquer the subproofs by solving them recursively

3. Combine the solution of each subproblem into the solution of the original problem

New cards

Merge sort

Sort elements of an array of n numbers

1. Divide array into left and half halves

2. Conquer each side by recursively sorting them

3. Combine sorted left and right halves into a full sorted array

New cards

Merge sort solution

Create a new array the same size as the original

Compare 1st two numbers of each list

Put larger number in array, leaving the other one

Keep doing it until the array is empty/ filled

Copy array back into the original array

New cards

Merge sort explaination

Essentially, merge sort keeps splitting the lists until what remains is a list the size of 1. Then it adds all those lists back together while ordering them

New cards

Merge sort pseudo code

if(left < right){

mid = left + right / 2

mergeSort(A, left, mid) // sorts left side

mergeSort(A, mid, right) // sorts right side

merge(A, left, mid, right)


New cards

Induction proofs

Prove that for all n ≥ n0, P(n)

n = just variable n, standing for number of times that the code runs through

n0 = any arbitrary number

P(n) = proposition

New cards

How to prove P(n)?

Use induction starting at a base case P(n0) aka prove n0 for P(n), then prove P(n0 + 1) as once you prove n + 1, it is logical that the rest should follow

New cards

Induction proof steps

1. Find the base case by making the equation = to given number

2. Get equations k and k + 1

3. Solve k + 1 by referring back to k equation

4. Make it equal to the equation given

New cards

Loop invariants

Prove that an algorithm will always work

New cards

What is an algorithm described by?

1. Input data

2. Output data

New cards


Specifies what restrictions to put on input data- parameters of what we put in

New cards


Specifies what is the result- parameters of what is put out

New cards

When is an algorithm correct?

1. Correct input data stops and produces correct output

2. Correct input and output data satisfies precondition and postcondition

New cards

Loop invariant

Loop property that holds before and after each iteration of a loop

-properties of loop hold before and after each iteration

-Variable must be true before and after loop

New cards

Proof using loop invariants: show

1. Initialization: it is true before initialization of loop

2. Maintenance: if it was true before, it must be true for the next iteration

3. Termination: if it stops and shows if algorithm is correct

New cards

Base case of loop invariant

Invariant holds before first loop

New cards

Inductive step of loop invariant

Invariant holds after first loop

New cards

Termination of a loop invariant

Stop induction when loop terminates instead aof going to infinity

New cards


Total amount of time an algorithm takes to run- the sum of operation times as different operations have different times

New cards

Primitive operation times

Time is always the same, independent of the size of bigger problems solved

-Run in constant time

-Summation of all total time

New cards

Primitive operations

1. Tassign- assign a value to a variable; x

New cards

For/while loops

Multiply by number of iterations- n

New cards

Best case

Input that makes it go as fast as possible

New cards

Worst case

Input that makes it go as slow as possible

New cards

Primitive run time assumptions

Assume that each operation is compatible- all primitive operations is 1 unit

New cards

n(n + 1) / 2

i = 0 ∑ n - 1 > i

New cards

Selection sort worst case

1 + 15n + 5n^2

New cards

Big O notation

Describes how running time of algorithm increases as a function n (n size of problem) when n is large

New cards

What does Big O notation do?

1. Simplifies running times

2. Gets rid of terms that become insignificant when n is large

New cards


Complicated equation

New cards


Simpler equation you want to reduce f(n) to

New cards

When is f(n) Big O of g(n)

When f(n) < c*g(n) when c is a constant for all n0 → n

-Prove that f(n) will be smaller

New cards

How to prove that f(n) is not Big O of g(n)

f(n) > c*g(n) for n0 and c

New cards

Hierarchy of Big O classes

Smallest to largest

1. O(1)

2. O(logn)

3. O(√n)

4. O(n) → constant

5. O(n^k) if k > 1

6. O(a^n) exponential

O(1) ⊂ O(log n) ⊂ O(√n) ⊂ O(n) ⊂ O(n^k) ⊂ O(2^n)

New cards


sin(n) + 10, 100 → O(1)

Primitive operations

New cards


Linear functions

New cards

Shortcuts for Big O

1. Sum rule

2. Constant factors rule

3. Product rule

4. Exponential

5. Log I

6. Log II

New cards

Sum rule

If f(n) is O(g(n)) and h(n) is O(g(n)) then f(n) + h(n) is O(g(n)) as

ex. f(log(n)) → O(n) and h(n) → O(n) then f(log(n)) + h(n) → O(n)

When each term is Big O then the sum is Big O

New cards

Constant factors rule

If f(n) is Big O of g(n) then kf(n) is big O of g(n) for any factor k

Any polynomial less or equal to biggest polynomial n^k is O(n^k)

ex. 10n^3 is Big O of (n^3)

n^3 + 10n^2 + log(n) is O(n^3)

New cards

Product rule

If f(n) is O(g(n)) and h(n) is O(e(n)) then f(n)*g(n) is O(f(n)*e(n)) because...

New cards


n^x is O(a^n) for any x > 0 and a > 1

BUT a^n is not O(n^x)

ex. n^10000 is O(1.0001^n) yet the c and n0 will be large and 1.0001^n is not O(n^100000)

New cards

Log I

Since log(n^x) = xlog(n) then log(n^x) is O(log(n)) because you isolate the log(n) since constants don't matter

New cards

Log II

Loga(n) is O(logb(n))

New cards

Limit shortcuts

1. If lim n→∞ f(n) / g(n) = 0 then f(n) is O(g(n)) but g(n) is not O(f(n))

2. If lim n→∞ f(n) / g(n) = something that is not 0 then f(n) is O(g(n)) and g(n) is O(f(n))

3. If lim n→∞ f(n) / g(n) = +∞ then g(n) is O(f(n)) and but f(n) is not O(g(n))

4. If the limit doesn't exist, then we can't say anything

New cards

l'Hopital rule

limn→+∞ f(n)/g(n) = limn→+∞



New cards

Find runtime of recursive code

1. Establish a base case where you prove that t(1) is true

2. Use substitution approach starting with t(n), finding t(n - 1), t(n - 2), etc

3. Find the pattern between the t(n)s and establish a case with constant k

4. Plug in base case 1 using n - k = 1 therefore k = n - 1 with k as 1

5. Solve after plugging in t(1) for k

New cards

Quick sort

Divide: Choses a pivot- an element of the array- and the pivot divides into 2 groups: the smaller than pivot and smaller or equal of pivot

Conquer: recursively sorts each group

Combines: puts together both groups

New cards

Quick sort pseudo code

if (start < stop) then

pivot ← partition(A, start, stop)

quickSort(A, start, pivot-1)

quickSort(A, pivot+1, stop)

New cards

Runtime of quick sort

Faster than other algorithms- O(n^2) worst case, O(nlogn) average case when for other sorts the O(nlogn) is worst

New cards

Worst case of quick sort

When the pivot is the largest number- the pivot stays where it is because everything is to the left and choses the one right next to it on the left

New cards

What is the advantage it has over mergeSort

Constant in O(nlogn) is smaller than for constant of mergeSort O(nlogn) making it faster

New cards

In-place algorithm

Algorithm that uses a constant amount of memory in addition to what is used to store the input

Importance: if the algorithm itself uses a lot of memory, it doesn't want to grow that memory when it uses more input

New cards

In-place algorithms

Selection Sort, Intersection Sort- both just moving elements around

New cards

Explore top notes

note Note
studied byStudied by 3 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 13 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 8 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 39 people
Updated ... ago
4.0 Stars(1)
note Note
studied byStudied by 20 people
Updated ... ago
5.0 Stars(2)
note Note
studied byStudied by 189 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 13 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 156 people
Updated ... ago
5.0 Stars(1)

Explore top flashcards

flashcards Flashcard51 terms
studied byStudied by 21 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard124 terms
studied byStudied by 20 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard101 terms
studied byStudied by 4 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard55 terms
studied byStudied by 5 people
Updated ... ago
5.0 Stars(2)
flashcards Flashcard170 terms
studied byStudied by 6 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard153 terms
studied byStudied by 16 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard150 terms
studied byStudied by 37 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard50 terms
studied byStudied by 1 person
Updated ... ago
5.0 Stars(1)