RAH pt2 Flashcards
Variables are using _________ to
redirect them to the memory
address
pointers
pointers are acting
as a __________ so that the
variable can be connected
function
__________ are associations when an element in a Set A is
directly associated to EXACTLY ONE element in Set B
Functions
T or F
Functions are applicable in a numeric manner
T
described as equations that will yield
a value depending on another numeric input.
Functions
is a well-defined, finite sequence of steps or
instructions designed to perform a specific task or solve a
problem.
algorithm
How does Efficient algorithms save time and resources
Faster code –> faster execution time –> lower energy and
financial costs –> lower consumption of fossil fuels –> lower
pollution
Measures the time an algorithm takes to run as a function
of the size of the input
Time complexity
measures the memory an algorithm requires during its execution
Space complexity
is used to describe the upper bound of an
algorithm’s running time or space requirements in terms of
input size.
Big O notation
helps benchmark and compare the performance of
algorithms
Big O notation
Domain
All possible inputs in a function
Range
all possible output from a function
input
the value you put in the function
output
the result you get out of a function
function with two arguments is
called a
binary
like a function except that it might not be
defined for some elements
Partial function
to mean a function that is defined on all its domain
total function
this function rounds down to the closest integer
Floor function
⌊x⌋
This function rounds up to the closest integer
Ceiling function
⌈x⌉
two integers, not both zero, is the
largest integer that divides them both.
Greatest common Divisior
Formula for mod?
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
We sometimes need to compute a list of values of a function. A useful tool
to accomplish this is the
map function
if a function’s range only one element but leaves one its called
Injective
if a function’s range is multiple elements its called
Surjective
What is a injective and surjective function called?
Injective and Surjective
if a function’s range is all the elements its called
Bijective
the function for bijective is called
bijection
is the information needed to encipher or decipher a
message.
cipher key
which is a cipher that
replaces repeated occurrences of a character in a message by the same
character from the cipher alphabet
Monoalphabetic cipher
is a monoalphabetic cipher that enciphers each
letter by using a multiplier as a key.
Multiplicative cipher
is a monoalphabetic cipher that combines additive and
multiplicative ciphers.
affine cipher
is a function that maps a set S of keys to a finite set of
table indexes,
hash function
able whose
information is found by a hash function is called a
hash table
When two keys map to the same table index, the
result is called a
collision
A
set is __________ if it is finite
countable
if there is a bijection between it and N, a set is said to be _________
countably infinite
If a set is not countable, it is said to be __________
uncountable
What is a technique to know if a set is countable?
N X N
real
numbers are uncountable.
Diagonalization
nonempty set of objects in which some of the objects may be
connected to each other in some way.
Graph
What are the circles called in graphs?
bertices, nodes, points
What are teh connections called in graphs??
edges, lines
Two vertices are __________________ if there
is an edge connecting them.
adjacent (or neighbors)
vertex is __________ if there are no edges
connected to it.
isolated
we say the edge is __________ to one or
both of the vertices, and the vertices are _____________ to the edge
incident
two
distinct edges are ___________ if they share a common vertex
adjacent
________is an edge that starts and ends at the same vertex.
loop
If a graph has two
or more edges between some pair of vertices, the edges are said to be
______________
parallel edges
graph with parallel edges is called a
multigraph
___________ is a graph where each edge points in
one direction
Directed graph (digraph for short)
A graph is called ___________ if each edge is assigned a number
weighted
A graph
(V′,E′) is a ___________ of a graph (V, E) if V′⊆V and E′⊆E.
subgraph
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
induced subgraph
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?
Path
graph is __________ if there is a path between every pair of vertices
connected
A digraph is
___________ if, when direction is ignored, the resulting ___________is connected.
weakly connected
undirected graph
digraph is ___________ if there is a directed
path between every pair of vertice
strongly connected
is a graph
that is connected and has no cycles
Tree
vertices and edges of a tree are called _________ and ________,
respectively
Nodes and branches
the node at the top of a tree is called the
root
The nodes that
hang immediately below a given node are its
children
the node
immediately above a given node is its
parent
If a node is childless, then it
is a
leaf
of a tree is the length of the longest path from
the root to the leaves.
height or depth
_________ of a node is the length of the path from the
root to the node
level
Any path from a node to a leaf contains ___________ of the
node
descendants
tree with a designated root is often called a ____________,Otherwise, it is
called a ___________
rooted tree
free tree or an unrooted tree
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
subtree
f we don’t care about the ordering of the children of a tree, then the tree is
called an
unordered tree.
A tree is __________ if there is a unique ordering of
the children of each node.
ordered
____________ is an ordered tree that may be empty or else has the property
that each node has two subtrees, called the ___________ and the _______
binary tree
left subtree
right
subtree,
Binary trees can be used to represent sets whose elements have some
ordering. Such a tree is called
Binary search tree
for a connected graph is a subgraph that is a tree and
contains all the vertices of the graph
spanning tree
for a
connected weighted graph is a spanning tree such that the sum of the edge
weights is minimum among all spanning trees
minimal spanning tree
constructs a minimal
spanning tree for any undirected connected weighted graph
Prim’s Algorithm
