Data Structures and algorithms

#### introduction..

beauty of computer science lies in efficiency with which it solves complicated problems which may take days n yrs 4 a normal human to to solve.Ever challenging task being to reduce consumption of time,money resourses for a perticular problem.Data-str deals with storing data effectively reducing consumption of the resourses.Algorithms are the strategies(in normal user language) to solve a problem.In this here we go about effective algos once again to reduce the resourse consumption.
DS(data Str) is very useful for advanced studies in computer science and a must read for aspiring IT proffessionals!

#### who should read this?

I'm a java programmer so my style of illustration here may or may not help just beginners.But Data-str by itself is a much independent subject basic programming knowledge is enough for you to take-off..

# complexity

• Recurrence Relations
• Iteration
• Master’s Theorem
• Examples

# Elementary Data Structures

Here we examine representat'n of dynamic sets with simple data str tht use pointers.

• Linked Lists (Insertion, Deletion, Reverse )
• Arrays
• Stacks
• Queue

# Hashing

#### Hashing

• Hash Functions (Linear and Quadratic)
• Collisions and Chaining
• Order
• Examples

#### Expression Evaluation

• Infix to Postfix

# Sorts

Here v 5nd brief descript'n of different sorting algos

• Insertion
• Bubble Sort
• Merge Sort
• Quick Sort (Partition Algorithm – Complexity Calculation)

• Selection Sort
• Bucket Sort
• Counting Sort
• K th Order Statistics

# Tree

• Terminology (Balanced Tree, Complete Tree, height, L-R children, Parent…)
• Binary Tree (Insertion, Deletion)
• Binary Search Tree (Tree formation, Insertion, Deletion)
• Implementation of Trees

# Heap

A heap is a specialized tree-based data structure that satisfies the heap property.We have 2 types of heaps .These are generally used 2 implement priority queues.

• Heap Sort
• Time Complexity
• Example : Trie

• Insertion
• Deletion
• AVL

# Graphs

In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.

• Terminology (Directed, Undirected, Acyclic, Cyclic, Weighted graphs)
• Representation
• Traversal
• BFS-Breadth First Search
• DFS-Depth First Search
• Topological Sort

# Tree spanning and shortest paths

• MST-Minimum Spanning Tree
• Kruskal’ s Algorithm (Greedy Approach)
• Prim’ s Algorithm
• Single Pair Shortest Paths
• Dijkstra’ s Algorithm
• All Pair Shortest Paths
• Floyd Warshall’ s Algorithm

# greedy algos n dynamic programmin

#### Greedy algo

Examples

• Fractional Knapsack Problem

#### Dynamic Programming

Examples

• 0-1 Knapsack Problem
• LCS
• Sequence
• Matrix Multiplication

# Back Tracking

• Examples
• Pole Example
• Matrix Multiplication
• Strassen‘ s Multiplication
• Polynomial Multiplication
• Karatsuba‘ s Rule
• Polynomial Evaluation
• Horner’ s Rule
• Rehashing

page revision: 39, last edited: 24 Jun 2007 12:22