Elec Eng IV

Mathematics

1994

1. Write an essay on each one of the following.

• The scheduling of projects using activity networks.
• The Travelling Salesman Problem.

• Describe Dijkstra's Algorithm for finding a minimum length path in a graph and Kruskal's Algorithm for finding a minimum weight spanning tree in a graph, and analyse the computational complexity of these two algorithms.
• Describe an algorithm for finding a maximum flow in a basic network and show how this algorithm can be used to prove the Maximum Flow Minimum Cut Theorem.

3. Consider an M|M|1|c queue with mean arrival rate l, mean service rate m (l ¹ m) and finite capacity c. Let p_n denote the probability that there are n customers in the system after the queue has settled down and let L be the average number of customers in the system, again when the system has settled down. Prove that,

A barber's shop has a total seating capacity of 10 (including the chair for the customer being served). The lone barber takes an average of 12 minutes to cut a customer's hair, and an average of 20 customers arrive each hour at the shop (arrival and service patterns are Poisson). Customers who arrive when the shop is full go to a different barber. How many customers per hour are lost, on average, due to the shop's restricted seating space?

4. (a) A company is considering investing in one of two stocks. Stock 1 always sells for Lm1 or Lm2. If it sells for Lm1 one day, then there is a 0.80 chance that it will sell for Lm1 again the next day, and if it is selling for Lm2 one day, then there is a 0.90 chance that it will again sell for Lm2 the following day. Stock 2 always sells for Lm1 or Lm2.5. If it sells one day for Lm1, then there is a 0.90 chance that it will again sell for Lm1 the next day, and if it sells for Lm2.5 on one day, then there is a 0.85 chance that it will again sell for Lm2.5 the following day. On the average, which stock will sell for a higher price?