Brainscape's Knowledge GenomeTM

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


See full index

COMP272 > Final > Flashcards

Final Flashcards

1
Q

explain the concept of data structures

A

collection of organized data eg. an integer is a type of data and an array of integers stored in the computer is a data structure

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

explain the concept of algorithms

A

step-by-step process that performs action on a data structure eg. finding the smallest integer in an array of integers

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

distinguish the difference between an interface and an implementation

A

interface- what a data structure does

implementation- how the structure does it

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

what is a FIFO queue?

A

first-in-first-out eg. checking out at the grocery store

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

what is a priority queue?

A

smallest element is always removed eg. emergency waiting room

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

what is a LIFO (stack) queue?

A

last-in-first-out eg. stack of plates

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

what is a USet?

A

a set of n distinct elements (no two elements are the same)

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

what is a SSet?

A

a sorted set

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

implement an ArrayStack

A

see notebook

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

implement an ArrayQueue

A

see notebook

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

implement an ArrayDeque

A

see notebook

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

implement a DualArrayDeque

A

see notebook

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

implement a RootishArrayStack

A

see notebook

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

what is the primary advantage and disadvantage of a linked list?

A

advantage- delete and insert in constant time

disadvantage- cannot get(i) and set(i,x) in constant time

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

implement add(x)/remove()/push(x)/pop() of a SLList

A

see notebook

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

what is the time complexity of a DLList for get(i)/set(i,x)/add(i,x)/remove(i)?

A

O(n)

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

implement a SkipListSSet

A

see notebook

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

implement a ChainedHashTable

A

see notebook

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

describe linear probing

A

on a linear hash table, if the index given by the hash function to store an element is already occupied, the next location is checked until an available location is found or the table is full

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

what are the two properties of hash code mappings?

A
  1. if x and y are equal, then x.hashCode() and y.hashCode should be equal
  2. if x and y are not equal, then the probability that x.hashCode() and y.hashCode() are equal should be very small
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

what is division hashing?

A

k % tableSize

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

what is multiplication hashing?

A

when you take k and multiply it by some number between 0 and 1 then take the decimal part and multiply that by the tableSize

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

what is folding hashing?

A

when you break an object into parts then add those parts together then do k % tableSize

eg. social security number
244 + 176 + 244 = k

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

what is radix transformation?

A

a hashing method where the base of a number is changed to form a new sequence of digits then the division method is applied

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

what is digit rearrangement?

A

a hashing method where the original sequence of numbers is somehow rearranged and then the division method is applied

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

what is length-dependent hashing?

A

when the key and length is combined in some way way to produce the index directly or a secondary step

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

what is mid-square hashing?

A

when the key is squared and the middle part is used

28
Q

what is quadratic probing?

A

a collision resolution technique where a quadratic function is used to determine the next location to try when the location provided by the hash function is occupied

29
Q

what is double hashing?

A

a collision resolution technique where a second hash function is used to determine the next location to try when the location given by the first hash function is occupied

30
Q

what is a recursive function?

A

a function that recursively calls itself until some condition is met

31
Q

what is in-order traversal of a binary tree?

A

left subtree, root, right subtree

32
Q

what is pre-order traversal of a binary tree?

A

root, left subtree, right subtree

33
Q

what is post-order traversal of a binary tree?

A

left subtree, right subtree, root

34
Q

what is breadth-first traversal of a binary tree?

A

start at the top and go left to right on each level like reading a book

35
Q

what is the depth of u on a binary tree?

A

the length of the path from u to the root

36
Q

what is the height of u on a binary tree?

A

the length of the LONGEST path from u to one of its descendants (leaf)

37
Q

implement add(x)/remove(x)/find(x) of a binary tree

A

see notebook

38
Q

implement add(x)/remove(x)/find(x) of a scapegoat tree

A

see notebook

39
Q

implement add(x)/delete(x)/find(x) of an AVL tree

A

see notebook

40
Q

what is the maximum height of a red black tree?

A

2 log n

41
Q

what is the disadvantage of red black trees?

A

the implementation is complex

42
Q

what are the two properties of 2-4 trees?

A
  1. the depth of all of the leafs is the same

2. all internal nodes have either 2, 3, or 4 children

43
Q

implement add(u)/remove(u) of a 2-4 tree

A

see notebook

44
Q

what are the two properties of red black trees?

A
  1. there are the same number of black nodes on the path from the root to each leaf
  2. along any path there are never two adjacent red nodes
45
Q

what are the two ways of simplifying a red black tree?

A
  1. always make the root black

2. make all external nodes (nil nodes of the leafs) black

46
Q

what is the left leaning property of a red black tree?

A

for any node u if u.left is black then u.right is black

47
Q

what is the time complexity of the operations add(x)/remove(x)/find(x) for a red black tree?

A

O(logn) worst case

48
Q

what is the time complexity for the fixUp methods for a red black tree?

A

O(m) where m is a sequence of add(x) and remove(x) operations

49
Q

what is the property of a binary heap?

A

a child must always be greater than its parent

50
Q

implement add(x)/remove() of a binary heap

A

see notebook

51
Q

which sorting algorithms are comparison-based?

A

merge-sort, quick-sort, heap-sort

52
Q

show how merge-sort works

A

see notebook

53
Q

show how quick-sort works

A

see notebook

54
Q

show how heap-sort works

A

see notebook

55
Q

show how a counting-sort works

A

see notebook

56
Q

for what operations does an adjacency matrix graph representation perform poorly for?

A
  • inEdges(i)

- outEdges(i)

57
Q

what is a disadvantage of an adjacency matrix representation of a graph?

A

uses a lot of memory

58
Q

what is the time complexity of the five operations on n adjacency matrix representation of a graph?

A
  1. addEdge(i, j)/removeEdge(i,j)/hasEdge(i,j) O(1)

2. inEdges(i)/outEdges(i) O(n)

59
Q

what is the time complexity of the space used by an adjacency matrix representation of a graph?

A

O(n^2)

60
Q

implement breadth-first traversal of a graph

A

see notebook

61
Q

implement depth-first traversal of a graph

A

see notebook

62
Q

implement a binary trie with integers 3, 9, 12, and 13

A

see notebook

63
Q

describe how remove() of a binary tree is performed

A

if the node to remove has no children then is is simply removed

if the node only has one child then the node is spliced

if the node has two children then the smallest node that is greater than the node to remove that has no children is swapped

64
Q

what condition determines the scapegoat in a scapegoat tree?

A

size(u)/size(u.children) > 2/3

65
Q

describe how a AVL tree works

A

an AVL tree is a self-balancing tree. Balancing occurs when the height of the sub trees differ by more than one

66
Q

describe the adjacency lists representation of a graph

A

an array of lists where each element in the array represents a vertex i and the list is all the vertexes that i has an edge too

COMP272 (1 decks)

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