# 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 Ti

1. 1. PROBLEM TO PROGRAM

Mathematical Model Informal algorithm Abstract Data Type

(ADT) Pseudo LanguagCode Data Structure (DS) Program (CProgram)

progra1) 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 Ccode

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 abstract data type (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 model of data type

A data 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. We use DS to implement ADT

Pseudo code: Mixture of natural language and high level programming language constructs that describes algorithm

A program is an expression of an algorithm in a programming languag

1. 2. INTRODUCTION
2. 1. NonComputational problem

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

1. 2. Computational problem

Specification of input

Specification output as function of input

Example: 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 DESIGN AND ANALYSIS OF ALGORITHM

1. 3. Algorithm Definition

An Algorithm is welldefined computational procedure that takes some value, or set of values as input and produces some value, or set of values as output

Instance: A particular input called an instance of a computational problema Example: The input sequence <31, 41, 59, 26, 41 58> is an instance of the sorting problem

1. 4. Algorithm Characteristics

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

Definition: Algorithms that are definite and effective are called computational procedures Example: Digital computer

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

1. 5. The study of Algorithm includes the followingimportant areas

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

1. 3. PERFORMANCE EVALUATION
2. 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 ANALYSIS OF ALGORITHM

2). a posterior testing (Performance Measurement or profiling)

. 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 Performance Analysis is general methodology because

• It uses high level description of an algorithm (Pseudocode

All possible input instances are taken into account

• Machine independent
1. 2. Space complexity

2.1 Components of space complexity

Instruction space

Space needed for code

Data Space

1. i. Space needed for constants and simple variables ii. Space needed for dynamically allocated objects (such as arrays, structures, etc) Environment stack space:
2. 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 stack space: 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 The total space needed by a program is divided into two parts
1. 1. Fixed Part 2. Variable Part

A fixed part 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 nonrecursive functions

A variable part dependent on instance characteristics

1. 1. Dynamically allocated space 2. Recursion stack space

2.2 Definition

The space complexity 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 ANALYSIS OF ALGORITHM

2.3 Examples

1. 1

Algorithm abc(a, b, c

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

Sp(abc) =

C = Space needed for a, b, cand result

1. 2

Algorithm Sum(a, n

S = 0; for(i = 1 to n

S = s + a[i]; return s

Space required for

• formal parameters a and

local variables s, i and constant

• 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), the space needed by it is also constant

Algorithm rsum(int a[], int n

if(n>0

return rsum(a, n1)+a[n1]; 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

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 machineindependent

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)

# 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
• 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
• 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

## Algorithm Notes PDF introduction to algorithms cormen #### Diznr International

Diznr International is known for International Business and Technology Magazine.

error: