Question $3(2$ marks$)$

A company named RT$\backslash$&T has a network of $\backslash ($ n $\backslash )$ switching stations connected by m high$-$speed communications links. Each customer's phone is directly connected to one station in their area. The engineers of RT$\backslash$&T have developed a prototype video$-$phone system that allows two customers to see each other during a phone call. However, to produce acceptable image quality, the number of links used to transmit video

signals between the two parties cannot exceed four. Suppose that the RT$\backslash$&T network is represented by a graph. Describe an efficient algorithm that computes, for each station, the set of stations it can reach using no more than four links.

Question $4(2$ marks$)$

The text is "ABCABCDABABCDABCDABDE," and the pattern is "ABCDABD." Apply the KMP pattern matching algorithm.

Question $1(2$ marks$)$

Consider the following flow network:

Compute the maximum flow for the network using the Ford & Fulkerson algorithm. Give the sequence of the augmenting paths and the value of the

maximum flow and the minimum cut.

Ins

I will be awarded full marks if you adequately answer the questions addressed. You will be awarded partial marks if your response demonstrates:

Application of the major and alternative approaches, methods, or algorithms to solve the problem.

Evidence of appropriate logic.

Evidence of correct computational skills and data structures.

Inclusion of appropriate comments or explanations.