Final Exam Math/ECE 276 Winter 2016
Name: ______This is a closed book exam. You may use a calculator and the formulas handed out with the exam. Show all work and explain any reasoning which is not clear from the computations. (This is particularly important if I am to be able to give part credit.) Turn in this exam along with your answers. However, don't write your answers on the exam itself; leave them on the pages with your work. Also return the formulas to the formula pile.
1. Your company just bought seven workstations which are going to be placed in the offices A, B, C, D, E, F and G, one per office. They are going to be linked into a network. The company’s plant department would charge the following to connect the computers in each of the following pairs of offices. See table at right. (It is not possible to make a direct connection between every pair of offices.)
a. (4 points) Draw a weighted graph representing this information. The vertices are the offices and the edges are the possible direct connections with cost.
b. (9 points) It is not necessary to use all the direct connections listed above. It is only necessary to establish enough direct connections so that there is a route from each workstation to every other workstation through a sequence of direct connections. For example, if you establish direct connections from A to B and from B to C then it is not necessary to make one from A to C. What group of direct connections should be made so as to link together all the workstations in the cheapest possible fashion.
2. Consider the circuit at the right.
a. (3 points) Write down a Boolean expression that describes the output w of this circuit as a function of the inputs x, y and z.
b. (3 points) Make the Karnaugh map of this function.
c. (3 points) Construct a simpler expression for this function using the map.
d. (3 points) Construct a circuit for the simpler expression in c.
3. (13 points) Use the algorithm discussed in class to find a shortest path from A to N in the graph below. For full credit your work must show the computations that lead to your answer.
4. (13 points) Three married couples are on a journey together. They come to a river that they must cross. There is no bridge, but there is a boat that can hold no more than two people. The crossing of the river is complicated by the fact that the husbands are all very jealous and will not permit their wives to be left without them in a company where there are other men present, even if there are other women present. You need to find a way they can all get to the other side of the river and proceed on their journey.
Part of the problem is to construct a graph model of the situation. Suppose the men are labeled m1, m2 and m3 and the women are labeled w1, w2 and w3 with m1 married to w1, etc. Also, suppose the boat is labeled by b. The vertices of the graph are going to be configurations of men, women and the boat on the two sides of the river that meet the restriction that no wife is in the company of other men if her husband is not present.
For example, the starting vertex is at the right with all the men and women and the boat on the north side of the river and nothing on the south side of the river.
The ending vertex is at the right with all the men and women and the boat on the south side of the river and nothing on the north side of the river.
A typical intermediate vertex is at the right with m2, w2, m3, w3 and the boat on the north side of the river and m1 and w1 on the south side of the river.
There is an edge between two vertices if it is possible to go from one to the other by a single crossing of the river. For example, the two vertices at the right are connected by an edge since it is possible to go from one to the other by m2 and m3 crossing the river in the boat.
Find a way for the three couples to go from the north side of the river to the south side keeping in mind that
a. the boat can hold no more than two people.
b. no wife can be in the presence of other men without her husband present even in the boat.
Show your answer as a sequence of vertices connected by edges beginning at the starting vertex and ending with the ending vertex.
5. (12 points) Consider the following relation, », where the objects being related are the subsets of the set {1,2,3,4}. Let X = {1, 4}. We say a set A is related to a set B if AÇX = BÇX and we write A»B if this is true. So {1, 3} » {1, 2}, since {1, 3}ÇX = {1, 3}Ç{1, 4} = {1} and {1,2}ÇX={1,2}Ç{1, 4} = {1}. However, {1, 3} {3, 4}, since {1, 3}ÇX = {1} and {3,4}ÇX={3,4}Ç{1, 4} = {4}. This is an equivalence relation on the set W of all subsets of {1,2,3,4}. You don't have to show this. Find all the equivalence classes and which elements of W are in each equivalence class.
6. Consider the expression 2x - + 7 - .
a. (6 points) Draw the tree representation for this expression. Assume that + and – have equal priority and in the absence of parentheses associate from left to right.
b. (6 points) Convert the expression to postfix.
7. Consider the following relation, «, where the objects being related are ordered pairs (a,b) where a and b can each be any of the integers 1, 2 or 3. (a,b)« (c,d) if a £ c and b £ d. For example (1,2)«(2,3) since 1 £ 2 and 2£3. However (1,2) (2,1) since 2 1. This is a partial ordering on on the set A={(a,b):a,b=1,2,3}. You don't have to show this.
a. (4 points) Draw the Hasse diagram for this partial order.
b. (4 points) Find the maximum (or least upper bound) of (1,2) and (3,1).
c. (4 points) Do a topological sort of the elements of A with this partial order.
8. Consider the following electric circuit.
To the right is a spanning tree for the underlying graph.
a. (3 points) Draw each of the cycles (or loops or circuits) in the fundamental system of cycles associated with this spanning tree for the graph of the electric circuit. Be sure to indicate a direction in each of the loops. Let p be the number of cycles that you found. What is p?
b. (3 points) Let v1, …, v9 be the voltage drops along each of the eight branches in the electric circuit above. For each of the cycles you found in part a write down the corresponding equation involving v1, …, v9 that you obtain by applying Kirchoff's voltage law to that cycles. Your answer should only involve v1, …, v9. It should not involve R1, …, R9 or e1, …, e9. Express your answer in vector matrix form.
c. (3 points) Let c1, …, cp be the currents in the p cycles that you found in part a. Let i1,…, i9 be the currents in the nine branches of the circuit. Express i1,…, i9 in terms of c1, …, cp. Your answer should only involve i1,…, i9 and c1, …, cp. It should not involve R1, …, R9 or e1, …, e9. Express your answer in vector matrix form. What is the relationship between the matrices in parts b and c?
d. (2 points) For each branch j write down an equation that expresses vj in terms of ej, Rj and ij. You will need to use Ohms law. Express your answer in vector matrix form.
e. (2 points) Combine the vector-matrix equations you obtained in parts b, c, and d to get an equation of form Ac = b, where c is the column vector whose components are the cj and A is a matrix and b is a vector that you should express in terms of the matrices and vectors appearing in parts b, c and d.
Solutions
3. Here is the result of applying Djkstra's algorithm.
Now follow the links backward from N to A to get a shortest path. Doing this gives NJKHIDGBA. Reversing gives AB-G-D-I-H-K-J-N as the shortest path from A to N.
5. If we replace {1, 4} for X in AÇX = BÇX we get A » B if AÇ{1, 4} = BÇ{1, 4}. What this means is that if A»B then A contains 1 if and only if B contains 1 and A contains 4 if and only if B contains 4. However, we can add or delete either 2 or 3 from A and still get a set that is related to A. So the sets related to A are the ones that contain the same elements of {1, 4} as A but differ from A in the elements 2 and 3. So [A]=equivalence class of A = {B: A » B} = {B:oftheelements1 and 4, A and B have the same ones}. Thus [Æ]={Æ,{2},{3}, {2, 3}}, [{1}]= {{1}, {1, 2}, {1, 3}, {1, 2, 3}}, [{4}]={{4},{4,2},{4,3},{4,2,3}} and [{1,4}]={{1,4},{1, 2, 4}, {1, 4, 3}, {1, 2, 3, 4}}. So there are 4 equivalence classes, each with four objects.
7. a. See diagram at right.
b. We want the smallest element larger than both (1,2) and (2,3). This is (3, 2).
c. Start at bottom and remove and list objects that don't have anything below them. One possibility is (1,1), (1,2), (2,1), (1,3) (2,2), (3,1), (2,3), (3,2), (3,3).
5