String Anagrams

You are required to implement a program which is able to print out all anagrams of a specified string. Two strings will become anagrams if letters of one string can be rearranged to obtain the other string. For example, the string "rats" is an anagram of "star". Your first step is to load a reasonable number of words in the dictionary into a hash table enabling the user to efficiently look for anagrams of a given word/s. The user should have the facility to specify anagram queries through stating the required word/s. The output should print out the given string/s along with the number of matching anagrams and the corresponding list of anagrams retrieved from the hash table.

       Example :    traps            2          sprat    strap

                            opt               2          top       pot

                            star              1          rats

      Note: The matching anagrams that the program prints out may be ordered differently.

Algorithm and Implementation 

Our first step is to load all of the words in the dictionary.txt into the hash table. A clever trick that we have used to facilitate this is to first sort the letters of every word we insert into hash table to produce a key for each word. For example, the key for the string for both "star" and "rats" is "arst". We will then use a hash table to store pairs of strings, where the pair consists of the original word and it’s key. When performing insertions, we will compute the hash of the key of the word to compute the correct bucket. This approach guarantees that all words which are anagrams of one another are stored in the same bucket of the hash table. Similarly, when we are searching for anagrams, we will first compute the key of the word we are searching for, then hash the key, then search that bucket for anagram matches. For this question, there are 5 files.

1. list.h ==> implementation of the linked list

2. hashtable.h ==> implementation of the hash table and basic functionality (insert, find) of a chained hash table.

3. main.cpp ==> a main program which loads words from the dictionary.txt into the hash table and then answers anagram queries

4. dictionary.txt ==> this contains all the anagrams of strings.

5. user_string.txt ==> user can be able to search word/words by specifying in this file.

http://www.scribd.com/doc/59581966/Dictionary

http://www.scribd.com/doc/59582006/User-String

http://www.scribd.com/doc/59582148/Hash-Table-1

http://www.scribd.com/doc/59582184/List-1

http://www.scribd.com/doc/59581988/Main

Dijkstra's Algorithm with example

Dijkstra's Algorithm solves the single-source shortest path problem in weighted graphs. Here we show it running on a planar graph whose edge weights are proportional to the distance between the vertices in the drawing -- thus the weight of an edge is equal to its visible length.

Dijkstra's algorithm starts from a source node, and in each iteration adds another vertex to the shortest-path spanning tree. This vertex is the point closest to the root which is still outside the tree. Watch as the tree grows by radiating out from the root. Note that it is not a breadth-first search; we do not care about the number of edges on the tree path, only the sum of their weights.

Dijkstra(G, w, s)

  Initialize-Single-Source(G, s);

  S<-- {}; Q <-- V[G];

  while Q not equal {}

    do u = extract-min(Q)

       S = S U {u}

       for each vertex v E Adj[u]

           do relax(u, v, w)

Example: Step by Step operation of Dijkstra algorithm.

Step1. Given initial graph G=(V, E). All nodes nodes have infinite cost except the source node, s,  which has 0 cost.

Step 2. First we choose the node, which is closest to the source node, s. We initialize d[s] to 0. Add it to S. Relax all nodes adjacent to source, s. Update predecessor (see red arrow in diagram below) for all nodes updated.

Step 3. Choose the closest node, x. Relax all nodes adjacent to node x. Update predecessors for nodes u, v and y (again notice red arrows in diagram below).

Step 4. Now, node y is the closest node, so add it to S. Relax node v and adjust its predecessor (red arrows remember!).

Step 5. Now we have node u that is closest. Choose this node and adjust its neighbor node v.

Step 6. Finally, add node v. The predecessor list now defines the shortest path from each node to the source node, s.

Q as a linear array

EXTRACT_MIN takes O(V) time and there are |V| such operations. Therefore, a total time for EXTRACT_MIN in while-loop is O(V²). Since the total number of edges in all the adjacency list is |E|. Therefore for-loop iterates |E| times with each iteration taking O(1) time. Hence, the running time of the algorithm with array implementation is O(V² + E) = O(V²).

Q as a binary heap ( If G is sparse)

In this case, EXTRACT_MIN operations takes O(lg V) time and there are |V| such operations.The binary heap can be build in O(V) time.Operation DECREASE (in the RELAX) takes O(lg V) time and there are at most such operations.

Hence, the running time of the algorithm with binary heap provided given graph is sparse is O((V + E) lg V). Note that this time becomes O(ElgV) if all vertices in the graph is reachable from the source vertices.

Q as a Fibonacci heap

In this case, the amortized cost of each of |V| EXTRAT_MIN operations if O(lg V).

Operation DECREASE_KEY in the subroutine RELAX now takes only O(1) amortized time for each of the |E| edges.

As we have mentioned above that Dijkstra's algorithm does not work on the digraph with negative-weight edges. Now we give a simple example to show that Dijkstra's algorithm produces incorrect results in this situation. Consider the digraph consists of V = {s, a, b} and E = {(s, a), (s, b), (b, a)} where w(s, a) = 1, w(s, b) = 2, and w(b, a) = -2.

Dijkstra's algorithm gives d[a] = 1, d[b] = 2. But due to the negative-edge weight w(b, a), the shortest distance from vertex s to vertex a is 1-2 = -1.

Shortest path Algorithms

In a shortest path problem we are given a weighted graph where each edge has an associated numerical value, called the weight of the edge.The weights are often used to represent time, cost, penalties or any other quantity that accumulates linearly along a path and that one wishes to minimize.

The weight of path p = < v0, v1,….vk> is the sum of the weights of its constituent edges.

Given a weighted graph and two vertices u and v, we want to find a path of minimum total weight between u and v. 

 –Length of a path is the sum of the weights of its edges.

We will focus on Single source shortest paths problem: given a graph G = (V,E), we want to find a shortest path from a given source vertex s Є V to each vertex v Є V.

Shortest Path Properties

Property 1: A sub path of a shortest path is itself a shortest path.

Property 2: There is a tree of shortest paths from a start vertex to all the other vertices.

The shortest path algorithms use the technique of relaxation.

For each vertex v Є V, an attribute d[v] is maintained which is an upper bound on the weight of a shortest path from source s to v.

d[v] – shortest path estimate

The shortest path estimates and predecessors are initialized by the following O(V) time procedure.

INITIALIZE-SINGLE-SOURCE (G,s)

for each vertex v Є V[G]

     do d[v] <-- ∞

         π[v] <-- NIL

                     d[s] <-- 0 

Relaxing and edge (u,v) – consists of testing whether the shortest path to v found so far  can be improved by going through u. If so d[v] and π[v]  values should be updated.

A relaxation step may decrease the value of the shortest path estimate d[v].

Relaxation

d[v] > d[u] + w(u,v)                              d[v] ≤ d[u] + w(u,v)

d[v] is changed by relaxation            d[v] is unchanged by relaxation

Relax (u,v,w)

if d[v] > d[u] + w(u,v)

  then d[v] <-- d[u] + w(u,v)

   π[v]  <-- u