Final Flashcards by Jessie Klein

explain the concept of data structures

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?

Not at all

Perfectly

explain the concept of algorithms

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?

Not at all

Perfectly

distinguish the difference between an interface and an implementation

interface- what a data structure does

implementation- how the structure does it

How well did you know this?

Not at all

Perfectly

what is a FIFO queue?

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

How well did you know this?

Not at all

Perfectly

what is a priority queue?

smallest element is always removed eg. emergency waiting room

How well did you know this?

Not at all

Perfectly

what is a LIFO (stack) queue?

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

How well did you know this?

Not at all

Perfectly

what is a USet?

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

How well did you know this?

Not at all

Perfectly

what is a SSet?

a sorted set

How well did you know this?

Not at all

Perfectly

implement an ArrayStack

see notebook

How well did you know this?

Not at all

Perfectly

implement an ArrayQueue

see notebook

How well did you know this?

Not at all

Perfectly

implement an ArrayDeque

see notebook

How well did you know this?

Not at all

Perfectly

implement a DualArrayDeque

see notebook

How well did you know this?

Not at all

Perfectly

implement a RootishArrayStack

see notebook

How well did you know this?

Not at all

Perfectly

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

advantage- delete and insert in constant time

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

How well did you know this?

Not at all

Perfectly

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

see notebook

How well did you know this?

Not at all

Perfectly

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

O(n)

How well did you know this?

Not at all

Perfectly

implement a SkipListSSet

see notebook

How well did you know this?

Not at all

Perfectly

implement a ChainedHashTable

see notebook

How well did you know this?

Not at all

Perfectly

describe linear probing

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?

Not at all

Perfectly

what are the two properties of hash code mappings?

if x and y are equal, then x.hashCode() and y.hashCode should be equal
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?

Not at all

Perfectly

what is division hashing?

k % tableSize

How well did you know this?

Not at all

Perfectly

what is multiplication hashing?

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?

Not at all

Perfectly

what is folding hashing?

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?

Not at all

Perfectly

what is radix transformation?

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?

Not at all

Perfectly

what is digit rearrangement?

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

what is length-dependent hashing?

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

what is mid-square hashing?

when the key is squared and the middle part is used

what is quadratic probing?

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

what is double hashing?

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

what is a recursive function?

a function that recursively calls itself until some condition is met

what is in-order traversal of a binary tree?

left subtree, root, right subtree

what is pre-order traversal of a binary tree?

root, left subtree, right subtree

what is post-order traversal of a binary tree?

left subtree, right subtree, root

what is breadth-first traversal of a binary tree?

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

what is the depth of u on a binary tree?

the length of the path from u to the root

what is the height of u on a binary tree?

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

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

see notebook

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

see notebook

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

see notebook

what is the maximum height of a red black tree?

2 log n

what is the disadvantage of red black trees?

the implementation is complex

what are the two properties of 2-4 trees?

1. the depth of all of the leafs is the same | 2. all internal nodes have either 2, 3, or 4 children

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

see notebook

what are the two properties of red black trees?

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

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

1. always make the root black | 2. make all external nodes (nil nodes of the leafs) black

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

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

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

O(logn) worst case

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

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

what is the property of a binary heap?

a child must always be greater than its parent

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

see notebook

which sorting algorithms are comparison-based?

merge-sort, quick-sort, heap-sort

show how merge-sort works

see notebook

show how quick-sort works

see notebook

show how heap-sort works

see notebook

show how a counting-sort works

see notebook

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

- inEdges(i) | - outEdges(i)

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

uses a lot of memory

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

1. addEdge(i, j)/removeEdge(i,j)/hasEdge(i,j) O(1) | 2. inEdges(i)/outEdges(i) O(n)

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

O(n^2)

implement breadth-first traversal of a graph

see notebook

implement depth-first traversal of a graph

see notebook

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

see notebook

describe how remove() of a binary tree is performed

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

what condition determines the scapegoat in a scapegoat tree?

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

describe how a AVL tree works

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

describe the adjacency lists representation of a graph

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

Final Flashcards

(66 cards)