Spell Checker Using BK - Tree

89 2/13/2017 6:57:17 AM

BK- Tree(Burkhard-Keller Trees) Time Complexity O(log n) ...

Spell Checker Using Ternary Search Tree

80 2/13/2017 6:56:42 AM

Ternary Search Tree Advantages More efficientthanTrie. Disadvantages Ternary Search Tree requires a lot of extra space thanTrie. ...

Spell Checker Using Trie

83 2/13/2017 6:55:39 AM

Trie Advantages Can find all words beginning with a prefix. Disadvantages Tries is they require a lot of extra space. Complexity Search time: O(M) where M is the length of the string. ...

Spell Checker Using ​Binary Search Tree

58 2/13/2017 6:54:56 AM

Binary Search Tree Complexity A well-balanced BST will need time proportional to M * log N, M is maximum string length and N is a number of keys in the tree. ...

Spell Checker Using Hashing

87 2/13/2017 6:52:40 AM

Hashing Dictionary Will be stored in Hash Table Spell Checker Matching will be done by exact match. Disadvantage Does not support prefix search,where a user types a prefix and your dictionary shows all words starting with that prefix. Doesn’t support efficient printing of all words in the dictionary in alphabetical order and nearest neighbor search. Complexity Seach - O(n) ...

Ternary Search Tree

85 2/12/2017 9:20:28 AM

Ternary search tree is a type of trie (sometimes called a prefix tree), unlike trie(standard) data structure where each node contains max 26 pointers for its children, each node in a ternary search tree contains only 3 pointers. Pointers in Ternary Tree: The left pointer points to the node whose value is less than the value of the current node. The equal pointer points to the node whose value is equal to/close to the value of the current node. The right pointer points to the node whose value is greater than the value of the current node. ref:http://d1hyf4ir1gqw6c.cloudfront.net//wp-content/upl...

Design Spell Checker

93 2/12/2017 7:28:33 AM

Let's see various data structures (e.g. Hashing, Binary Search Tree, Trie, Ternary Search Tree, BK- Tree) which can be used to design data structure and their features and usage: ...

Design Tic-Tac-Toe

134 2/11/2017 10:57:16 PM

Object Oriented Tic-Tac-Toe Tic-tac-toe - Java Game Programming Case Study Object-Oriented Design - Ohio State Computer Science and Engineering TicTacToe - Game Design design Tic Tac Toe ...

Basic Terminology of Graphs

76 2/7/2017 6:15:55 AM

Define a Graph: G = (V, E)by defining a pair of sets: V = a set ofvertices E = a set ofedges Edges: Each edge is defined by a pair of vertices An edgeconnectsthe vertices that define it In some cases, the vertices can be the same Vertices: Vertices also callednodes Denote vertices with labels Representation: Represent vertices with circles, perhaps containing a label Represent edges with lines between circles Example: V = {A,B,C,D} E = {(A,B),(A,C),(A,D),(B,D),(C,D)} Path: sequence of vertices in which each pair of successive vertices is connected by an edge Cycle: a path that starts and ends ...


Height Balance Tree (aka AVL trees)

98 2/7/2017 6:09:13 AM

Balanced tree -A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of "much farther" and different amounts of work to keep them balanced. Height Balanced Tree aka AVL Tree(InventorsG.M. Adel’son-Vel’skii and E.M. Landis), are self-balancing binary search trees. An AVL tree is one that requires heights of left and right children of every node to differ by at most ±1. AVL Tree (Height Balanced Tree) - A tree whose subtrees differ in height by no more than one and the subtrees are height-...

Threaded Binary Tree

70 2/7/2017 6:06:58 AM

What is Threaded Binary Tree? It is a binary tree where leaf node is threaded towardsboththe in-order pre­de­ces­soror suc­ces­sor (leftorright) means all right null point­ers will point to inorder suc­ces­sororall left null point­ers will point to inorder predecessor. A binary tree isthreadedby making all right child pointers that would normally be null point to the inorder successor of the node (ifit exists), and all left child pointers that would normally be null point to the inorder predecessor of the node Why do we need Threaded Binary Tree? Binary tree...

Application of Tree Data Structure

69 2/7/2017 6:05:47 AM

Decision Making Next Move in games Computer chess games build a huge tree (training) which they prune at runtime using heuristics to reach an optimal move. Networking Router algorithms -Network Routing, where the next path/route of the packet is determined Social networking is the current buzzword in CS research. It goes without saying that connections/relations are very naturally modeled using graphs. Often, trees are used to represent/identify more interesting phenomena. Representation Chemical formulas representation XML/Markup parsers use trees Producers/consumers often use a balanced tree...

Basic Terminology Of Trees

80 2/7/2017 4:19:03 AM

Trees are hierarchical data structures, itsabstract data type, made up of nodes or vertices and edges without having any cycle. Tree Terminologies: Root The node at the top of the tree is called root. Parent Any node that has one edge upward to a node Child The node below a given node connected by its edge downward Leaf The node which does not have any child node Level The level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on. Height Height is consideredas is the maximum number of nod...

Factorial Function

83 2/7/2017 4:04:04 AM

Factorial Function: Theproduct of the integers 1 through given number. Represented using '!' factorial of 3 will represented as 3!. For example, 3! equals1*2*3(i.e 6) function factorial(n) { if (n<=1) return 1; else return n * factorial(n-1); } How factorial/recursion works: e.g. 3! = 3*2! = 3*2*1! (base case reached) = 3*2*1 (recursion is terminated) ...

Recursion

76 2/7/2017 4:02:34 AM

Recursion is the repeated application of a procedure or function or definition, with one base case/termination case. Examples of Recursion: Application Factorial function Check if word is palindrome Computing powers of a number The Sierpinksi gasket Counting employees under The 8-Queens problem Hierarchies A tree traversal algorithm Networks Google Map Graphs Business’s organization chart A minesweeper game Algorithm Euclid's algorithm (GreteGreateston divisor) Towers of Hanoi ...

Priority Queue

99 2/7/2017 3:53:34 AM

A priority queue can be implemented using many of the data structures that we've already studied (an array, a linked list, or a binary search tree (BST)). However, those data structures do not provide the most efficient operations. To make all of the operations very efficient, we'll use a new data structure called a heap. Implementing priority queues using heaps A priority queue is a data structure that stores priorities (comparable values) and perhaps associated information. A priority queue supports inserting new priorities and removing/returning the highest priority. When a priority...

Operations On Queues

98 2/7/2017 3:53:01 AM

Queueprimitive operationsare to be supported: enqueue(o): Insert o at rear of queue – Input: Object; Output: None dequeue(): Remove object at front; error if empty – Input: None; Output: Object removed Queuesupport operationsare to be supported: size(): Return number of objects in queue – Input: None; Output: Integer isEmpty(): Return a boolean indicating queue empty – Input: None; Output: Boolean first(): Return object at front without removing; error if empty – Input: None; Output: Object ...

Implementation of queues as an array and linked list

53 2/7/2017 3:51:37 AM

Queue - Array Implementation - Types Queue - Linked-List Implementation - Types ...

Circular Queue

72 2/7/2017 3:50:15 AM

A circular queue follows the basic rules of a queue data structure. It has the first in first out mechanism, but its size is restricted. We just need to keep track of two terms to understand, implement, and use a circular queue; they are: Front position (from where you can dequeue) Rear position (the last element's position in the queue) ...

Queues stored as a linked list

43 2/7/2017 3:49:44 AM

Queue - Linked-List Implementation - Types ...

Queues as an ADT

46 2/7/2017 3:48:19 AM

Collection: Elements of some proper type T Operations: void push (T t) void pop () T front () bool empty () unsigned int size () (plus constructor and destructor) Axioms: (for any Queue Q) Q.size(), Q.empty(), Q.push(t) are always defined Q.pop() and Q.front() are defined iff Q.empty() is false Q.empty(), Q.size(), Q.front() do not change Q Q.empty() is true iff 0 = Q.size() Suppose n = Q.size() and the next element pushed onto Q is t; then, after n elements have been popped from Q, t = Q.front() Q.push(t) increases Q.size() by 1 Q.pop() decreases Q.size() by 1 If t = Q.front() then Q.pop() re...

Converting an expression from infix to postfix

82 2/7/2017 1:06:19 AM

Infix, Prefix and Postfix Expressions: Examples: Infix Expression Prefix Expression Postfix Expression A + B + A B A B + A + B * C + A * B C A B C * + (A + B) * C * + A B C A B + C * A + B * C + D + + A * B C D A B C * + D + (A + B) * (C + D) * + A B + C D A B + C D + * A * B + C * D + * A B * C D A B * C D * + A + B + C + D + + + A B C D A B + C + D + Algorithm for converting an expression from infix to postfix: Create an empty stack called myStack for keeping operators. Create an empty list for output. Convert the input infix string to a list by using the string method split. Scan the token ...

Evaluating Postfix expressions

97 2/7/2017 1:05:41 AM

Infix, Prefix and Postfix Expressions: Examples: Infix Expression Prefix Expression Postfix Expression A + B + A B A B + A + B * C + A * B C A B C * + (A + B) * C * + A B C A B + C * A + B * C + D + + A * B C D A B C * + D + (A + B) * (C + D) * + A B + C D A B + C D + * A * B + C * D + * A B * C D A B * C D * + A + B + C + D + + + A B C D A B + C + D + Algorithm for evaluating postfix expression: Create an empty stack called myStack. Convert the string to a list by using the string method split. Scan the token list from left to right. If the token is an operand, convert it from a string to an ...

Arithmetic expressions

97 2/7/2017 1:04:50 AM

Anarithmetic expressionis an expression using additions+, subtractions-, multiplications*, divisions/, and exponentials** Anarithmetic expressionis anexpressionthat results in a numeric value. Types of numeric values Integers(whole numbers), and Realorfloating pointnumbers (numbers containing a decimal point). Anarithmetic expressionis a syntactically correct combination of numbers, operators, parenthesis, and variables. Examples: 1 + 3is4 1.23 - 0.45is0.78 3 * 8is24 6.5/1.25is5.2 8.4/4.2is2.0rather than2, since the result must be of Realtype. -5**2is-25 12/4is3 13/4is3rather than3.25. Since13...

stacks stored as a linked list

57 2/7/2017 1:04:04 AM

Implementation of stacks as a linked list ...

Implementation of stacks as an array and linked list

121 2/7/2017 1:02:21 AM

Implementation of stacks as an array Implementation of stacks as a linked list ...

Stack as an ADT

97 2/7/2017 1:01:27 AM

Collection:elements of some proper typeT Operations: voidpush(Tt) voidpop() Ttop() boolempty() unsigned intsize() constructor and destructor Axioms:(for any stackS) S.size(),S.empty(),S.push(t) are always defined S.pop() andS.top() are defined iffS.empty() is false S.empty(),S.size(),S.top() do not change S S.empty() is true iff 0 =S.size() S.push(t) followed byS.pop() leaves S unchanged afterS.push(t),S.top() returnst S.push(t) increasesS.size() by 1 S.pop() decreasesS.size() by 1 ...

Stack Operations

70 2/7/2017 12:54:10 AM

Stack Operations : Following primitive operations are to be supported: CreateStack() DestroyStack() Push(element) Pop(element) The following useful support operations are also going to be supported: Size() - returns the number of items in the stack IsEmpty() - returns true if the stack is empty, otherwise false Display() - Gives a picture of the stack contents on the screen ...

Array Operations

50 2/7/2017 12:21:52 AM

Operations on Array: Traversing an array. Insert Append a new node (to the end) of array Prepend a new node (to the beginning) of the array Inserting a new node to a specific position on the array Deleting a node from the array Updating a node in the array ...

Linked Lists Operations

53 2/7/2017 12:19:22 AM

Operations on Linked Lists: Traversing a linked list. Insert Append a new node (to the end) of a list Prepend a new node (to the beginning) of the list Inserting a new node to a specific position on the list Deleting a node from the list Updating a node in the list ...