# Unit-1

## Introduction

### Algorithm

It’s a finite set of instructions that are followed to accomplish a particular task. It’s a Step-by-Step process of performing a task.

**Characteristics**:

- Input: 0 or more
- Output: 1 or more
- Definiteness: Statement should be clear and unambiguous
- Finiteness: Must terminate at some point
- Effectiveness

### Performance Analysis

An algorithm is efficient if it takes less time to execute and consumes less space. It’s measured in terms of **Space Complexity** and **Time Complexity**.

#### Space Complexity

Amount of memory required to execute an algorithm. Generally memory is required for:

- Instruction Space: Space required to execute
- Data Space: Space required to store constants and variables
- Environment Space

Two Types:

- Constant Space Complexity (Fixed)
- Linear Space Complexity (Variable)

#### Time Complexity

Amount of time required by an algorithm to complete it’s execution.

Two Types:

- Constant Time Complexity (Fixed)
- Linear Time Complexity (Variable)

##### Asymptotic Notations

Comparison of Functions:

```
1 < log(n) < sqroot(n) < n < nlog(n) < n**2 < n**3 < ... < 2**n < 3**n ... < n**n
```

Types:

- O (Big-O) - Upper Bound
- Ω (Omega) - Lower Bound
- θ (Theta) - Average Bound

**O (Big-O)**: Function f(n) = O(g(n)) IFF there exists +ve constants *c* and nø, such that f(n) ⇐ c * g(n) forall n belongs to nø

**Ω (Omega)**: Function f(n) = Ω(g(n)) IFF there exists +ve constants *c* and nø, such that f(n) >= c * g(n) forall n belongs to nø

**θ (Theta)**: Function f(n) = θ(g(n)) IFF there exists +ve constants *c1 , c2* and *nø*, such that c1 * g(n) ⇐ f(n) ⇐ c2 * g(n) forall n belongs to nø

## Divide and Conquer

The problem is solved by dividing the problem to 2 or more subproblems that are similar to the original problem but smaller in size. Again these subproblems are divided into smaller problems until we can not divide further.

We find solution to the problem recursively and combine to create a solution for original problem.

Steps:

- Divide
- Conquer
- Combine

**General Algoritm**:

### Stassen’s Matrix Multiplication

Time Complexity:

### Merge Sort

Time Complexity:

### Quick Sort

Time Complexity:

# Unit-2

## Disjoint Sets

Two sets which don’t have any common elements are called disjoint sets.

**Operation**:

- Find
- Union

### Find Operation

Finding the parent of a node

### Union Operation

Combining both sets

### Collapsing Find

The process of directly linking a to the direct parent of a set by which we can reduce to time to find the parent of a node.

## BackTracking

Back tracking uses bruteforce approach to solve problems. It explores all possible solutions. It is not for optimization, it is used to find multiple solutions. It is shown as a tree called as **State Space Tree**

All backtracking problems have some constraint to exploring that node.

### N-Queen

Fill a chess board such that no two queens should be on the same row, column and diagonal.

### SumOfSubsets

Finding a subset whose sum is equal to a given number

### Graph Coloring

Color the graph such that no two adjacent vertices have the same color.

The minimum number of colors required to color the graph is called **Chromatic number**

# Unit-3

## Dynamic Programming

A dynamic programming problem is divided into number of stages at every stage an optimal decision is taken. It follows principle of Optimality.

**Principle of Optimality**: A problem is solved by following a sequence of decisions to get a optimal solution.

### Optimal Binary Search Tree (OBST)

Frequencies of every node are given we need find the minimum cost binary search tree, for that we need to find the cost matrix[C].

### KnapSack 0/1

We are given a set of weights, their profits and maximum weight knapsack can hold. We to find the Optimal solution to get maximum profit from choosing minimum weights in the knapsack.

### All Pair Shortest Path

From the given graph we first construct a adjacentcy matrix.

### Traveling Sales Person

Starting from any place the person has to visit every place exactly once and reach the starting place. Distance travelled should be minimum.

### Reliability Design

We are given number of devices and their cost and reliability including total amount to spent. We need to find maximum reliability.

# Unit-4

## Greedy Method

### Job Sequencing

In this we the number of jobs ‘J’ and their profits ‘P’ and deadlines ‘D’. We need solve in such a way that we get maximum profit within the deadline.

### KnapSack

Here there are three ways to solve the problem.

**Case 1:** We start selecting the objects based on their weight from lowest to heighest without crossing the maximum weight.

**Case 2:** We start selecting the objects based on their profit from heighest to lowest without crossing the maximum weight.

**Case 3:** We start selecting the objects based on their profit per weight basis from heighest to lowest without crossing the maximum weight (we could also include partial weight). This is the best Optimal Solution.\

Time Complexity:

### Kruskal’s Algorithm

We find minimum cost spanning tree of a graph.

First select a minimum cost edge from graph, consequently select next minimum cost edge from graph which should not form a cycle, repeat until all vertices are covered.

Time Complexity

### Prim’s Algorithm

We find minimum cost spanning tree of a graph.

First select a minimum cost edge from graph, consequently select next minimum cost edge selected to this edge without forming a cycle

Time Complexity

### Single Source Shortest Path (Dijkstra’s)

Used to determine shortest path from V(o) to all remaining vertices in a graph.

Time Complexity

# Unit-5

Problems are classified into two groups:\

- That can be solved in polynomial time by using deterministic algorithm.
- Searching for an element from an array
- Sorting given array

- That can be solved in polynomial time by using non-deterministic algorithm
- Knapsack problem
- Traveling sales person problem

**Deterministic Algorithm**: Here every operation is uniquely defined
**Non-Deterministic Algorithm**: Every operation may not have unique result instead they result in set of possibilities.

Types of problems:

- P - Problem
- NP - Problem
- NP - Complete
- NP - Hard