WOKAS blogger

There are two groups of men and women who desire to get married. Participants of each group indicate who among the opposite sex would be acceptable as a potential spouse. Every woman can be married to at most one man, and every man to at most one woman. To solve this problem, we used set of input data for equal number of men and women, where each person has an ordered list of preferences for whom that person would like to marry. Task is to pair up the man with the woman in such a way that no one is unsatisfied with their partner.  There we used bipartite graph implementation through the adjacency matrix and BFS algorithm to pair up (married couple) men and women and repeatedly improve the pairings as necessary until every person is satisfied. Consider an engagement (m, w) between man m and woman w. It says that (m, w) is unstable if either m or w has another person they would rather marry. It means unstable engagement meets one or more of the following condition. (Following ...

A military group is monitoring messages from terrorists which are transmitted as binary coded data streams. (a) The military is looking for an efficient way to search an identified pattern in the serial stream, in the data so far monitored, at a given time. In this setting, suppose the message T[1 ...n] is being transferred serially, in the order T[1],T[2],.... the military is interested in checking if the text seen so far contains a pattern P, where P has length m. Every time when the next letter of the text T is transmitted, it is necessary to check if the text seen so far contains P. (b) Now the terrorists are broadcasting reversed messages of the original message. So that although the same pattern P is used, the text T[1 ...n] is being transferred in reverse. That is, in the order T[n],T[n−1],... .Modify your algorithm so that it still detects the occurrence of P in the text T[i...n] immediately (i.e., in constant time) after the letter T[i] is seen. Implementation in C# ...