Hello to all of you …… Feel yourself lucky to visit this blog because i have made many dreams come true and i am felling very happy by solving some of the most difficult problems in computer science .. one may feel that its really tough to create graph using linked list . But now this difficult problem is solved, now graph can be created at run time and i have written a program in c-language which creates graph at run time . The screen shot of the program execution is here ……….now how about creating a graph at run time and start doing depth first search on it ? no need to worry i am going to provide a link to a .exe file which creates graph at run time and also allows to perform depth first search on it here is the link to .exe file https://docs.google.com/file/d/0ByhrU1o5gom6MjZkMWVrTHhXYUE/edit?pli=1 ( file name - DFS1.exe size - 18.6 kb ) All we need to do here is to just create a graph as shown in the above image and then enter the starting vertex to begin the dfs .The program which i have written just allocates the space which is required at run time for the creation of graph and uses a recursive function called as “dfs” which is also actually used in the actual dfs algorithm Also i have written a c-program which inserts , deletes , searches vertices and edges and also performs dfs on it the screen shot of program execution is given below
In a similar way i have also written a program based on concept of breadth first search using linked list which creates a graph at run time and also traverses the graph in bfs manner . The screen shot of program execution is here ........
there are two more programs which i have written -> all pairs shortest path (or floyd’ s warshalls algorithm) using linked lists in this program i took infinity distance as value 9999 the screen shot of program execution is here ....
also i have written program based on concept of ->minimum spanning tree using linked list based on prims algorithm the screen shot of program execution is here .....
the specialty of all this programs is that nowhere i have used any arrays and also none of the programs asks to enter the number of vertices or edges while executing the program. Recently i have implemented AVL-trees the screen shot of program execution is given below the tree is displayed in preorder fashion the nodes key and its balence factor(b) are displayed while printing the tree
another avl tree example shown below
in my view AVL trees are far more better than red-black trees . Now i will explain why AVL trees are better than red black trees with a small example consider the image given below
the upper trees are red black tree and the bottom one is the AVL tree now when we delete the node in red black tree pointed by arrow then the resulting tree is not height balanced even though it satisfies all the properties of red-black trees but when same operation is done in AVL tree then since the roots balence factor becomes 2 after deletion we need to perform a left rotation followed by right rotation which gives a perfectly balanced binary height search tree .... therefore its better to completely avoid red-black trees Also i have implemented chaining hash table the screen shot of program execution is given below ... hash function used in this program Hash(X)=X mod 10
importance of chained hash tables- Chained hash tables with linked lists are popular because they require only basic data structures with simple algorithms, and can use simple hash functions that are unsuitable for other methods. The cost of a table operation is that of scanning the entries of the selected bucket for the desired key. If the distribution of keys is sufficiently uniform, the average cost of a look-up depends only on the average number of keys per bucket—that is, on the load factor. Chained hash tables remain effective even when the number of table entries n is much higher than the number of slots. Their performance degrades more gracefully (linearly) with the load factor. For example, a chained hash table with 1000 slots and 10,000 stored keys (load factor 10) is five to ten times slower than a 10,000-slot table (load factor 1); but still 1000 times faster than a plain sequential list, and possibly even faster than a balanced search tree.As far as my program is concerned it can increase its slots form 10 to 10,000 or more than that depending on requirement and i have taken only 10 slots from (0 to 9) in the above example of chained hashing .. My facebook address is http://www.facebook.com/r5274 or my email id is rajgopal527@gmail.com flame527@yahoo.com the cost of each program is given below dfs using linked lists - $ 4 billion dfs using linked lists ( inserts,deletes,searches vertices and edges ) - $ 16 billion bfs using linked lists- $ 4 billion all pair shortest path using linked lists - $ 4 billion minimum spanning tree using using linked lists - $ 4 billion chaining hash tables - $ 4 billion Avl tree - $ 111 billion live demo for all remaining programs - $ 1 billion the buyer has to verify his proof of identity before buying any program or willing to have demo of all remaining programs i will be thankful to all those people who create awareness about my blog linked list representation for graphs and avl-trees ..... there is slight change in master theorem's case 1 please check the below image
thank you
