WOKAS blogger

The greedy algorithm always adopts the best solution at the given time, with no regard for how that choice will affect to future choices. Using a greedy algorithm generally indicates that the implementer hopes that the series of “best” local choices made will lead to a final “best” choice. If so, that the algorithm has produced an optimal solution. If not sub optimal solution has been found. This coin changing problem is following a greedy algorithm strategy. Let’s say some one buy some items at the store and change from his purchase is 103. This 103 can give minimum units of denominators of that particular country. To solve such kind of problems we can use greedy strategy, 100’s > 1, 2’s > 1, 1’s > 1. That is the smallest number of units of coins that will equal to 103. It has been proven that optimal solutions for coin changing can always current denominations of coins. However if we introduce some other denomination to the mix, the greedy algorithm doesn’t produce an

In maze traversal, we must have to traverse deeper as soon as possible through the selected particular path until we reach the dead end. When we are on the way in that path, if it closed then we must have to back track to previous state to select another path. For this reasons, this traversal very similar to the DFS algorithm. Strategy for exploring Maze:  To convert given maze to a graph mark each intersection, corner and dead end (vertex) visited.  We mark each corridor (edge) as traversed.  We keep track of the path back to the entrance (start vertex) by means of a rope. (recursion stack) According to above all reasons, DFS (Depth First Search) algorithm very similar to a classic strategy for exploring a maze. Implementation in C# Graph.cs using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Maze_traversal {     class Graph     {         private int maxVertex;         private Vertex[] vList;         private int[

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 matc

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#