Chapter 0, 1 (intro) Flashcards
Deciding on the proper algorithm
Analyze underlying characteristics of problem
Design algorithm according to characteristics of problem, NOT types of problems
What is an algorithm?
Sequence of unambiguous instructions for solving a problem in the finite amount of time
Fundamentals of algorithmic problem solving
Problem -> Algorithm -> (input-> ‘computation’ -> output)
|
Definiteness
Finiteness
Effectiveness
Euler path
A path that uses every edge of the graph exactly once. The path starts and ends at different vertices
Euler circuit
an Euler path that starts and ends at the same vertex
Analysis of algorithms is the determination of the amount of ____ and ____ resources required to execute it
time
space
Efficiency or running time of algorithm is stated as a function relating input size to the number of steps, known as ___ ___, or volume of memory, knowm as ____ ____
time complexity
space complexity
Programming paradigm
Procedural
state the order in which to execute instructions (how to compute the answer)
Programming paradigm
Declarative
does not state the order in which to execute instruction, instead, declare properties of the desired result (not how to compute the answer)
Data Structures
Storing and organizing data so data can be accessed efficiently
- Linear Data structures
* Arrays (static vs. dynamic)
* Linked Lists (Singly vs doubly)
- stacks
- Trees
- Graphs
- Sets and Dictionaries
An array contains ____ _____
homogeneous elements
Static array
allocated at compile time, its size must be a compile time constant.
Size of array is allocated on the stack
Dynamic array
allocated at run time.
Size is allocated on the heap.
May be allocated and then de-allocated multiple times
A linked list contains nodes and each node stores its elements
Singly linked list
Doubly linked list
Circularly linked list
Writing code for Linked Lists
A class define the node
A class define the linked list
Using head and tail to construct linked lists
Operations on the linked list
Operations on Singly Linked List
- SinglyLinkedList()
- ~SinglyLinkedList()
- bool empty()
- addFront(item)
- removeFront()
- displaySinglyLinkedList()
Singly linked list acting like stack
First in Last out (FILO)
Doubly Linked List operations
– DoublyLinkedList();
– ~DoublyLinkedList();
– bool empty();
– void addFront(dNode& newNode);
– void addBack(dNode& newNode);
– void removeFront();
– void removeBack();
– void displayDoublyLinkedListFromFront();
– void displayDoublyLinkedListFromBack();
A circularly linked list has the same kind of nodes as a
singly linked list.
The nodes of a circularly linked list are linked into a ______
cycle
Arrays are faster than linked lists because they use an ____ _____
array index
____ ____ are faster if an element must be removed from the middle of inserted into the middle
Linked lists
Stacks
LIFO (last-in first-out)
stack operation:
push(e)
Insert element e at the top of the stack
stack operation:
pop()
Remove the top element from the stack; an
error occurs if the stack is empty
stack operation:
top()
Return a reference to the top element on the
stack, without removing it; an error occurs if the
stack is empty
stack operation:
size()
Return a reference to the top element on the stack, without removing it; an error occurs if the stack is empty
stack operation:
empty()
Return true if the stack is empty and false
otherwise
Tree
an abstract data type that stores elements
hierarchically.
With the exception of
the top element, each
element in a tree has a
____ element and
zero or more _____
elements. Typically, the
top element is called
the _____ of the tree.
parent
children
root
We define a (general) tree to be a set of nodes storing elements in a parent-child relationship with the following properties:
– If a tree T is nonempty, it has a special node, called the root of T, that has no parent.
– Each node v of T different from the root has a unique parent node w; every node with parent w is a ___ of w.
child
siblings
nodes that are children of the same parent
A node v is _____ if v has no children.
external
A node is ____ if it has one or more children.
internal
External nodes are also known as _____.
leaves
A graph G is simply a set V of ____ and a collection of E of pairs of vertices from V, called _____.
G = {V, E}, where
V = {V1, V2, …, Vn}
E = E{ij} = (Vi, Vj), 1 <= i <= n, 1 <= j <= n}
vertices
edges
Directed graph (digraph)
set of vertices and a
collection of directed edges that each connects an
ordered pair of vertices.
X -> X
| ^
▼ |
X <- X
undirected graph
set of vertices and a collection of
undirected edges that each pair of vertices is not ordered.
mixed graph
has both directed and undirected edges.
End vertices (_____) are the two vertices joined by an edge.
– If an edge is directed, its first endpoint is its ____ and the other is the destination of the edge.
A———–B
A and B are endpoints
endpoints
origin
When an edge connects two vertices, we say that the vertices are _____ to one another and that the edge is _____ on both vertices
adjacent
incident
Adjacency matrix
Let the vertices of graph G be labeled V1, V2, …, Vn. The Adjacency Matrix A(G) is the n x n matric:
a{ij} = 1 if v[i]v[j] is an edge of G; 0 otherwise
Sine a vertex is never adjacent to itself, A(G) has 0’s on the diagonal.
A matrix each of whose entries is 0
or 1.
* Examples are the identity matrix and the zero matrix.
Adjacency List structure
A graph G has vertex set V(G)={v1, v2, …, vn} and edge set E(G) = {e1, e2, … em}. The adjacency list structure represents a graph by the adjacency lists of all the vertices
Adjacency list of a vertex v is a sequence of vertices adjacent to ____
v
The ____ _____ of a vertex are the directed edges whose origin is that vertex.
outgoing edges
The ____ _____ of a vertex are the directed edges whose destination is that vertex.
incoming edges
The _____ of a vertex v, denoted deg(v), is the number of incident edges of v.
degree
The in-degree and out-degree of a vertex v are the incoming and outgoing edges of v and are denoted _____() and ____(), respectively
indeg(v)
outdeg(v)
self-loop
an edge that connects a vertex to itself
Two edges are ____ if they connect the same pair of vertices.
parallel
A ____ in a graph is a sequence of vertices connected by edges. A ____ ____ is one with no repeated vertices.
path
simple path
A _____ is a path (with at least one edge) whose first and last vertices are the same.
cycle
A ____ _____ is a cycle
with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
simple cycle
the ____ of a path or a cycle is its number of edges
length
A ______ G’ of a graph G is a graph G’
whose vertices and edges are subsets of those of G.
subgraph
one vertex is ______ to another if
there exists a path that contains both of them.
connected
A graph is connected if there is a path from every vertex to ____ other vertex.
every
A graph that is not connected consists of a set of ____ _____, which are maximal connected subgraphs
connected components
Acyclic graph
graph with no cycles
