Ignou MCS-021 Data and File Stucture Free Solved Assignment
Course Title : Data and File Structures
Assignment Number : MCA(2)/021/Assign/13
Last Dates for Submission : 15th October, 2013 (For July 2013 Session)
15th April, 2014 (For January 2014 Session)
This assignment has four questions which carry 80 marks. Answer all the questions. Each question carries 20 marks. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in theProgramme Guide. Ensure that you don’t copy the program from course material or any other source. All the implementations should be in C language.
Write an algorithm for the implementation of Doubly Linked Lists.
Step 1: Read the list operation.
Step 2: If operation is Create then process the following steps.
1.Create the new node and allocate memory for the new node.
2. Read the data in the new node.
3. Assign Flink and Blink as NULL.
4. Assign current as new.
Step 3: If operation is Insertion do the following steps.
iCheck insertion at beginning is true then
Create the new node and allocate memory for the new node
Read the data in the new node.
Move the current node to start position
Assign new->Flink=current
Now assign current->Blink=new
Insertion at between nodes is true then
Create the new node and allocate memory for the new node
Read the data in the new node.
Move the current node required position
Assign new node’s Blink=current.
Assign new node’s Flink=current->Flink
Assign current node’s Flink =new
Insertion at between nodes is true then
Create the new node and allocate memory for the new node.
Read the data in the new node.
Move the current node to end position.
Assign current node’s Flink =new.
Assign new’s Blink as current.
Assign new’s Flink as NULL.
Move end pointer to new node.
Step 4: If operation is deletion then do the following steps. i). Check deletion at beginning is true then.
Move current pointer to start position.
Move the start pointer next node in the link.
Assign start’s Blink as NULL.
Reallocate current node from memory.
Check deletion between two nodes is true
Move the current pointer to required position.
Assign current’s->Blink->Flink as current’s Flink.
Assign currents’s->Flink->Blink as current’s Blink.
Reallocate current from memory.
Check deletion at end is true
Move the current pointer to end position.
Assign current’s->Blink->Flink as Null.
Reallocate current from memory.
Reallocate current from memory. Step 5: If the operation is traversing.
Check deletion at end is true
Move the current pointer to end position.
Repeat the following steps until current becomes NULL.
If Backward traversing then
Move the current to end position.
Repeat the following steps until current becomes NULL.
if L.head == NIL return True
if L.head == NIL: x.prev = NIL L.head = x
while cur.next != NIL cur = cur.next
cur.next = x x.prev = cur x.next = NIL
x = L.head L.head = x.next
x.next.prev = L.head return x
Implement multiple queues in a single dimensional array. Write algorithms for variousqueue operations for them .
Write a note of not more than 5 pages summarizing the latest research in the area of
“Searching Algorithms”. Refer to various journals and other online resources. Indicatethem in your assignment.
The Fish-Search Algorithm
A typical example of dynamic search is WebGlimpse [Manber et al. 97] that allows users to dynamically search sub-areas of the Web predefined by a given “hop” parameter (i.e. depth in the Web viewed as a graph). The fish-search [De Bra et al. 94] proposes a more refined paradigm that can be explained by the following metaphor. It compares search agents exploring the Web to a school of fish in the sea. When food (relevant information) is found, fish (search agents) reproduce and continue looking for food, in the absence of food (no relevant information) or when the water is polluted (poor bandwidth), they die. The key principle of the algorithm is the following: it takes as input a seed URL and a search query, and dynamically builds a priority list (initialized to the seed URL) of the next URLs (hereafter called nodes) to be explored. At each step the first node is popped from the list and processed. As each document’s text becomes available, it is analyzed by a scoring component evaluating whether it is relevant or irrelevant to the search query (1-0value) and, based on that score, a heuristic decides whether to pursue the exploration in that direction or not: Whenever a document source is fetched, it is scanned for links. The nodes pointed to by these links (denoted “children”) are each assigned a depth value. If the parent is relevant, the depth of the children is set to some predefined value. Otherwise, the depth of the children is set to be one less than the depth of the parent. When the depth reaches zero, the direction is dropped and none of its children is inserted into the list.
Children whose depth is greater than 0 are inserted in the priority list according to the following heuristics:
are added to the head of the list
the first width children of an irrelevant node are added to the list right after the last child of a relevant node
the rest of the children are added to the tail (to be handled only if time permits) 4. We propose several improvements to the original fish-search algorithm in order to overcome these limitations. They result in a new algorithm, called the “shark search” algorithm, that while using the same simple metaphor, leads to the discovery of more relevant information in the same exploration time.
One immediate improvement is to use, instead of the binary (relevant/irrelevant) evaluation of document relevance, what we will call hereafter a similarity engine in order to evaluate the relevance of documents to a given query. Such an engine analyzes two documents dynamically and returns a “fuzzy” score, i.e., a score between 0 and 1 (0 for no similarity whatsoever, 1 for perfect
“conceptual” match) rather than a binary value. A straightforward method for building such an engine is to apply the usual vector space model [Salton & McGill 83]. It has been shown that these kinds of techniques give better results than simple string- or regular-expression matching [Salton 89, p306]. The similarity algorithm can be seen as orthogonal to the fish-search algorithm. We will assume in the rest of the paper that such an engine is available and that for any pair query, document, (q,d), it returns a similarity score sim(q,d) between 0 and 1.
This first improvement has a direct impact on the priority list. We use a “fuzzy” relevance score, giving the child an inherited score, thus preferring the children of a node that has a better score. This information can be propagated down the descendants chain, thus boosting the importance of the grandchildren of a relevant node over the grandchildren of an irrelevant node.
The children of an irrelevant node use their parent’s inherited score for calculating their own inherited score -
“fading” factor [Marchiori 97]. Thus, suppose documents X and Y were analyzed and that X has higher score. Suppose further that the children of both X and Y have a null score, and the algorithm now has to select the most promising of their grandchildren. Since both their scores are multiplied g
further away from X, into the great-grandchildren zone, would bring Y’s descendants back into inheritance is much more natural than the Boolean approach of the fish-search.
A more significant improvement consists of refining the calculation of the potential score of the children not only by propagating ancestral relevance scores deeper down the hierarchy, but also by making use of the meta-information contained in the links to documents. We propose to use the hints that appear in the parent document, regarding a child. The anchor text of the link is the author’s way to hint as to the subject of the linked document. A surfer on the Web, encountering a page with a large amount of links, will use the anchor text of the links in order to decide how to proceed. Some automated tools (see [Iwazume et al. 96]) also take advantage of that information.
This approach however can fail in poorly styled HTML documents, in which anchor texts consist only of “click here” or “jump there”, or when the anchor information is a picture without ALT information.
To remedy this problem we suggest using the close textual context of the link, and combining the information extracted from it with the information extracted from the anchor text. To reduce the risk of mistakenly giving a high potential score to a node due to a textual context that actually belongs to another node linked in the same paragraph (context boundaries are difficult to identify), we suggest a small fix. If a node has a relevant anchor text, the score of the textual context is set to the maximum (value of 1), thus giving it an edge over neighboring links. We claim that a policy that selects the children with the most promising anchor and anchor context information is preferable to arbitrarily selecting the first set of children.
Open Mass Spectrometry Search Algorithm
Large numbers of MS/MS peptide spectra generated in proteomics experiments require efficient, sensitive and specific algorithms for peptide identification. In the Open Mass Spectrometry Search Algorithm (OMSSA), specificity is calculated by a classic probability score using an explicit model for matching experimental spectra to sequences. At default thresholds, OMSSA matches more spectra from a standard protein cocktail than a comparable algorithm. OMSSA is designed to be faster than published algorithms in searching large MS/MS datasets.
The Shark-Search Algorithm
We propose several improvements to the original fish-search algorithm in order to overcome these limitations. They result in a new algorithm, called the “shark search” algorithm, that while using the same simple metaphor, leads to the discovery of more relevant information in the same exploration time.
One immediate improvement is to use, instead of the binary (relevant/irrelevant) evaluation of document relevance, what we will call hereafter a similarity engine in order to evaluate the relevance of documents to a given query. Such an engine analyzes two documents dynamically and returns a “fuzzy” score, i.e., a score between 0 and 1 (0 for no similarity whatsoever, 1 for perfect
“conceptual” match) rather than a binary value. A straightforward method for building such an engine is to apply the usual vector space model [Salton & McGill 83]. It has been shown that these kinds of techniques give better results than simple string- or regular- expression matching [Salton 89, p306]. The similarity algorithm can be seen as orthogonal to the fish-search algorithm. We will assume in the rest of the paper that such an engine is available and that for any pair query, document, (q,d), it returns a similarity score
sim(q,d) between 0 and 1.
This first improvement has a direct impact on the priority list. We use a “fuzzy” relevance score, giving the child an inherited score, thus preferring the children of a node that has a better score. This information can be propagated down the descendants chain, thus boosting the importance of the grandchildren of a relevant node over the grandchildren of an irrelevant node. The children of an irrelevant node use their parent’s inherited score for calculating their own inherited score – by ing” factor
[Marchiori 97]. Thus, suppose documents X and Y were analyzed and that X has higher score.
Suppose further that the children of both X and Y have a null score, and the algorithm now has to select the most promising of their grandchildren. Since
shark search chooses X’s grandchildren first (which seems intuitively correct). Stepping further away from X, into the great-grandchildren zone, would bring Y’s descendants back into consideration, given an app
more natural than the Boolean approach of the fish-search.
A more significant improvement consists of refining the calculation of the potential score of the children not only by propagating ancestral relevance scores deeper down the hierarchy, but also by making use of the meta-information contained in the links to documents. We propose to use the hints that appear in the parent document, regarding a child. The anchor text of the link is the author’s way to hint as to the subject of the linked document. A surfer on the Web, encountering a page with a large amount of links, will use the anchor text of the links in order to decide how to proceed. Some automated tools (see [Iwazume et al. 96]) also take advantage of that information.
This approach however can fail in poorly styled HTML documents, in which anchor texts consist only of “click here” or “jump there”, or when the anchor information is a picture without ALT information.
To remedy this problem we suggest using the close textual context of the link, and combining the information extracted from it with the information extracted from the anchor text. To reduce the risk of mistakenly giving a high potential score to a node due to a textual context that actually belongs to another node linked in the same paragraph (context boundaries are difficult to identify), we suggest a small fix. If a node has a relevant anchor text, the score of the textual context is set to the maximum (value of 1), thus giving it an edge over neighboring links. We claim that a policy that selects the children with the most promising anchor and anchor context information is preferable to arbitrarily selecting the first set of children.
What are the applications of Tries?
Tries find numerous applications. Some of them are explained as follow s:
1 - Tries in the Web search engines: Tries can be used to store and maintain the index words and the relevant Web site address. In the Web search process the users query the index words, the search engine has to fetch the appropriate links as results. In this process the search engines maintain the table of index words to the Web link or Website address. To maintain a sequence of words as the index , the search engines follow the tries procedure for quick retrieval of appropriate information.
2 – Symbol table maintenance : A symbol table is a data structur e used in the language translators such as compilers or interpreters. A symbol table consists of the address
location, syntax and semantic information of the identifier , type and scope of the ident ifier . To maintain all the identifiers’ information, the compilers or interpreters use tries procedure in the form of hash tables.
As a replacement for other data structures
As mentioned, a trie has a number of advantages over binary search trees.[4] A trie can also be used to replace a hash table, over which it has the following advantages:
Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.
There are no collisions of different keys in a trie.
Buckets in a trie which are analogous to hash table buckets that store key collisions are necessary only if a single key is associated with more than one value.
There is no need to provide a hash function or to change hash functions as more keys are added to a trie. A trie can provide an alphabetical ordering of the entries by key.
Tries do have some drawbacks as well:
Tries can be slower in some cases than hash tables for looking up data, especially if the data is directly accessed on a hard disk drive or some other secondary storage device where the random-access time is high compared to main memory.[5]
Some keys, such as floating point numbers, can lead to long chains and prefixes that are not particularly meaningful. Nevertheless a bitwise trie can handle standard IEEE single and double format floating point numbers.
Some tries can require more space than a hash table, as memory may be allocated for each character in the search string, rather than a single chunk of memory for the whole entry, as in most hash tables.
Dictionary representation
A common application of a trie is storing a predictive text or autocomplete dictionary, such as found on a mobile telephone. Such applications take advantage of a trie’s ability to quickly search for, insert, and delete entries; however, if storing dictionary words is all that is required (i.e. storage of information auxiliary to each word is not required), a minimal deterministic acyclic finite state automaton would use less space than a trie. This is because an acyclic deterministic finite automaton can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored.
Tries are also well suited for implementing approximate matching algorithms, including those used in spell checking and hyphenation[2] software.
Algorithms[edit source | editbeta]
We can describe lookup (and membership) easily. Given a recursive trie type, storing an optional value at each node, and a list of children tries, indexed by the next character, (here, represented as a Haskell data type):
, children :: [(Char,Trie a)] }
We can look up a value in the trie as follows:
find :: String -> Trie a -> Maybe a find [] t = value t
find (k:ks) t = case lookup k (children t) of
In an imperative style, and assuming an appropriate data type in place, we can describe the same algorithm
in Python (here, specifically for testing membership). Note that children is map of a node’s children; and we say that a “terminal” node is one which contains a valid word.
def find(node, key): for char in key:
if char not in node.children: return None
node = node.children[char] return node.value
trie * initialize(trie *node)
node=(trie *)malloc(sizeof(trie)); node->words=0;
node->edges[i]=NULL; return node;
trie * addWord(trie *ver,char *str)
ver->prefixes=(ver->prefixes)+1; char k;
if(ver->edges[index]==NULL)
ver->edges[index]=initialize(ver->edges[index]);
ver->edges[index]=addWord(ver->edges[index],str);
int countWords(trie *ver,char *str)
return countWords(ver->edges[k],str);
int countPrefix(trie *ver,char *str)
return countPrefix(ver->edges[k],str);
trie *start=NULL; start=initialize(start); int ch=1;
printf(“1. Insert a word “); printf(“2. Count words”); printf(“3. Count prefixes”); printf(“0.
Exit”); printf(“your choice: “); scanf(“%d”,&ch); char input[1000]; switch(ch)
printf(“a word to insert: “);
start=addWord(start,input);
printf(“a word to count words: “);
printf(“%d”,countWords(start,input));
printf(“a word to count prefixes: “);
printf(“%d”,countPrefix(start,input));
