Theory of Computation.

CS 345: Spring, 20151.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 2014Page 1 of 7Midterm D4.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 2014Page 2 of 7Midterm D6.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 2014Page 3 of 7Midterm D8.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 2014Page 4 of 7Midterm D9.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 2014Page 5 of 7Midterm D10.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 2014Page 6 of 7Midterm DThis 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 2014Page 7 of 7Midterm DBasic TopicsChapter 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 PathChapter 5:Algorithm Verification?Assertions and Invariants?Convergence?Verification Conditions?Partial and Total Correctness!

Welcome to Vision Essays! For over 10 years we have been helping students like you write, research, and generate ideas for their research papers, essays, term papers, dissertations, editing, resumes, and any other type of work your learning institution may assign you.

We can write any paper and have flexible payment plans with a minimum deadline of 6 Hrs.

Type of paper Academic level Subject area
Number of pages Paper urgency Cost per page:
 Total: