final

Question 1

mapping ADT

Answer 1

refers to items by a key rather than their index

Question 2

hashing

Answer 2

a hash function converts a key to an index; try f(x) = x % (# of keys)

Question 3

hash collision

Answer 3

keys hash to the same integer, potentially overwriting existing values

Question 4

runtime: mapping with mod hashing

Answer 4

put - O(n); get - O(n)

Question 5

load factor

Answer 5

values hash function produces / entries currently in table;
capacity / entries;
minimal empty slots

Question 6

runtime: mapping with rehashing

Answer 6

put - O(1); get - O(1)

Question 7

mapping with dictionaries

Answer 7

dictionaries support O(1) for put and get, regardless of n

Question 8

only immutable built-ins can be keys, meaning:

Answer 8

only tuples and strings can be keys

Question 9

sets

Answer 9

cannot be hashed

Question 10

tree

Answer 10

hierarchal collection of nodes

Question 11

root

Answer 11

top node of a tree

Question 12

children

Answer 12

any node with a node above it

Question 13

parent

Answer 13

any node with a node below it

Question 14

edge

Answer 14

connections between two vertices; connect nodes in a graph

Question 15

path

Answer 15

series of edges connecting two nodes

Question 16

path length

Answer 16

number of edges in a path

Question 17

depth

Answer 17

length of path from a node to the root

Question 18

height

Answer 18

maximum depth of any node in a tree

Question 19

descendants

Answer 19

all nodes for which there is a path from x’

Question 20

ancestors

Answer 20

all nodes which x is a descendant of

Question 21

subtree

Answer 21

node x and its descendents; where x is not the parent node of the original tree

Question 22

binary tree

Answer 22

nodes of a graph;
often stored as a set

Question 23

binary search tree

Answer 23

binary tree where all the descendants to the left are less and all the descendants to the right are greater

Question 24

graph - mathematic

Answer 24

a set of vertices V and a set of edges E: G(V, E)

Question 25

vertices

Answer 25

nodes of a graph; oftern stored as a set

Question 26

weighted edges

Answer 26

has a specific value, more or less than other edges

Question 27

directed edges

Answer 27

an edge that points one way, signaling that inforation is carried in that direction

Question 28

edge set - {(x, y)}

Answer 28

signals that x is connected to y, but not vice versa; x-y edge is directional

Question 29

undirected edges

Answer 29

a path between two vertices; works in all directions

Question 30

path

Answer 30

a set of vertices connected by edges; can get from edge a to edge d by edges b and c and the vertices in between

Question 31

cycles

Answer 31

a path where v(0) = v(n); a path that can go in a circle

Question 32

avoiding cycles

Answer 32

memoization

Question 33

two nodes are connected if

Answer 33

there is a path between them

Question 34

graph data structure: edge set

Answer 34

stores a set of vertices and a set of edges

Question 35

graph data structure: adjacency set

Answer 35

stores a set of vertices and a dictionary of neighbors

Question 36

EdgeSet: add_vertex(self, v):

Answer 36

self.V.add(v)

Question 37

EdgeSet: add_edge(self, e):

Answer 37

self.E.add(e)

Question 38

inheritance

Answer 38

class Class1(Class2): pass; Class1 inherits attributes and functions of Class2

Question 39

remove_vertex(self,v):

Answer 39

self.V.remove(v)

Question 40

remove_edge(self, e):

Answer 40

self.E.remove(e)

Question 41

EdgeSet: __iter__(self):

Answer 41

return iter(self.V)

Question 42

_neighbors(self, v):

Answer 42

nbrs = set(); for e in self.E: >if e[0] == v: nbrs.add(e[1]); return nbrs; new set to store new vertex' neighbors; if the source of the edge is v, add v to the dict as a destination

Question 43

class AdjacencySet:

Answer 43

initialize with empty set of vertices, empty dict of neighbors; v = set() neighbors = dict()

Question 44

Adjacency set

Answer 44

set for vertices, dictionary for edges; each vertex is a key, value is all neighbors

Question 45

AdjacencySet: add_vertex

Answer 45

self.V.add(V)

Question 46

AdjacencySet: remove_vertex

Answer 46

self.V.remove(V)

Question 47

AdjacencySet: add_edge(self, e):

Answer 47

a, b = e; if a not in self.nbrs: self.nbrs[a] = {b}; else: self.nbrs[a].add(b); check if in dict.neighbors. else; add to neighbors

Question 48

AdjacencySet: remove_edge:

Answer 48

a, b = e; self.nbrs[a].remove(b); if len(self.nbrs[a]) == 0: self.nbrs.pop(a)

Question 49

AdjacencySet: _neighbors:

Answer 49

return iter(self.nbrs[v])

Question 50

degree of a vertex

Answer 50

edges connected to that vertex

Question 51

simple graph

Answer 51

don't self-loop, no multi-edges

Question 52

breadth first search

Answer 52

begins at a source node, inspects neighboring nodes; inspects neighbors' neighbors, etc; queue of nodes in order of first explored, sorted lowest-first

Question 53

depth first search

Answer 53

recursively explore one part before going back to the other, unexplored ones; stack of previously explored nodes, noting what can be explored in x many steps; sorted how the neighbors are stored/visited

Question 54

guaranteed to find a path, not necessarily shortest

Answer 54

DFS

Question 55

useful for exploring graphs + finding connected components

Answer 55

DFS

Question 56

guaranteed to find a path, shortest

Answer 56

BFS