A200 Exam 1

What is a data structure?

A way to store and organize data in a computer so that it can be used efficiently.

What is data abstraction?

It separates the logical view of the data from the physical view of how it is actually stored.

How is a procedure or an algorithm like a recipe?

It describes the exact steps needed to solve a problem or reach a goal.

What is an abstract data type?

A high-level definition of data types.

What is a graph?

A data structure that consists of a set of vertices (nodes) and with edges (relations) between them.

What is considered an adjacent vertex?

When there is an edge from one vertex to the other vertex.

What is a simple graph?

A graph where there are no parallel edges and self loops.

What is the degree of a vertex?

The number of edges in a vertex.

In a directed graph, what is the in-degree and out-degree of a vertex?

The number of incoming and outcoming edges.

What is considered a simple path?

A path where all the vertices and edges are distinct.

What is a cycle?

A path with distinct vertices, but the starting and end vertex are identical.

What is an adjacency matrix?

A square grid of true/false values that represent the edges of a graph.

What is a directed acyclic graph?

A digraph that has no directed cycles.

How do you perform a topological ordering (topological sort) of a digraph?

List them in the way that all predecessors are accessed before moving forward.

If we have a directed graph represented as an adjacency matrix where the adjacency of two vertices is defined by Boolean variables, how do we determine the number of Boolean variables necessary?

Why is the state graph for tic-tac-toe a directed graph rather than an undirected graph?

Once a move is made, it cannot be unmade.

What defines a subgraph of a graph?

The vertices and the edges of the subgraph are a subset of the vertices and edges of the graph.

What is a spanning subgraph?

The subgraph contains all the vertices of the graph.

What is a traversal?

A systematic procedure for exploring a graph by examining all of its vertices and edges.

What makes a traversal efficient?

If it visits all vertices and edges in time proportional to their number in linear time.

What does a depth-first search use?

It uses a stack to keep track of vertices that still need to be visited.

How do you perform a depth-first search?

Start at the initial vertex, visit it. Choose an adjacent vertex to visit until there are no more adjacent vertices. If not, add it to the post order sequence and go back to the predecessor.

In a depth-first search, what do you do once all vertices have been visited?

It would be inefficient to keep checking, so we pop them from the stack and add them to the post order sequence.

What does a breadth-first search use?

It uses a queue to keep track of vertices that still need to be visited.

How do you perform a breadth-first search?

Start at the initial vertex and mark it as visited. Find all adjacent vertexes and add them to the queue. Pop the first vertex and mark it as visited. Repeat until there are no more vertices to visit.

What does Dijkstra’s algorithm do?

It computes the distsances of all vertices from a given initial vertex to find the shortest path.

How does Dijkstra’s algorithm work?

It finds the shortest path from an initial vertex by repeatedly choosing unvisited nodes with the smallest known distance. It will update its neighbors’ distances until all nodes are processed.

What is a minimum spanning tree?

A spanning tree of a weighted graph with minimum total edge weight.

How does Kruskal’s algorithm work?

It builds a minimum spanning tree by repeatedly adding the smallest-weight edge that connects two previously unconnected components. It stops when all vertices are connected.

How is Kruskal’s algorithm a greedy algorithm?

At each step, it greedily chooses the smallest edge available that does not create a cycle.