Flashcards
CS 345 - Midterm 1 Review
Cards in this deck (21)
- 1A distinguishing difference between a depth-first traversal and a breadth-first traversal is the data structure used to hold nodes to be visited. Which data structure goes with which traversal?Depth-first: stack, recursion
Breadth-first: queue - 2What is an application for an in-order traversal?Tree sort
- 3A depth-first traversal requires space proportional to the depth of the tree, and a breadth-first traversal requires space proportional to the number of leaves of the tree. For a balanced tree with a finite number of nodes, which traversal would require the least amount of space?A breadth first traversal uses more memory than a depth first
- 4Be prepared to give an example of a divide and conquer algorithm. Under what conditions might a divide and conquer algorithm be useful? What are some characteristics of a problem that must be true if it is to be solved by a divide-and-conquer algorithm?Merge sort is an example of a divide and conquer algorithm. A divide and conquer algorithm is useful when it can be used to solve a problem, it is generally very efficient. These characteristics must be true; 1. There must be a natural way of dividing the problem. 2. There must be a natural way of merging the problem back together. 3. The run time order to the solution to the problem is n^2 or higher.
- 5What characterizes a greedy algorithm? What is the advantage of using a greedy approach? Can you give an example of a greedy algorithm? Can you always use a greedy approach? Why or why not?A greedy algorithm can solve certain specific types of problems like the least coins used problem demonstrated in class. The advantage is for certain types of problems it is a fast, simple way of solving problems. The minimum coin problem, or the knapsack problem are examples of using a greedy algorithm. You cannot always use the greedy approach. Not all problems work with it, for example the slobovian coin problem solves, but it gives the incorrect answer.
- 6What are the steps in creating a dynamic programming solution to a problem?1. View the problem in terms of subproblems.
2. Devise a recursive solution.
3. Replace the recursion with a table and compute the optimal solution in a bottom up fashion. - 7What must be true of a problem before you can use a dynamic programming solution?The problem must be capable of being broken down into independent halves that can be solved independently and merged back together.
- 8Why can a dynamic programming solution solve problems that a greedy solution cannot?Dynamic programming breaks a problem into smaller subprograms. It then keeps track of all optimal solutions for these subproblems (usually through use of a data structure), then solving each subprogram in order of increasing magnitude so that it can find the most optimal solution to the larger problem. In comparison, a greedy algorithm may only solve a problem based on a linear sequence of choices.
- 9What is a memoized solution? How does it differ from a purely dynamic programming solution and from a recursive solution? When might you use a memoized solution rather than a dynamic programming solution?memoized is recursive but uses array and puts answer in array. when it goes to recursive call it looks in the array to see if it has an answer first.
in some cases recursion starts at the top and fills its way down. just filling in the array
in dynamic - 10Describe a state-space search and what is needed for it to functionStates (start, current, goal)
Operators that allow the program to change states
Rules (ex. fox cannot be left alone with chicken) - 11When a problem can be solved by backtracking, it can be described by a decision tree. The term backtracking refers to the fact that the decision tree is traversed in a depth-first manner. Describe the Knight’s Tour problem. This problem can be solved by backtracking, what does the decision tree look like for this problem?knight’s tour,way back to middle ages chess board, 1 knight can it land in each place once and only once. a lot of backtracking.
- 12When a problem is solved by backtracking, it makes use of a bounding function. What is the purpose of a bounding function, and how is it used in backtracking?bounding function when you get to a point and can't go further you backtrack. bounding cuts off everything after that to reduce the path
- 13What are the similarities and differences between a backtracking solution and a branch-and-bound solution to a problem?Backtracking is a depth first search “stack,” branch-and-bound is a breadth first search “queue.”
- 14A standard problem in Computer Science is the Knapsack Problem. Describe this problem. What are some variations of this problem? What are some algorithmic paradigm that can solve this problem?The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
- 15A binomial coefficient, BinCoef( m, n ), can be computed recursively by the following algorithm. BinCoef( m, n ) //m > 0 and n ≤ m if( m = 0 OR m = 1 ) return 1 else if( n = 0 OR n = m ) return 1 else if( n = 1 OR n = m-1 ) return m else return BinCoef( m-1, n-1 ) + BinCoef( m-1, n )it can
n dimensions is same as input it has so two variables so two dimensional array.
easier one way or the other both very similar, either they both would solve it. - 16The text book presented a solution to the problem of finding a minimum cost spanning tree of a graph by Prim’s algorithm (the Lazy Contractor). What algorithmic paradigm does this algorithm use? What is a minimum cost spanning tree of a graph?A minimum cost spanning tree is like a series of roads that connect each vertex in a graph in such a way that all vertices can be visited by driving along the road. In addition, the sum of the edge weights between the vertices on the road will be lowest possible. This is done using a greedy algorithm.
- 17What does it mean when an algorithm is partially correct? How is this different from an algorithm that is totally correct?If an algorithm is partially correct it means that at least one of the paths can return a correct result for the algorithm. A totally correct algorithm returns correct data on all paths.
- 18When trying to show that an algorithm is partially correct, what role does an assertion play? What does it mean when an assertion is an invariant?An assertion down a given path of an algorithm can at least tell us that path of the algorithm is correct. An invariant assertion simply means that a statement is true no matter how many times it is reached.
- 19Where are assertions normally placed in an algorithm; that is, what strategy is used when trying to locate a place for an assertion?Assertions are generally placed at checkpoints throughout an algorithm, otherwise known as a place where you should know the return value for the given algorithm. The Invariant Assertion Method is a strategy commonly used to locate a place for assertion.
- 20What is a convergent? Is it related to partial or total correctness?A convergent is related to total correctness. Convergent is the idea that a problem will eventually terminate.
- 21True or False: “Verification of the correctness of an algorithm is tedious, but not hard. It is a process that can be fully automated."False. This type of algorithm cannot be fully automated.
Information
- Description
- Flashcards on CS 345 - Midterm 1 Review, created by jshin13 on 03/05/2015.
- Created by
- jshin13
- Views
- 2
- Rating