Chapter 0, 1 (intro)

Question 1

Deciding on the proper algorithm

Answer 1

Analyze underlying characteristics of problem

Design algorithm according to characteristics of problem, NOT types of problems

Question 2

What is an algorithm?

Answer 2

Sequence of unambiguous instructions for solving a problem in the finite amount of time

Question 3

Fundamentals of algorithmic problem solving

Answer 3

Problem -> Algorithm -> (input-> ‘computation’ -> output)
|
Definiteness
Finiteness
Effectiveness

Question 4

Euler path

Answer 4

A path that uses every edge of the graph exactly once. The path starts and ends at different vertices

Question 5

Euler circuit

Answer 5

an Euler path that starts and ends at the same vertex

Question 6

Analysis of algorithms is the determination of the amount of ____ and ____ resources required to execute it

Answer 6

time
space

Question 7

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 ____ ____

Answer 7

time complexity
space complexity

Question 8

Programming paradigm
Procedural

Answer 8

state the order in which to execute instructions (how to compute the answer)

Question 9

Programming paradigm
Declarative

Answer 9

does not state the order in which to execute instruction, instead, declare properties of the desired result (not how to compute the answer)

Question 10

Data Structures

Answer 10

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

Question 11

An array contains ____ _____

Answer 11

homogeneous elements

Question 12

Static array

Answer 12

allocated at compile time, its size must be a compile time constant.
Size of array is allocated on the stack

Question 13

Dynamic array

Answer 13

allocated at run time.
Size is allocated on the heap.
May be allocated and then de-allocated multiple times

Question 14

A linked list contains nodes and each node stores its elements

Answer 14

Singly linked list
Doubly linked list
Circularly linked list

Question 15

Writing code for Linked Lists

Answer 15

A class define the node

A class define the linked list

Using head and tail to construct linked lists

Operations on the linked list

Question 16

Operations on Singly Linked List

Answer 16

• SinglyLinkedList()
• ~SinglyLinkedList()
• bool empty()
• addFront(item)
• removeFront()
• displaySinglyLinkedList()

Question 17

Singly linked list acting like stack

Answer 17

First in Last out (FILO)

Question 18

Doubly Linked List operations

Answer 18

– DoublyLinkedList();
– ~DoublyLinkedList();
– bool empty();
– void addFront(dNode& newNode);
– void addBack(dNode& newNode);
– void removeFront();
– void removeBack();
– void displayDoublyLinkedListFromFront();
– void displayDoublyLinkedListFromBack();

Question 19

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 ______

Answer 19

cycle

Question 20

Arrays are faster than linked lists because they use an ____ _____

Answer 20

array index

Question 21

____ ____ are faster if an element must be removed from the middle of inserted into the middle

Answer 21

Linked lists

Question 22

Stacks

Answer 22

LIFO (last-in first-out)

Question 23

stack operation:
push(e)

Answer 23

Insert element e at the top of the stack

Question 24

stack operation:
pop()

Answer 24

Remove the top element from the stack; an
error occurs if the stack is empty

Question 25

stack operation: top()

Answer 25

Return a reference to the top element on the stack, without removing it; an error occurs if the stack is empty

Question 26

stack operation: size()

Answer 26

Return a reference to the top element on the stack, without removing it; an error occurs if the stack is empty

Question 27

stack operation: empty()

Answer 27

Return true if the stack is empty and false otherwise

Question 28

Tree

Answer 28

an abstract data type that stores elements hierarchically.

Question 29

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.

Answer 29

parent children root

Question 30

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.

Answer 30

child

Question 31

siblings

Answer 31

nodes that are children of the same parent

Question 32

A node v is _____ if v has no children.

Answer 32

external

Question 33

A node is ____ if it has one or more children.

Answer 33

internal

Question 34

External nodes are also known as _____.

Answer 34

leaves

Question 35

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}

Answer 35

vertices edges

Question 36

Directed graph (digraph)

Answer 36

set of vertices and a collection of directed edges that each connects an ordered pair of vertices. X -> X | ^ ▼ | X <- X

Question 37

undirected graph

Answer 37

set of vertices and a collection of undirected edges that each pair of vertices is not ordered.

Question 38

mixed graph

Answer 38

has both directed and undirected edges.

Question 39

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

Answer 39

endpoints origin

Question 40

When an edge connects two vertices, we say that the vertices are _____ to one another and that the edge is _____ on both vertices

Answer 40

adjacent incident

Question 41

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.

Answer 41

A matrix each of whose entries is 0 or 1. * Examples are the identity matrix and the zero matrix.

Question 42

Adjacency List structure

Answer 42

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

Question 43

Adjacency list of a vertex v is a sequence of vertices adjacent to ____

Answer 43

v

Question 44

The ____ _____ of a vertex are the directed edges whose origin is that vertex.

Answer 44

outgoing edges

Question 45

The ____ _____ of a vertex are the directed edges whose destination is that vertex.

Answer 45

incoming edges

Question 46

The _____ of a vertex v, denoted deg(v), is the number of incident edges of v.

Answer 46

degree

Question 47

The in-degree and out-degree of a vertex v are the incoming and outgoing edges of v and are denoted _____(_) and ____(_), respectively

Answer 47

indeg(v) outdeg(v)

Question 48

self-loop

Answer 48

an edge that connects a vertex to itself

Question 49

Two edges are ____ if they connect the same pair of vertices.

Answer 49

parallel

Question 50

A ____ in a graph is a sequence of vertices connected by edges. A ____ ____ is one with no repeated vertices.

Answer 50

path simple path

Question 51

A _____ is a path (with at least one edge) whose first and last vertices are the same.

Answer 51

cycle

Question 52

A ____ _____ is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).

Answer 52

simple cycle

Question 53

the ____ of a path or a cycle is its number of edges

Answer 53

length

Question 54

A ______ G’ of a graph G is a graph G’ whose vertices and edges are subsets of those of G.

Answer 54

subgraph

Question 55

one vertex is ______ to another if there exists a path that contains both of them.

Answer 55

connected

Question 56

A graph is connected if there is a path from every vertex to ____ other vertex.

Answer 56

every

Question 57

A graph that is not connected consists of a set of ____ _____, which are maximal connected subgraphs

Answer 57

connected components

Question 58

Acyclic graph

Answer 58

graph with no cycles