Algorithms And DataStructure

Sorting (selection, insertion, merge, heap, etc.) Stacks & Queues Linked Lists Trees & Graphs (binary trees, binary search trees, etc.) Hash tables Bit manipulation Dynamic Programming Backtracking

Formula: fn(n) = O(g(n)) Case: Worst case Upper Bound: c.g(n) (Function never grows faster than the upper bound) Must true: fn(n) <= c.g(n)

For all n >= no (N not) and c > 0 c must be equal to or greater than 0 no must be greator than 0 (Positive number)

Formula: fn(n) = Ω(g(n)) Case: Best case Lower Bound: c.g(n) (Function never grows slowest than the lower bound) Must true: fn(n) >= c.g(n)

For all n >= no (N not) and c > 0 c must be equal to or greater than 0 no must be greator than 0 (Positive number)

Formula: fn(n) = θ(g(n)) Case: Average case Lower and Upper Bound: c1.g(n) and c2.g(n) (Function never grows slowest/faster than the lower bound and upper bound) Must true: c1.g(n) <= fn(n) <= c2.g(n)

For all n >= no (N not) and c > 0 c must be equal to or greater than 0 no must be greator than 0 (Positive number)

• constant − Ο(1)
• logarithmic − Ο(log n)
• linear − Ο(n)
• n log n − Ο(n log n)
• quadratic − Ο(n2)
• cubic − Ο(n3)
• polynomial − nΟ(1)
• exponential − 2Ο(n)

• Travelling Salesman Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm
• Graph - Map Coloring
• Graph - Vertex Cover
• Knapsack Problem
• Job Scheduling Problem

• Merge Sort
• Quick Sort
• Binary Search
• Strassen's Matrix Multiplication
• Closest pair (points)

• Fibonacci number series
• Knapsack problem
• Tower of Hanoi
• All pair shortest path by Floyd-Warshall
• Shortest path by Dijkstra
• Project scheduling