# Data Structures and Algorithms PDF: Based on introduction to algorithms by Cormen For GATE/B.Tech Computer Engineering

Data structures and algorithms pdf provided by me is my handwritten notes pdf based on the latest pattern of Gate/PSU and B.E/B.tech.

This notes is helpful for all of the Computer science and Engineering students who is in undergraduate course and preparing for Graduate Appitude test in Engineering GATE.algorithms pdf, cormen, introduction to algorithms pdf, introduction to algorithms cormen pdf, algorithm notes pdf, introduction to algorithms, design and analysis of algorithms, data structures and algorithms pdf,Data Structures and Algorithms PDF: Based on introduction to algorithms by Cormen For GATE/B.Tech Computer Engineering

**Data Structures and Algorithms PDF**** **

**Problem ****to ****Program **

**Introduction **

**Performance ****Evaluation **

**Sorting ****Problem **

**Mathematical ****Preliminaries **

**Asymptotic ****Notation **

**DESIGN ****AND ****ANALYSIS ****OF ****ALGORITHM **Tic

**1****.****PROBLEM****TO****PROGRAM**

**Mathematical ****Model ****Informal ****a****lgor****ithm ****Abstract ****Data ****Type **

*(***A****D****T****) ****Ps****e****udo ****Lang****u****a****g****e ****C****o****de ****Data ****Structure **(DS) **Program ****(****C****–****P****r****ogram) **

program 1) Model the problem using an appropriate mathematic model (Informal algorithm)

2) The informal algorithm is written in pseudo language

3) The stepwise refinement of pseudo language gives various types of data used and Operations to be performed on data. (i.e., data type)

4) We create ADT for each data type.

5) We choose an appropriate Data Strucure to implement eachzADI

6) Finally replace informal statements in pseudo language code by C–code

**An ****algorithm **is a finite sequence of computational steps that transform the input into the output in finite number of steps

**A ****data ****type **is a collection of objects and a set of operations that act on those objects

An **a****bstract ****d****ata ****t****yp****e ****(****ADT**) is a data type, that is organized in such a way that the specification of the objects and the operations on the objects is separated from the representation of the objects and the implementation of the operation. **ADT ****is ****mathematical ***m***ode****l ****of ****data ****type **

**A ****dat****a ****structure****(****DS**) is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them. *W*e use DS to implement ADT:

**Pseudo ****cod**e: Mixture of natural language and high level programming language constructs that describes algorithm

**A ****program **is an expression of an algorithm in a programming language

**2****.****INTRODUCTION**- 1. Non–Co
**mputational****problem**

A problem that has no precise and simple specification **Example**: Convince your boss for salary hike; convince your faculty for marks.

**2****.****Computational****problem**

Specification of input

Specification output as function of input

**Exampl**e: The sorting problem:

**Input**: a sequence <al, a2......,an> of n numbers. **Output**: a permutation <al, a2,..., an > of the input with al <= a2 <= .... <= an .

RU DESI*GN *AND AN**ALYSIS ****OF ****ALGOR***I***THM **

**3****.****A****lg****orithm Definition**

An Algorithm is well–defined computational procedure that takes some value, or set of values as input and produces some value, or set of values as output.

**Instanc**e: A particular input called an **instance **of a computational problema **Exampl**e: The input sequence <31, 41, 59, 26, 41 58> is an instance of the sorting problem.

**4****.****Algorithm****Characteristics**

All algorithms should satisfy the following criteria. **Input**: Zero or more quantities are externally supplied. A **Output**: At least one quantity–is, produced. **Definitene****s****s**: Each instruction is clear and unambiguous. **Finitene****s**s: For all cases, the algorithm terminates after a finite number or *s***teps****. ****Effectiveness**: instruction is basic enough to be carried out.

**Definition**: Algorithms that are definite and effecti*v*e are called **computational ****pr****oced****ures ****Example**: Digital computer.

**Definition**: An algorithm is said to þe correct if, for every input instance, it halts with the correct output.

- 5. The study of A
**lgorithm****includes****the****foll**owing–im**portant****areas**

**Desig****n ****an ****a****l****g**orithm: Creating and algorithm is an art which may never be fully automated, Different design strategies: Divide and Conquer, Greedy, Dynamic programming....etc. **Express ****an ****algo**rithm: Algorithm specification using Pseudo code. **Validat****e ****an ****algo**rithm (correctness): To show that algorithm computes the correct answer for all possible legal inputs, **Analysis ****an ****algo**rithm: Find the time and space complexity. Prove that we cannot solve the problem any faster using asymptotic analysis **Implementati**on : Implementing algorithm in a programming language **Verification **:–Test the program (debugging and profiling)

- 3. PERFORMANCE EVALUATION
**1****.****Performance****evaluation**

As an algorithm is executed, it uses the computers CPU to perform operations and its memory to hold the program and data. **An ****efficient algorithm **

needs less running time

- uses less space 1.1. Space Complexity: The space complexity of an algorithm is the amount of memory if

needs to run to completion. 1.2. Time Complexity: The time complexity of an algorithm is the amount of computer time it

needs to run to completion. 1.3. **Performance ****evaluation **of an algorithm refers to the task of computing space and time

complexity of an algorithm **1****.****4 ****Performance ****evaluation **can be loosely divided into two major phases:

1) a priority **estimates ****(****Performance ****Analysis****) **

1 Uses analytical methods

- Machine independent

**DESIGN ****AND AN***A***LYSIS ****OF ALGORITHM **

2). **a ****posterior ****testing ****(****Performance ****Measurement or prof**iling):

. It is the process of executing a correct program on data sets and measuring time

and space it takes to compute results

1 Machine dependent Perform**ance Analysis ****is ****general ****methodo**logy because

- It uses high level description of an algorithm (Pseudo–code)

All possible input instances are taken into account

- Machine independent

**2****.****Space****complexity**

**2****.****1 ****Components ****of ****s****p****ace ****complexity **

**Instruction ****spa****c****e****: **

Space needed for code

**Data ****Space****: **

- i. Space needed for constants and simple variables ii. Space needed for dynamically allocated objects (such as arrays, structures, etc)
**Environment****stack****space:** - i. It is used to save information needed to resume execution of partially executed function. ii. Each time a function is invoked the following data are saved on the environment stack

The return address The values of local variables and formal parameters

**Recursion ****stac****k ****s****pac****e**: Amount of stack space needed by recursive functions is called recursion stack space. It depends on

- Space needed by local variables and formal parameters
- Maximum depth of recursion (i.e., maximum number of nested recursive calls)
- Compiler being used
**T****h****e****total****s****p****ace**needed by a program is divided into two parts:

- 1. Fixed Part 2. Variable Part

**A ****fixed ****p**art independent of instance characteristics (e.g., size, number, value) 1. Instruction space 2. Data space (space needed for constants and simple variables and some dynamically

allocated objects) **Note**: The space needed by some of the dynamically allocated memory may also

be independent of problem size 3. Environment stack space for non–recursive functions

*A **v***ariable ****pa**rt dependent on instance characteristics

- 1. Dynamically allocated space 2. Recursion stack space

**2****.****2 ****D**efinition

**The ****space ****comp**lexity S (P) of any algorithm P can be written as

S (P) = C + Sp(I) C constant that denotes fixed part Sp Variable part that depends on instance characteristics (I) (e.g., size, number, value)

** CRMD ****ANALYSI****S ****OF ****ALG***O***RITHM **

2.3 Examples

- 1.

Algorithm abc(a, b, c)

return a + b + b**c**/*(a+b+4.0);

Sp(abc) = 0

C = Space needed for a, b, cand result;

- 2.

Algorithm Sum(a, n)

S = 0; for(i = 1 to n)

S = s + a[i]; return s;

Space required for

**f**ormal parameters a and n

local variables s, i and constant 0

- instruction space. This amount of space needed does not depend on value of n.

Ssum(n) = 0 Since a is actually the address of the first element in a[](i.e., a[0]), the space needed by it is also constant

Algorithm rsum(int a[], int n)

if(n>0)

return rsum(a, n–1)+a[n–1]; return 0;

Let reference of a = 4bytes; value of n = 4 bytes; return address = 4 bytes are stored on recursion stack for each recursion call. Each recursive call require 12 bytes Depth of recursion = (n+1) recursion stack space = 12(n+1) Sisum(n) = 12 (n+1)

**3****.****Time****Complexity**

**3****.****1 ****Time ****Complexity **

Time taken by a program P is sum of compile time and runtime

T(P) = C + TP(I) C (compile time) is independent of instance characteristics (*.*. constant) TP(I) (Run time) is dependent on instance characteristics.

(i) However, **analytical ****approach ****to ****determine ****the ****exact ****runtime ****is ****complicated **

Since runtime depends on machine dependent issues like i) Type of processor, ii) Access

rate (rate*/*write operations), iii) Architecture and machine independent issue iv) input size. **(****ii****) ****Run ****time ****expression ****should ****be ****machine****–****inde****pe****n****d****ent****. **

Therefore, **we ****estimate ****runtime ****as ****function ****of ****input ****size**. i.e., we find rate of growth of time with respect to input size.

Running time = f(input size)

**WWW****.****GRADESETTER.****COM **

# Introduction to algorithms cormen pdf

- I Foundations
- The Role of Algorithms in Computing
- Getting Started
- Growth of Functions
- Divide-and-Conquer
- Probabilistic Analysis and Randomized Algorithms
- II Sorting and Order Statistics
- Heapsort
- Quicksort
- Sorting in Linear Time
- Medians and Order Statistics
- III Data Structures
- Elementary Data Structures
- Hash Tables
- Binary Search Trees
- Red-Black Trees
- Augmenting Data Structures
- IV Advanced Design and Analysis Techniques
- Dynamic Programming
- Greedy Algorithms
- Amortized Analysis
- V Advanced Data Structures
- B-Trees
- Fibonacci Heap
- Emde Boas Trees
- Data Structures for Disjoint Sets
- VI Graph Algorithms
- Elementary Graph Algorithms
- Minimum Spanning Trees
- Single-Source Shortest Paths
- All-Pairs Shortest Paths
- Maximum Flow
- VII Selected Topics
- Multithreaded Algorithms
- Matrix Operations
- Linear Programming
- Polynomials and the FFT
- Number-Theoretic Algorithms
- String Matching
- Computational Geometry
- NP-Completeness
- Approximation Algorithms
- VIII Appendix: Mathematical Background
- A Summations
- B Sets, Etc.
- C Counting and Probability
- D Matrices