# Theory of Computation.

Theory of Computation.

CS 345: Spring, 2014

1.

a. A distinguishing difference between a depth-first traversal and a breadth-first traversal is the data structure used to hold the nodes to be visited. What data structure is used with a breadth-first traversal? [5 points]

b. If the structure to be traversed is a complete, balanced binary tree (every non-leaf node has two children), does a breadth-first traversal require more or less space to store the nodes to be visited than a depth-first traversal? [5 points]

2.

The textbook presents a solution to the problem of finding a minimum cost spanning tree of a graph by Prim’s algorithm (the Lazy Contractor). What algorithm paradigm does this algorithm use? [10 points]

3.

Write the pseudocode for a function called pre-order(). This is a recursive function which performs a pre-order traversal of a binary tree. The function takes one parameter, n, which is a node of a tree; and it calls a function visit(), which processes the node. [10 points]

CS 345: Spring 2014

Page 1 of 7

Midterm D

4.

a. Under what conditions might a divide-and-conquer algorithm be useful? [10 points]

b. Describe either a problem that can be solved using a divide-and-conquer algorithm or a well-known algorithm that implements a divide-and-conquer approach. [10 points]

5.

What are the steps necessary to create a dynamic programming solution to a problem? [10 points]

CS 345: Spring 2014

Page 2 of 7

Midterm D

6.

When a problem can be solved by backtracking, it makes use of a bounding function. Describe the purpose of the bounding function. [10 points]

7.

Graph 1 represents a map of cities. A traveler wants to go from city A to city B.

a. What path would a greedy algorithm take? [10 points]

b. What path would a dynamic programming algorithm take? [10 points]

CS 345: Spring 2014

Page 3 of 7

Midterm D

8.

Draw a depth-first spanning tree for Graph 3 starting from node A. Process the children of a node in alphabetical order. [10 points]

CS 345: Spring 2014

Page 4 of 7

Midterm D

9.

Below is a method that calculates a binomial coefficient.
/* int [][] BC = new int[m][n] and int EMPTY = -1 are defined globally. In addition, BC has been initialized to EMPTY before the method is called. */ public int binomialCoefficient( int m, int n ) { if( (m == 0) || (m == 1) ) return 1; else if( (n == 0) || (n == m) ) return 1; else if( (n == 1) || (n == (m-1)) ) return m; else { if( BC[ m – 1 ][ n – 1 ] == EMPTY ) BC[ m – 1 ][ n – 1 ] = binomialCoefficient ( m-1, n-1 ); if( BC[ m – 1 ][ n ] == EMPTY ) BC[ m – 1 ][ n ] = binomialCoefficient ( m-1, n ); return ( BC[ m – 1 ][ n – 1 ] + BC[ m – 1 ][ n ] ); } }

a. What algorithmic paradigm is it using? [5 points]

CS 345: Spring 2014

Page 5 of 7

Midterm D

10.

a. Describe what it means when an algorithm is partially correct. [5 points]

b. Describe what it means when an algorithm is totally correct. [5 points]

c. Describe the purpose of a convergent. [5 points]

CS 345: Spring 2014

Page 6 of 7

Midterm D

This page is scratch paper. It may be removed from the exam, and it does not need to be turned in with the exam.

CS 345: Spring 2014

Page 7 of 7

Midterm D
Basic Topics
Chapter 4
:

Trees

Traversals and Searches

Depth

First: pre

order, in

order, post

order

First

Divide

and

Conquer

Greedy

Dynamic Programming

Memoization

State Space Search

Backtracking

Branch and Bound

Problems

N

Queens

Knight

s Tour

Stack Permutation

Subset Sum

Maximum Subsequence Sum

Slobovian Coin

Knapsack

Minimum Cost Spanning Tree

Shortest Path
Chapter 5:
Algorithm Verification

Assertions and Invariants

Convergence

Verification Conditions

Partial and Total Correctness
PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT 🙂