Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Comp Sci Algorithms > Exam 1 Deck > Flashcards

Exam 1 Deck Flashcards

1
Q

Fibonachi Time Complexity T(n)

A

If n<= 2 T(n) = 1 ELSE T(n)=2^n+1 - 1

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

Fibonachi Recursive Relation

A

T(n)= T(n-1) + T(n-2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q 
T(n)?  Big-0?
for(int i = 0; i < n; i++){
    for(int j = i+1; j< n; j++){
        Simple Statement
    }
}
A

T(n) = n(n-1)/2 => T(n) = 0.5n^2 - 0.5n

Big 0 => n^2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q 
T(n)?  Big-0?
for(int i=0; i<=n; i++){ 
    for(int j=1; j<=n; j++) {
        for(int k=n; k>=1; k--) {
            sum = i+j+k;
            cout<< sum << endl;
          }
    }
}
A

T(n) = 2 x n x n x (n+1) => 2n^3 + 2n^2

Big 0 => n^3

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

Master Theorem Case 1:
T(n)=
IF

A

If ( d > log[b] a )

T(n) = c * n^d

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

Master Theorem Case 2:
T(n)=
IF

A

If ( d = log[b] a )

T(n) = n^d * (log n)

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

Master Theorem Case 3:
T(n)=
IF

A

If ( d < log[b] a )

T(n) = n^(log[b] a)

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

Using Master Method:
T(n) = 9T(n/3) + n
What are a, b, c, d?
What is Big-O?

A 
a = 9 b = 3 c = 1 d = 1
Because d = 1 and log<3> 9 = 2
d < log<b> a
T(n) = n^(log<b> a) => n^(log<3> 9)
T(n) = n^2</b></b>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Using Master Method:
T(n) = T(2n/3) + 1
What are a, b, c, d?
What is Big-O?

A

a = 1 b=3/2 c= 1 d = 0
log<3/2> 1 = 0 and d = 0
d = log<b> a</b>

T(n) = n^0 * log n => 1 * log n
T(n) = log n</b>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Using Master Method:
T(n) = 3T(n/4) + n*log n
What are a, b, c, d?
What is Big-O?

A 
a = 3 b = 4 c= log n d = 1
log<b> a = log<4> 3 = x and  0 < x < 1
d > log<b> a
1 > x
T(n) = c * n^d 
T(n) = n*log n</b></b>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Using Master Method:
T(n) = 2T(n/2) + n
What are a, b, c, d?
What is Big-O?

A 
a = 2 b =2 c = 1 d = 1
log<2> 2 = 1
d= 1 
log<b> a = d
so
T(n) = (n^1) log n
T(n) = n log n</b>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Using Master Method:
T(n) = 8T(n/2) + n^2
What are a, b, c, d?
What is Big-O?

A 
a = 8 b = 2 c = 1 d = 2
log<2> 8 = 3
d < log<b> a => 2 < 3
so
T(n) = n^(log<b> a)
T(n) = n^3</b></b>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

List comparison sort algorithms:

A

Insertion Sort:

Merge Sort: A[n], B[m], C[n+m)

Heaps

Quick Sort

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

Which can have duplicate values? Heaps or Binary Search Trees?

A

Heaps

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

Last Child in a Heap is?

A

The LOWEST right child

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

Insertion Sort T(n) Best/Worst?

A

Best = T(n) = n -1

Worst: T(n) = n^2

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

Merge Sort T(n) Worst? Which variable are passed in?

A

Worst: W(n,m) = n+m-1 COMPARISONS
T(n) = nlog n - (n-1)
O(n) = nlog n
A[n], B[m], C[n+m)

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

Heaps Sort T(n) Worst? Build? Shrinking Cost? Insert/Increase Key? Return Max?

A 
Worst Building Cost = O(n)
Shrinking Cost = O(n log n)
Worst = O(n log n)
Priority Queue (Heap) functions
Increase Key (or insert) O(n) = log n
Return Max = O(n) = 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Which comparison sorts are Worst O(n) = n log n?

A

Heaps and Merge Sort (and on average not worst case Quick Sort)

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

Which comparison sorts are Worst O(n) = n^2

A

Insertion Sort and Quick Sort
Quick sort is only n^2 if the list is sorting such that A[n] < A[n+1]
Mostly Quick sort is n log n

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

BST n = max number of nodes in a tree of given height h. What is the function for n? What is the function for h? What is the worst time complexity?

A 
n = 2^h - 1
h = log (n+1)
O(n) = log n
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the O(n) for BST search?

A

O(n) = n

In general the O(n) = h

23
Q

How do you traverse a BST to create a vector?

A

start at furthest left child
local left-> parent -> local right -> parents parent -> parents right sibling ext

left -> parent -> right recursively basically

24
Q

How do you delete an item from a BST?

A

If the item is not present? Nothing

If the item is present in a leaf with no children then delete the leaf

If the item is in a node with 1 child then replace the child with the parent and delete the parent-now-child

if the item is in a node with 2 children: Find the largest item in the LEFT sub tree. Recursively remove it. Use it as parent of the two sub trees

25
Q

Calculate the BST cost?

A

Root of tree Cost = 0 + 1
Child cost = depth * probability of node
Tree cost = root + all children costs

26
Q

In a Huffman tree, the most frequent values used are closer to the _______ of the tree. Thus having a _____ amount of bits.

A

Top

Smaller/Lower

27
Q

In a Huffman tree, the least frequent values are stored closer to the ________ of the tree. Thus having a _____ amount of bits.

A

Bottom

Larger/Higher

28
Q

Huffman trees can be used to…

Used to represent what?

A

encode messages. used to represent characters

29
Q

ASCII has a _______ amout of bits for each character. Huffman has a _______ amount of bits for each character

A

fixed

dynamic

30
Q

Left edge has value of _ in a Huffman tree. Right edge has value of _ in a Huffman tree. Characters are stored in ______ nodes.

A

0
1
leaf

31
Q

How do we append Huffman characters bits?

A

Root->Leaf

32
Q

Count Sorting must be sorting ______ variable type. N input numbers are in a ________ _________.

A

Integers

Limited Range

33
Q

Counting Sort has 4 loops put them in order

A 
//fill helper array with 0s
for i = 0 to k
do C[i] = 0
//count the numbers that equal i
for i = 1 to n
do C[A[i]] = C[A[i]] + 1
//add them up so we can count their spots later
for i = 1 to k
do C[i] = C[i] + C[i-1]
//put the items in array B with C[i] and A[j]
for j = n downto 1
do{
i = A[j]
B[C[i]] = A[j]
C[i] = C[i] -1
} END
34
Q

What is the time complexity of the counting sort?

A

O(n) = n+k or just O(n) = n

35
Q

How to make counting algorithm work with negative numbers?

A

As long a they are negative integers its easy. Add the minimum number to all numbers, sort then subtract the minimum number out again.

36
Q

How do you do a radix sort?

A

Radix-Sort (A, d) // d = num of digits in largest number
for i = 1 to d
—–do Counting Sort on A on the ith digit
End

37
Q

What is the time complexity on Radix sort?

A

O(n) = d(n+k)
or
O(n) = n

38
Q

Bucket Sort Worst T(n)? Average case?

A 
O(n) = n^2
Average T(n) = n
39
Q

When should we use Counting Sort? When should we use Radix Sort? When should we use bucket sort?

A

Counting sort is good if the number range is not too big.

Radix is good if there are a low number of digits

Bucket sort is good for linked lists, and is dependent on your hasting function.

40
Q

What are the non-comparison sorting algorithms?

A

Counting, Radix, and Bucket

41
Q 
On average what is the O(n) of non-comparison sorts?
Counting O(n) ?
Radix O(n) ?
Bucket O(n) ?
A 
Mostly O(n) = n
Counting = O(n) = n+k
Radix = O(n) = d(n+k)
Bucket = O(n) = n^2 but on average = n
42
Q

How do we construct a Hoffman Tree?

A

Sort the array of characters by frequency
take the two lowest frequency items (A[1] and A[2]) add them together. That sum is compared to all the other values. Grab the two lowest and join them. When joining the smaller value goes on the left, larger on the right. Continue till tree is completed. Always join the two lowest frequencies.

43
Q 
Modify fibo to allow for dynamic programming
int fibo (int n)
if n <= 2
return 1
else 
return fibo (n-1) + fibo (n-2)
A

int fibo_init ( int n ) {
create array f[n]; //fill initial array with -1
for int i = 0; i < n; i++
f[i] = -1;
return fibo(n); // call the recursion function fibo
}

int fibo (int n)
if n<=2  // check if easy fibo
return 1;
else if f[n] != -1 {  //have we solved already?
return f[n];
}
else {
int answer = fibo(n-1) + fibo(n-2)
f[n] = answer;  //save the answer for future use
return answer;
}
44
Q

Matrix

A
r[1,1] r[1,2] r[1,3]
x
r[2,1] r[2,2] r[2,3]

x
B
t[1,1]
t[2,1] 
t[3,1]]

AB?

A

this is a 2x3 and a 3x1 = 2x1

so
M[1,1] = r11 x t11 + r12 x t21 + r13 x t31
M[2,1] = r21 x t11 + r22 x t21 + r23 x t31

45
Q

A : a x b
B : b x c
AB = ?

A

axc

46
Q 
Multiply
A
4     8     
0    2   
1     6

B
5 2
9 4

AB?

A

Can we? 3x2 x 2x2 = 3x2 yes
1 2=c 3x2= r x c
4x5 + 8x9 4x2 + 8x4 1
0x5 + 2x9 0x2 + 2x4 2
1x5 + 6x9 1x2 + 6x4 3=r

47
Q

What is the number of multiplications between AB if A = 12x2 and B = 2x2

A

AB number of multiplications would be 12 x 2 x 2= 48

48
Q

Number of ways we can multiply n matrix?

A 
C(n-1) = C(2n-2, n-1) /n
Cn = (2n)!/(n+1)!n!
49
Q

How many ways can you multiply 4 matrix?

A

C3 = 4 matrix multiply
6!/4! * 3!

6x5
——– = 5
3x2x1

50
Q 
For for a set of functions that we are trying to find the longest set of compatible activities what is:
Si
Fi
Li
Pi
A 
Si = start time of activity
Fi = finish time of activity
Li = longest set of compatible activities (number of|)
Pi = which activity is compatible with current activity i
51
Q

Where is an new item inserted into a heap? How do we restore heap-ness?

A

New items are inserted at the lowest and most left position. To restore heap-ness we look at the parent and swap if inserted value is larger. continue until not true.

52
Q

Where is an item removed from in a heap?

A

Always the top

53
Q

In a heap the item that is removed leaves a hole, what leaf/child moves to that hole? What do you do to restore heapness?

A

Lower right child. To restore heap-ness swap with child that is larger. Repeat until not true

Comp Sci Algorithms (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions