String replacement program in C

A program to find a particular pattern in a string and replace all occurrences of that pattern with a new pattern to produce a modified string.

#include<stdio.h>
#include<string.h>

void main()
{
  char str[100], pattern[50], replace[50], new_str[100], temp[50];
  int l1, l2, l3, flag_eos = 0, pattern_found = 0;
  int i = 0, j, k, n;
  printf("\n###################################\n");
  printf("Enter any string\n");
  gets(str);
  printf("\n###################################\n");
  printf("Enter pattern to be replaced\n");
  gets(pattern);
  printf("\n###################################\n");
  printf("Enter new pattern\n");
  gets(replace);

  l1 = strlen(str);
  l2 = strlen(pattern);
  l3 = strlen(replace);
 
  while(flag_eos == 0)
  {
    for(; i < l1; i++)
      // if any character of str = first character of the pattern
      if((str[i] == pattern[0]) && (i + l2 - 1 < l1))
      {
        for(j = i, k = 0; j < i + l2; j++)
          temp[k++] = str[j];
        temp[k] = '\0';
        break;
      }
    if(i == l1)
    {
      flag_eos = 1;
      temp[0] = '\0';
    }
    if(strcmp(temp, pattern) == 0)
    {
      pattern_found = 1;
      n = 0;
      for(j = 0; j < i; j++)
        new_str[n++] = str[j];
      for(j = 0; j < l3; j++)
        new_str[n++] = replace[j];
      for(j = i + l2; j < l1; j++)
        new_str[n++] = str[j];
      new_str[n] = '\0';
      // Recompute the new string length and
      // continue to look for more occurrences
      strcpy(str, new_str);
      l1 = strlen(str);
    }
    else
      i = i + 1;
  }
  if(pattern_found == 1)
  {
    printf("\n###################################\n");
    printf("The modified string is \n");
    puts(str);
    printf("###################################\n");
  }
  else
  {
    printf("\n###################################\n");
    printf("Pattern not found in the string !!!\n");
    printf("###################################\n");
  }
}

Written by Munia Balayil

Bellman-Ford Algorithm - Shortest Path Algorithm

"The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights. The algorithm is named after its developers, Richard Bellman and Lester Ford, Jr. 

Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm. However, if a graph contains a "negative cycle", i.e., a cycle whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed by repeatedly following the cycle, so there may not be a shortest path. In such a case, the Bellman-Ford algorithm can detect negative cycles and report their existence, but it cannot produce a correct "shortest path" answer if a negative cycle is reachable from the source." - Wikipedia

INITIALISE_SINGLE_SOURCE(G, start)
{
  for each vertex v ∈ v(G)
    dist[v] <- ∞
    pred[v] <- NIL
  dist[start] <- 0
}
// dist[v] <- distance of vertex "v" from vertex "start"
// pred[v] <- predecessor of "v" in the shortest path 
//            from "start"

RELAX(u, v, cost)
{
  if dist[v] > dist[u] + cost[u, v]
    dist[v] <- dist[u] + cost[u, v]
    pred[v] <- u
} 

BELLMAN_FORD(G, cost, start)
{
  INITIALISE_SINGLE_SOURCE(G, start)
  for i <- 1 to |v(G)| - 1
    do for each edge (u, v) ∈ E[G]
      do RELAX(u, v, cost)
  for each edge (u, v) ∈ E[G]
    do if dist[v] > dist[u] + cost[u, v]
      then return FALSE
  return TRUE
}

Written by Munia Balayil
Image courtesy - ArsRout

Dijkstra's Algorithm - Shortest Path Algorithm

"Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, producing a shortest path tree.

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined." - Wikipedia

INITIALISE_SINGLE_SOURCE(G, start)
{
  for each vertex v ∈ v(G)
    dist[v] <- ∞
    pred[v] <- NIL
  dist[start] <- 0
}
// dist[v] <- distance of vertex "v" from vertex "start"
// pred[v] <- predecessor of "v" in the shortest path 
//            from "start"

RELAX(u, v, cost)
{
  if dist[v] > dist[u] + cost[u, v]
    dist[v] <- dist[u] + cost[u, v]
    pred[v] <- u
} 

DIJKSTRA(G, cost, start)
{
  INITIALISE_SINGLE_SOURCE(G, start)
  S <- φ
  Q <- V[G]
  while Q ≠ φ do
    u <- EXTRACT_MIN(Q)
    S <- S U {u}
    for each vertex v ∈ Adj[u]
      do RELAX(u, v, cost)
}
// S <- Set of vertices whose final shortest path weights
//      from the source (start) have already been determined
// Q <- min_priority queue of vertices, keyed by their 'dist'
//      values

Written by Munia Balayil

Prim's Algorithm - Minimum Cost Spanning Tree problem

"Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim–Jarník algorithm." - Wikipedia

1. MST_PRIM(G, cost, root)
2.   for each vertex u ∈ V[G]
3.     do Key[u] <- ∞
4.        Pred[u] <- NIL
5.   Key[root] <- 0
6.   Q <- V[G] // create a priority queue of the vertices
7.   while Q ≠ φ
8.     do u <- EXTRACT_MIN(Q)
9.       for each v ∈ Adj[u]
10.        do if v ∈ Q & (cost(u,v) < Key[v])
11.          then Pred[v] <- u
12.               Key[v] <- cost(u,v)

Key[v] -> minimum weight of any edge connecting v to a vertex in the tree

Pred[v] -> parent of v in the tree

Q -> min priority queue of all the vertices that are not in the tree

Initially, A = { (v, Pred[v]) : v ∈ V - {root} - Q }
Finally, A = { (v, Pred[v] : v ∈ V - {root} } // Q is empty

References :

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil

Kruskal's Algorithm - Minimum Cost Spanning Tree Problem

"Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component)." - Wikipedia

1. MST_KRUSKAL(G, cost)
2.   A -> φ
3.   for each vertex v ∈ V[G]
4.     do MAKE-SET(v)
5.   sort the edges of E into non-decreasing order by weight
6.   for each edge (u,v) ∈ E taken in non-decreasing order by weight
7.     do if FIND-SET(u) ≠ FIND-SET(v)
8.       then A <- A ∪ { (u,v) }
9.         UNION(u,v)
10.  return A

MAKE-SET(x) -> creates a new set (tree) whose only
member is x (creates disjoint sets)

UNION(x,y) -> unites the dynamic sets that contain x & y, 
say Sx & Sy into a new set that is the union of these two sets 
Sx & Sy are assumed to be disjoint prior to this operation

FIND-SET(x) -> return a pointer to the representative of the set
containing x (here the root of the tree to which it belongs to)

References :

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil