Brainscape's Knowledge GenomeTM

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


See full index

Algorithms and Complexity > Block 2: Trees and Advanced Data Structures > Flashcards

Block 2: Trees and Advanced Data Structures Flashcards

1
Q

what is an ADT?

A

Abstract Data Type

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

what is a data structure?

A

a concrete way of organising data in memory

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

what are 4 stack operations?

A

push(x), pop(), top(), isEmpty()

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

what is the order of a stack?

A

LIFO

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

what are 2 implementations of a stack?

A

linked list and dynamic array

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

what are 2 operations of a linked list?

A

push and pop

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

what is the theta value of a linked list?

A

Θ(1)

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

what is the average theta value of a dynamic list?

A

Θ(1)

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

what is the worst case of an operation on a dynamic list?

A

Θ(n)

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

What are the 4 queue operations?

A

Enqueue(x), dequeue(), Front(), isEmpty() or size()

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

What order does a queue work in?

A

FIFO

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

What are 2 applications of queues?

A

Buffering, Breadth-first Search

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

what operations do we expect small ADTs to have?

A

add(x), min(), max(), contains(x), delete(x)

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

what ADT did we cover in last year’s CS1860?

A

sets

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

What is a map ADT also known as?

A

dictionary / associative array

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

what is an unordered implementation of an ADT?

A

Hashtable

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

What is an ordered implementation of an ADT?

A

Balanced Binary Search Tree

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

What is the main concept of a binary tree?

A

the left subtree contains smaller values, and larger values are on the right

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

what operations do we look at for BSTs?

A

insert(x), lookup(x), min(), max(), successor(x), delete(x)

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

what time does any operation on a BST take maximum?

A

O(h) where h is the height of the tree

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

what is the best height for a tree with n elements?

A

O(log n)

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

what is the worst height for a tree with n elements?

A

n-1

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

how do you remove t from a BST if t is a leaf?

A

just remove it

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

how do you remove t from a BST if it isn’t a leaf but has no left child? What if has no right child?

A

replace t with t.rightchild. vice versa for no right child.

25
Q

How do you delete a node t that has 2 children in a BST?

A
  1. find the largest node t2 in subtree t.leftChild
  2. delete t2 from subtree t.leftChild
  3. insert t2 in the place of t
26
Q

what is the time complexity of deleting a node with 2 children from a BST?

A

O(h)

27
Q

what is a rotation?

A

way to change structure of the tree, with few, local changes, without breaking the order property

28
Q

what are 3 strategies for a self-balancing tree?

A

AVL trees, Red-Black trees, Splay trees

29
Q

what is the AVL property?

A

for any node t, the height of the subtrees t.leftChild and t.rightChild differ by at most 1.

30
Q

What is the equation for balance?

A

balance(t) = height(t.leftChild) - height(t.rightChild)

31
Q

summarise the ADT sorting algorithm in 3 steps

A
  1. insert every item of the list into a data structure X
  2. start with item X.min()
  3. read out items in order using item = X.successor(item)
32
Q

what is the definition of a set?

A

A set is a collection of distinct objects, considered an object in its own right

33
Q

what are the set operations?

A

insert(x), delete(x), contains(x)

34
Q

what are the 2 java implementations of sets?

A

TreeSet and HashSet

35
Q

what 2 attributes do you need to add to each node to apply maps to a BST?

A

node.key and node.value

36
Q

operations of a BST using a map?

A

containsKey(key), get(key), put(key, value), remove(key)

37
Q

what are the inefficient methods in a BST using a map?

A

minValue and containsValue, as values are not ordered

38
Q

do hash tables support ordering?

A

no

39
Q

what is the average time complexity for hashMap operations?

A

O(1) / constant time

40
Q

what are hash tables a perfect implementation of?

A

unordered sets and maps

41
Q

what are the 2 values of a hash table?

A

size and capacity

42
Q

what are slots in a hash table called?

A

hash buckets

43
Q

what is the process for insertion into a hash table?

A
  1. compute hash(x)
  2. find hash bucket h%m
  3. if empty good, if not we need collision handling
44
Q

what is the process for looking up a value in hash table?

A
  1. compute hash(x)
  2. find hash bucket h%m
  3. if it contains x or is empty, we know if x is in the hash table
45
Q

what are the 2 principles for handling collisions?

A

chaining and open addressing

46
Q

what is chaining?

A

placing colliding keys outside of the main table. used in java. each slot is the start of a linked list of table entries.

47
Q

what is open addressing?

A

placing colliding keys inside the table, in a new slot.

48
Q

what are the advantages of open addressing over chaining?

A

less memory usage, better data locality

49
Q

what do cryptographic hash functions do?

A

convert file to a “fingerprint” bitstring

50
Q

ideally, what is a hash function?

A

uninvertible and infeasible to find a similar pair

51
Q

what are the desired properties of our hash functions?

A

> easy to compute
reasonably irregular
few collisions even with non-random data
consistent with equals

52
Q

what does immutable mean?

A

unchangeable

53
Q

what is the heap property?

A

every node in the tree contains a smaller value than both its children

54
Q

what is the worst case time complexity of heapsort?

A

O(n log n)

55
Q

what are the operations for a min-priority queue?

A

insert(x), minItem(), deleteMin()

56
Q

what are the operations for a max-priority queue?

A

insert(x), maxItem(), deleteMax()

57
Q

what is the running time of sifting up or down?

A

O(log n)

58
Q

what ADT is used for priority queues?

A

heaps

Algorithms and Complexity (3 decks)

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