1. For
topic __, see your group-work submission.
(a) What were the main concepts presented in the course that this group work exercised
or reinforced for you?
(b) Discuss briefly any errors in your group work for this topic.
(c) Critique the group-work submission that appears just after yours on the
Discussion Board. (If yours is last, critique the first submission.)
2.
Referring to chapter __ of Johnsonbaugh-Schaefer,
(a) What are the main concepts presented?
(b) What are the main concepts presented in the topic(s) of this course for
which the chapter was assigned?
(c) Compare and contrast the textbook presentation with what was presented in
the classroom and the slides.
3. Relate the eleven topics discussed in this course. Focus on the way that some material occurred again and again in later topics. Contrast different approaches taken, problems addressed, and objects analyzed. Include discussion of ways to mathematically formalize some of the different notions addressed in the course. While covering all the main topics, you may emphasize ones that interested you the most.
1. An algorithm lacks which of these features? (a) computes a function; (b) is deterministic; (c) may take an unreasonably long time; (d) works in discrete steps; (e) may take forever
2. Algorithm specifications presuppose (a) that input has occurred; (b) that processing has occurred; (c) that output has occurred; (d) the meaning of input; (e) that loops time out
3. Algorithms solve problems that are associated with (a) services; (b) protocols; (c) irrational numbers; (d) functions; (e) none of these
1. Arrays are structures that are (a) linked; (b) branching; (c) linear; (d) dynamically allocated; (e) none of these
2. Linked lists are (a) static; (b) branching; (c) linear; (d) stack allocated; (e) none of these
3. Graphs are implemented as (a) trees; (b) matrices or arrays of lists; (c) queues; (d) stacks; (e) none of these
4. A tree is a kind of (a) list; (b) array; (c) graph; (d) all of these; (e) none of these
1. A graph is a (a) vertex; (b) edge; (c) vertex and edge; (d) set of vertices and an edge; (e) set of vertices and set of edges
2. A language is a (a) string; (b) number; (c) set of numbers; (d) sequence of strings; (e) set of strings
3. When A and B are sets, (A ´ B) is (a) a set of ordered pairs; (b) an arithmetic expression; (c) a sequence of values; (d) all of these; (e) none of these
4. For array A, |A| is (a) the absolute value of the sum of A’s elements; (b) the absolute value of A; (c) the smallest element of A; (d) the number of elements in A; (e) none of these
5. Í denotes (a) set membership; (b) union; (c) conjunction; (d) a relation between sets; (e) negation
6. Ù
denotes (a) set membership; (b) union; (c)
7. Ø
denotes (a) set membership; (b) union; (c)
8. È
denotes (a) set membership; (b) union; (c)
9. Æ
denotes (a) set membership; (b) union; (c)
10. Î
denotes (a) set membership; (b) union; (c)
11. (a) ; (b) ; (c) ; (d) ; (e) none of these
1.
Use
2. Name common features of a set, a dictionary, and a list. Name features that distinguish the three.
3. Using the definition of a tree and the notion of induction, explain in your own words why every tree G = (V, E) has exactly one more vertex than its number of edges.
4. What are the domain and the range of the square-root function?
5. Show by induction that every complete binary tree has 2k-1 vertices, where k is depth of three.
6. Show by induction that every number whose binary representation ends in 1 is odd.
1. An example of an order statistic is (a) average; (b) mode; (c) standard deviation; (d) median; (e) none of these
2. A topological sort is applied to (a) graph vertices; (b) an array; (c) a tree; (d) a logical formula; (e) none of these
3. The order statistic problem finds the ____ of an array (a) average element value; (b) median value; (c) kth largest element; (d) kth element; (e) sorted version
4. Graph path search involves finding a (a) set of vertices; (b) sequence of vertices; (c) set of edges; (d) minimal set of edges; (e) none of these
5. The minimum priority queue problem is (a) an optimization problem; (b) a data-storage problem; (c) a sorting problem; (d) a search problem; (e) none of these
6. The prerequesite relationships among required courses in the Computer Science major form a (a) binary tree; (b) linked list; (c) directed acyclic graph; (d) weighted graph; (e) spanning tree
7.
String matching is a(n) _____ problem
(a) vector; (b) optimization; (c) state-space search;
(d) behavior-of-program; (e) interactive computation
8. Bin packing a(n) _____ problem (a) non-optimization vector, matrix or graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
9. Matrix multiplication is a(n) _____ problem (a) non-optimization; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
10. Path search is a(n) _____ problem (a) graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
1. Minimum spanning tree is an attribute of (a) arrays; (b) weighted graphs; (c) unweighted graphs; (d) sets of points; (e) none of these
2. Convex hull is an attribute of (a) arrays; (b) weighted graphs; (c) unweighted graphs; (d) sets of points; (e) none of these
3. Closest pair is an attribute of (a) arrays; (b) weighted graphs; (c) unweighted graphs; (d) sets of points; (e) none of these
4. Which of these is an optimization problem? (a) reachability; (b) traversal; (c) sort; (d) string search; (e) knapsack
5. Closest-pair is a(n) _____ problem (a) non-optimization vector, matrix or graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
6. Graph coloring is a(n) _____ problem (a) non-optimization vector, matrix or graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
7. Minimum-path search is a(n) _____ problem (a) non-optimization vector, matrix or graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
8. Knapsack is a(n) _____ problem (a) non-optimization vector, matrix or graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
1. Satisfiability is a(n) _____ problem (a) graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
2. Set partition is a(n) _____ problem (a) non-optimization vector, matrix or graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
3. Hamiltonian path is a(n) _____ problem (a) non-optimization vector, matrix or graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
4. Topological sort is a(n) _____ problem (a) non-optimization vector, matrix or graph; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
1. Web pages in general (a) compute functions; (b) do sorts; (c) provide services; (d) compute traversals; (e) none of these
2. DBMS design is a(n) _____ problem (a) non-optimization problem; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
3. Web-site design is a(n) _____ problem (a) non-optimization problem; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
4. GUI design is a(n) _____ problem (a) non-optimization problem; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
5. Protocol design is a(n) _____ problem (a) non-optimization problem; (b) optimization; (c) state-space search; (d) behavior-of-program; (e) interactive computation
1. Ù denotes (a) for all; (b) there exists; (c) and; (d) or; (e) not
2. Ø denotes (a) for all; (b) there exists; (c) and; (d) or; (e) not
3. " denotes (a) for all; (b) there exists; (c) and; (d) or; (e) not
4. Ú denotes (a) for all; (b) there exists; (c) and; (d) or; (e) not
5. $ denotes (a) for all; (b) there exists; (c) and; (d) or; (e) not
6. A Hoare triple specifies (a) loop invariant and postcondition; (b) precondition, program and postcondition; (c) program and postcondition; (d) performance requirements; (e) none of these
7. A precondition (a) should be true before an algorithm executes; (b) is asserted to be true at the beginning of every iteration of a loop; (c) should be true after an algorithm executes; (d) all the above; (e) none of the above
8. A postcondition (a) should be true before an algorithm executes; (b) is asserted to be true at the beginning of every iteration of a loop; (c) should be true after an algorithm executes; (d) all the above; (e) none of the above
1. Computation Tree Logic supports assertions about (a) algorithms; (b) interactive processes; (c) counted loops; (d) postconditions; (e) loop invariants
1. Distinguish an optimization problem from a constraint-satisfaction problem.
2. List two problems involving each of the following: arrays, graphs, sets of points on a coordinate graph.
3. Which
of the following problems use solutions to which others, and in what way? String
match, string search, pattern match
4. Distinguish
a solution tree from a binary search tree.
5. Closest-pair
and convex-hull are problems of what type?
6. Why
is graph coloring an optimization problem?
7. What
are the components of a graph that determine paths?
8. What
kind of graph does the shortest-path problem apply to?
9. What
is a subgraphs that is connected, acyclic, and provides a minimum-cost subway
system design?
10. What
kind of path passes through all vertices of a graph exactly once and returns to
the start?
11. What
problem finds the minimum-cost graph through all vertices of a graph?
12. What
problem seeks the maximum-valued subset of weighted items totaling less than a
given weight?
13. What
problem involves grouping items so as to fit them in a set of containers of
fixed size?
14. Satisfiability
is a property of what sort of expression?
15. What is an ongoing series of responses to inputs, queries, or requests?
16. What sort of problem requires servicing multiple input streams, possibly under time constraints?
17. Use
the principle of optimality to describe finding the best batting average among
players on teams in the major baseball leagues.
18. In
what sense can one problem be said to be reducible to another?
1. Which are conditions for algorithm correctness? (a) good programming methodology; (b) customer satisfaction; (c) approval by QA; (d) output is specified function of input; (e) program always halts and output is specified function of input
2. Total correctness is partial correctness plus (a) termination; (b) proof; (c) loop invariant; (d) postcondition; (e) efficiency
3.
Which of these is not used to prove correctness
of reactive systems? (a) Hoare triples; (b)
1. A loop invariant is asserted to be true (a) throughout the loop body; (b) at the beginning of every iteration of a loop; (c) is the same as the postcondition; (d) all the above; (e) none of the above
2. An assertion that is true at the start of each iteration of a loop is (a) a precondition; (b) a loop invariant; (c) a postcondition; (d) a loop exit condition; (e) none of these
3.
4. An appropriate loop invariant in an insertion sort is that (a) one particular element is less than its successor; (b) one particular element is the smallest; (c) the entire array is sorted; (d) part of the array is sorted; (e) none of these
5. An uncounted while statement may be proven correct by (a) contradiction; (b) a short series of tests; (c) construction; (d) induction; (e) none of these
6. A useful loop invariant to help prove correctness of a sorting algorithm could be (a) elements out of order are swapped; (b) elements are compared; (c) n passes occur; (d) the rightmost k elements are in ascending order; (e) none of these
7. A loop invariant asserts that (a) the precondition holds; (b) the postcondition holds, partly; (c) a weaker version of the postcondition holds; (d) the algorithm terminates; (e) none of these
1. An assertion is (a) a comment that tells what occurs in a program; (b) a comment that tells about values of variables and expressions; (c) always true throughout execution of a program; (d) an executable statement; (e) none of the above
2. Valid assertions (a) can help establish that code is to spec; (b) guarantee correctness; (c) guarantee that a program halts; (d) are always coded; (e) all the above
3. A Hoare triple consists of (a) precondition, loop invariant, postcondition; (b) program, loop invariant, postcondition; (c) precondition, program, postcondition; (d) proof, loop invariant, program; (e) none of these
4.
<f> P <j> is a (a) precondition; (b) loop
invariant; (c) postcondition; (d) Hoare triple; (e)
5.
In <f> P <j>, f is a (a) precondition; (b) loop invariant;
(c) postcondition; (d) Hoare triple; (e)
6.
In <f> P <j>, j is a (a) precondition; (b) loop invariant; (c) postcondition;
(d) Hoare triple; (e)
7.
In <f> P <j>, P is a (a) precondition; (b) loop
invariant; (c) postcondition; (d) program; (e)
1. Safety ensures that (a) that desired states will obtain; (b) that undesired states will never occur; (c) termination; (d) total correctness; (e) efficiency
2. Liveness ensures (a) that desired states will obtain; (b) that undesired states will never occur; (c) termination; (d) total correctness; (e) efficiency
3. A Kripke structure is (a) a control structure; (b) a transition system; (c) a diagram of an algorithm; (d) a proof; (e) a set of objects and formulas
1. What is an assertion, about the state of a repetitive process, that holds at the start of the process and helps to establish that the process spec is satisfied?
2. What are three classes of comments that help establish that the spec of a procedure is satisfied? For each, state where the comment should appear in the code or pseudocode.
3.
What is the name of a particular mathematical technique
or notation for defining a function, that converts straightforwardly into code
or pseudocode?
4.
What are Hoare triples used for?
5.
What is Computation Tree Logic used for?