Final Exam Review - Discrete
A. Selections/Concepts: For each of the following, find a problem in the book or on a test, write down the page number and problem number (or test and problem number), and work the problem. If a problem is not called for, explain the answer and reference a page number in your book or the date you took notes on the topic. Feel free to ask for help if you don’t understand what is being asked.
1. Given a digraph, find the critical path and minimum project time.
2. Select a picture of a digraph from a list of vertices and edges.
3. Find a directed Euler circuit in a description of digraphs by vertices and edges.
4. Select an adjacency matrix for a graph.
5. Find earliest start time and total time to complete job from a digraph.
6. Use notation to depict a complete graph.
7. Find the winner of a tournament.
8. From description of a graph, determine # of edges or vertices.
9. Use graph coloring to determine the chromatic number of a map or graph.
10. TSP tour tree - find optimal solution
11. Find a Hamiltonian circuit from a graph.
12. Find shortest path of a graph.
13. Use Kruskal's algortihm to find a MST
14. Find minimum and maximum # of edges given vertices of a connected graph.
15. find chromatic # of a tree.
16. Reverse Polish notation
17. Given a matrix, name the entry given by notation.
18. Multiply matrices
19. Given a preference schedule, find plurality winner, run-off winner, Borda count winner, Condorcet method winner, and the winner by approval voting.
20. Find essential coalitions, winning coalition and power index given a weighted voting situation.
21. Estate division - fair share and total settlement.
22. Apportionment - ideal ratio. initial quota,Hamilton, Jefferson and Hill methods of apportionment.
23. Word problems in matrices
24. Explain a payoff matrix
25. Transformation matrices
26. Write a recurrence relation from a table.
DEFINE:
a. Euler circuit
b. Euler path
c. Hamiltonian circuit
d. Hamiltonian path
e. Notation depicting a complete graph
f. Tree