RAH pt2

Question 1

Variables are using _________ to
redirect them to the memory
address

Answer 1

pointers

Question 2

pointers are acting
as a __________ so that the
variable can be connected

Answer 2

function

Question 3

__________ are associations when an element in a Set A is
directly associated to EXACTLY ONE element in Set B

Answer 3

Functions

Question 4

T or F

Functions are applicable in a numeric manner

Answer 4

T

Question 5

described as equations that will yield
a value depending on another numeric input.

Answer 5

Functions

Question 6

is a well-defined, finite sequence of steps or
instructions designed to perform a specific task or solve a
problem.

Answer 6

algorithm

Question 7

How does Efficient algorithms save time and resources

Answer 7

Faster code –> faster execution time –> lower energy and
financial costs –> lower consumption of fossil fuels –> lower
pollution

Question 8

Measures the time an algorithm takes to run as a function
of the size of the input

Answer 8

Time complexity

Question 9

measures the memory an algorithm requires during its execution

Answer 9

Space complexity

Question 10

is used to describe the upper bound of an
algorithm’s running time or space requirements in terms of
input size.

Answer 10

Big O notation

Question 11

helps benchmark and compare the performance of
algorithms

Answer 11

Big O notation

Question 12

Domain

Answer 12

All possible inputs in a function

Question 13

Range

Answer 13

all possible output from a function

Question 14

input

Answer 14

the value you put in the function

Question 15

output

Answer 15

the result you get out of a function

Question 16

function with two arguments is
called a

Answer 16

binary

Question 17

like a function except that it might not be
defined for some elements

Answer 17

Partial function

Question 18

to mean a function that is defined on all its domain

Answer 18

total function

Question 19

this function rounds down to the closest integer

Answer 19

Floor function

⌊x⌋

Question 20

This function rounds up to the closest integer

Answer 20

Ceiling function

⌈x⌉

Question 21

two integers, not both zero, is the
largest integer that divides them both.

Answer 21

Greatest common Divisior

Question 22

Formula for mod?

Answer 22

5 mod 2
5/2 = 2.5
> take the floor of 2.5 which is 2 from 2.5
2*2 = 4
5-4 = 1
5 mod 2 == 1

Question 23

We sometimes need to compute a list of values of a function. A useful tool
to accomplish this is the

Answer 23

map function

Question 24

if a function’s range only one element but leaves one its called

Answer 24

Injective

Question 25

if a function's range is multiple elements its called

Answer 25

Surjective

Question 26

What is a injective and surjective function called?

Answer 26

Injective and Surjective

Question 27

if a function's range is all the elements its called

Answer 27

Bijective

Question 28

the function for bijective is called

Answer 28

bijection

Question 29

is the information needed to encipher or decipher a message.

Answer 29

cipher key

Question 30

which is a cipher that replaces repeated occurrences of a character in a message by the same character from the cipher alphabet

Answer 30

Monoalphabetic cipher

Question 31

is a monoalphabetic cipher that enciphers each letter by using a multiplier as a key.

Answer 31

Multiplicative cipher

Question 32

is a monoalphabetic cipher that combines additive and multiplicative ciphers.

Answer 32

affine cipher

Question 33

is a function that maps a set S of keys to a finite set of table indexes,

Answer 33

hash function

Question 34

able whose information is found by a hash function is called a

Answer 34

hash table

Question 35

When two keys map to the same table index, the result is called a

Answer 35

collision

Question 36

A set is __________ if it is finite

Answer 36

countable

Question 37

if there is a bijection between it and N, a set is said to be _________

Answer 37

countably infinite

Question 38

If a set is not countable, it is said to be __________

Answer 38

uncountable

Question 39

What is a technique to know if a set is countable?

Answer 39

N X N

Question 40

real numbers are uncountable.

Answer 40

Diagonalization

Question 41

nonempty set of objects in which some of the objects may be connected to each other in some way.

Answer 41

Graph

Question 42

What are the circles called in graphs?

Answer 42

bertices, nodes, points

Question 43

What are teh connections called in graphs??

Answer 43

edges, lines

Question 44

Two vertices are __________________ if there is an edge connecting them.

Answer 44

adjacent (or neighbors)

Question 45

vertex is __________ if there are no edges connected to it.

Answer 45

isolated

Question 46

we say the edge is __________ to one or both of the vertices, and the vertices are _____________ to the edge

Answer 46

incident

Question 47

two distinct edges are ___________ if they share a common vertex

Answer 47

adjacent

Question 48

________is an edge that starts and ends at the same vertex.

Answer 48

loop

Question 49

If a graph has two or more edges between some pair of vertices, the edges are said to be ______________

Answer 49

parallel edges

Question 50

graph with parallel edges is called a

Answer 50

multigraph

Question 51

___________ is a graph where each edge points in one direction

Answer 51

Directed graph (digraph for short)

Question 52

A graph is called ___________ if each edge is assigned a number

Answer 52

weighted

Question 53

A graph (V′,E′) is a ___________ of a graph (V, E) if V′⊆V and E′⊆E.

Answer 53

subgraph

Question 54

A subgraph H of a graph G is an ________________ if the edges of H consist of all possible edges of G over the vertex set of H

Answer 54

induced subgraph

Question 55

graph problems involve moving from one vertex to another by traversing a sequence of edges, where each edge shares a vertex with the next edge in the sequence and there are no repeated edges or vertices. What is this called?

Answer 55

Path

Question 56

graph is __________ if there is a path between every pair of vertices

Answer 56

connected

Question 57

A digraph is ___________ if, when direction is ignored, the resulting ___________is connected.

Answer 57

weakly connected undirected graph

Question 58

digraph is ___________ if there is a directed path between every pair of vertice

Answer 58

strongly connected

Question 59

is a graph that is connected and has no cycles

Answer 59

Tree

Question 60

vertices and edges of a tree are called _________ and ________, respectively

Answer 60

Nodes and branches

Question 61

the node at the top of a tree is called the

Answer 61

root

Question 62

The nodes that hang immediately below a given node are its

Answer 62

children

Question 63

the node immediately above a given node is its

Answer 63

parent

Question 64

If a node is childless, then it is a

Answer 64

leaf

Question 65

of a tree is the length of the longest path from the root to the leaves.

Answer 65

height or depth

Question 66

_________ of a node is the length of the path from the root to the node

Answer 66

level

Question 67

Any path from a node to a leaf contains ___________ of the node

Answer 67

descendants

Question 68

tree with a designated root is often called a ____________,Otherwise, it is called a ___________

Answer 68

rooted tree free tree or an unrooted tree

Question 69

If x is a node in a tree T, then x together with all its descendants forms a tree S with x as its root. S is called a

Answer 69

subtree

Question 70

f we don’t care about the ordering of the children of a tree, then the tree is called an

Answer 70

unordered tree.

Question 71

A tree is __________ if there is a unique ordering of the children of each node.

Answer 71

ordered

Question 72

____________ is an ordered tree that may be empty or else has the property that each node has two subtrees, called the ___________ and the _______

Answer 72

binary tree left subtree right subtree,

Question 73

Binary trees can be used to represent sets whose elements have some ordering. Such a tree is called

Answer 73

Binary search tree

Question 74

for a connected graph is a subgraph that is a tree and contains all the vertices of the graph

Answer 74

spanning tree

Question 75

for a connected weighted graph is a spanning tree such that the sum of the edge weights is minimum among all spanning trees

Answer 75

minimal spanning tree

Question 76

constructs a minimal spanning tree for any undirected connected weighted graph

Answer 76

Prim’s Algorithm