Re: Fwd: reg exam [Request: EVENT-3208 is created]
0 views
Skip to first unread message
ICMHelpDesk
Mar 26, 2020, 4:09:31 AM3/26/20
to cse-a...@googlegroups.com
Thank you for your email request. Your request ID is EVENT-3208
------------------------------------------------------------
gdiv...@gmail.com wrote:
<html>
<head></head>
<body>
---------- Forwarded message ---------- From: sireesha Vikkurty
<sireesha...@gmail.com>
Date: Thu, Dec 8, 2011 at 10:24 PM Subject: Re: reg exam To: koppu sharath
<shara...@gmail.com>
Cc: gdiv...@gmail.com Sharat, Find the required information below: If it is not clear refer to the document in the attachment. I hope divya has mailed u all the question bank. *Stack Applications:* 1. Evaluation of Postfix expressions 2. Conversion of infix to postfix expression 3. Undo sequence in a text editor 4. Page visited history in a web browser 5. Reversing Data: We can use stacks to reverse data. (example: files, strings) Very useful for finding palindromes. 6. Conversion of decimal number to binary number *Queue Applications:* * * 1. Access to shared resources (eg. Printer) 2. Multiprogramming 3. Round robin job scheduling by operating system can be implemented using queues 4. Call center phone systems will use a queue to hold people in line until a service representative is free 5. Buffers on MP3 players and portable CD players, iPod playlist. Playlist for jukebox - add songs to the end, play from the front of the list *BFS Applications:* Queue data structure is used to implement BFS Breadth-first search can be used to solve many problems in graph theory, for example: 1. Finding all nodes within one connected component 2. Copying Collection, Cheney's algorithm 3. Finding the shortest path between two nodes *u* and *v* 4. Testing a graph for bipartiteness * * *DFS Applications:* Stack data structure is used to implement DFS Algorithms that use depth-first search as a building block include: 1. Finding connected components. 2. Topological sorting. 3. Finding 2-(edge or vertex)-connected components. 4. Finding 3-(edge or vertex)-connected components. 5. Finding the bridges of a graph. 6. Finding strongly connected components. 7. Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.) 8. Maze generation may use a randomized depth-first search. 9. Finding biconnectivity in graphs. *Trees Applications:* 1. One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer: 2. If we organize keys in form of a tree (with some ordering e.g., BST), we can search for a given key in moderate time (quicker than Linked List and slower than arrays). Self-balancing search trees like AVL and Red-Black trees guarantee an upper bound of O(Logn) for search. 3. Like Linked Lists and unlike Arrays, Pointer implementation of trees don’t have an upper limit on number of nodes as nodes are linked using pointers. 4. Manipulate hierarchical data. 5. Make information easy to search (see tree traversal). 6. Manipulate sorted lists of data. 7. As a workflow for compositing digital images for visual effects. 8. Router algorithms *Graphs Applications:** * 1. Used in the area of Computer Network Security2. Graph coloring problems 3. Network flow problems 4. Prim’s algorithm 5. Kruskal’s algorithm 6. Shortest path algorithm On Mon, Dec 5, 2011 at 3:54 PM, koppu sharath
<shara...@gmail.com>
wrote: &gt; gudevng medam.tis is sharath.plz send applications of &gt; trees,graphs,bfs,dfs,stacks,queues which are frequently asked in exam.we &gt; are not findind accurate in any text book &gt; &gt; -- G.Divya
</shara...@gmail.com>
</shara...@gmail.com>
</sireesha...@gmail.com>
</body>
</html>
Reply all
Reply to author
Forward
0 new messages