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]

b. Justify your answer. [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

:

Algorithm Paradigms

•

Trees

•

Traversals and Searches

•

Depth

–

First: pre

–

order, in

–

order, post

–

order

•

Breadth

–

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 🙂