Block 1: Introduction and Basic Concepts

Question 1

Define an algorithm

Answer 1

A specific procedure for solving a specific task

Question 2

5 things that impact the running time of a program

Answer 2

> programming language
> hardware
> pattern
> size of the input data
> algorithm used

Question 3

what does f(n) = O(g(n)) roughly mean?

Answer 3

f(n) < c * g(n), for some constant c, large enough n

Question 4

describe the model we use for reasoning about program speed?

Answer 4

> 1 CPU core (single thread)
sequential
primitive operations take unit time

Question 5

define running time

Answer 5

the number of steps it takes to finish for data of size n.

Question 6

Worst Case

Answer 6

the longest time the algorithm takes for size n

Question 7

Best Case

Answer 7

the shortest time the algorithm takes for size n

Question 8

Average Case

Answer 8

the expected time for size n

Question 9

O(f(n)) (big-oh)

Answer 9

upper-bound: time(n) < c * f(n)

Question 10

Ω(f(n)) (omega)

Answer 10

lower bound: time(n) > c * f(n)

Question 11

Θ(f(n)) (theta)

Answer 11

upper and lower bound

Question 12

Big-oh of selection sort

Answer 12

O(n^2)

Question 13

Worst case of insertion sort

Answer 13

O(n^2)

Question 14

Best case of insertion sort

Answer 14

O(n)

Question 15

Big oh of merge subroutine

Answer 15

O(n)

Question 16

Big oh of mergesort

Answer 16

O(nlogn)

Question 17

1 + 2 + 3 + 4 + … + n

Answer 17

(n(n+1))/2 ~ n^2 / 2

Question 18

what are 2 sources of log n?

Answer 18

if something is repeatedly doubled or halved.

Question 19

does the basis of a logarithm matter?

Answer 19

no

Question 20

formal definition of big-oh

Answer 20

f (n) = O(g(n)) as n → ∞ if and only if:
There exist constants c > 0, n0 ≥ 0 such that
for every n ≥ n0 we have f (n) ≤ c · g(n)

Question 21

3n^2 + 6nlogn + n

Answer 21

Θ(n^2)

Question 22

8logn + 4n

Answer 22

Θ(n)

Question 23

sort into increasing speed of growth:
> n log n
> n / (log n)
> 2^n
> log n
> n
> n^2
> n^1000
> n!
> 1

Answer 23

> 1
> log n
> n / (log n)
> n
> n log n
> n^2
> n^1000
> 2^n
> n!

Question 24

sorting algorithms:

? is faster than ? is faster than ?

Answer 24

insertion sort, merge sort, selection sort

Question 25

what is a recursive algorithm?

Answer 25

an algorithm that calls itself on smaller data to solve a problem.

Question 26

define base case

Answer 26

where the recursion bottoms out. and the problem is simple enough to be solved directly.

Question 27

3 things that happen when a recursive call is made

Answer 27

1. the current state is remembered (put on call stack)
2. new working space is created for the next function
3. after the called function returns, the calling function resumes

Question 28

What does the running time of quicksort strongly depend on?

Answer 28

getting balanced splits

Question 29

unlucky quicksort big oh

Answer 29

O(n^2)

Question 30

what is the likely big oh of quicksort with a random pivot element?

Answer 30

O(n log n)

Question 31

add new item to the start of a list

Answer 31

Θ(n)

Question 32

delete item at the start of a list

Answer 32

Θ(n)

Question 33

add new item at the end

Answer 33

Θ(1)

Question 34

delete item at the end

Answer 34

Θ(1)

Question 35

add/delete at position i

Answer 35

Θ(n - i)

Question 36

get/set at position i

Answer 36

Θ(1)

Question 37

disadvantage of linked lists

Answer 37

harder to navigate:
> no random access
> not local in memory

Question 38

advantage of linked lists

Answer 38

easier to modify and extend:
> insets/delete in constant time
> can even delete items from the middle

Question 39

What are the 4 stages to delete a node in a linked list?

Answer 39

1. node.prev.next = node.next
2. node.next.prev = node.prev
3. node.prev = null
4. node.next = null

Question 40

What are the stages to inset node2 after node1?

Answer 40

1. node2.next = node1.next
2. node2.prev = node1
3. node1.next.prev = node2
4. node1.next = node2

Question 41

What linked list operations take constant time?

Answer 41

insertFirst, insertLast, deleteFirst, deleteLast, deleteNode (if you already have the node pointer)

Question 42

What linked list operations take linear time?

Answer 42

locate an item by value, access the ith item, delete an item by value