Block 1: Introduction and Basic Concepts Flashcards

1
Q

Define an algorithm

A

A specific procedure for solving a specific task

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

5 things that impact the running time of a program

A
> programming language
> hardware
> pattern
> size of the input data
> algorithm used
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

describe the model we use for reasoning about program speed?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

define running time

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Worst Case

A

the longest time the algorithm takes for size n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Best Case

A

the shortest time the algorithm takes for size n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Average Case

A

the expected time for size n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Ω(f(n)) (omega)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Θ(f(n)) (theta)

A

upper and lower bound

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Big-oh of selection sort

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Worst case of insertion sort

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Best case of insertion sort

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Big oh of merge subroutine

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Big oh of mergesort

A

O(nlogn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

1 + 2 + 3 + 4 + … + n

A

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

18
Q

what are 2 sources of log n?

A

if something is repeatedly doubled or halved.

19
Q

does the basis of a logarithm matter?

20
Q

formal definition of big-oh

A

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)

21
Q

3n^2 + 6nlogn + n

22
Q

8logn + 4n

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

sorting algorithms:

? is faster than ? is faster than ?

A

insertion sort, merge sort, selection sort

25
what is a recursive algorithm?
an algorithm that calls itself on smaller data to solve a problem.
26
define base case
where the recursion bottoms out. and the problem is simple enough to be solved directly.
27
3 things that happen when a recursive call is made
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
28
What does the running time of quicksort strongly depend on?
getting balanced splits
29
unlucky quicksort big oh
O(n^2)
30
what is the likely big oh of quicksort with a random pivot element?
O(n log n)
31
add new item to the start of a list
Θ(n)
32
delete item at the start of a list
Θ(n)
33
add new item at the end
Θ(1)
34
delete item at the end
Θ(1)
35
add/delete at position i
Θ(n - i)
36
get/set at position i
Θ(1)
37
disadvantage of linked lists
harder to navigate: > no random access > not local in memory
38
advantage of linked lists
easier to modify and extend: > insets/delete in constant time > can even delete items from the middle
39
What are the 4 stages to delete a node in a linked list?
1. node.prev.next = node.next 2. node.next.prev = node.prev 3. node.prev = null 4. node.next = null
40
What are the stages to inset node2 after node1?
1. node2.next = node1.next 2. node2.prev = node1 3. node1.next.prev = node2 4. node1.next = node2
41
What linked list operations take constant time?
insertFirst, insertLast, deleteFirst, deleteLast, deleteNode (if you already have the node pointer)
42
What linked list operations take linear time?
locate an item by value, access the ith item, delete an item by value