ALGO (1)

The document is a comprehensive guide on algorithms, covering various topics such as asymptotic analysis, recurrence relations, divide and conquer strategies, greedy techniques, graph-based algorithms, and dynamic programming. It includes solved examples, practice questions, and student assignments to enhance understanding. The publication has gone through multiple editions from 2015 to 2023, indicating its ongoing relevance in the field of computer science and information technology.

Uploaded by

Akhu Patel

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

32 views19 pages

ALGO (1)

Uploaded by

Akhu Patel

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 19

COMPUTER SCIENCE &

INFORMATION TECHNOLOGY

Algorithms

Comprehensive Theory
with Solved Examples and Practice Questions

www.madeeasypublications.org
MADE EASY Publications Pvt. Ltd.
Corporate Office: 44-A/4, Kalu Sarai (Near Hauz Khas Metro
Station), New Delhi-110016 | Ph. : 9021300500
Email : infomep@madeeasy.in | Web : www.madeeasypublications.org

First Edition : 2015

Algorithms Second Edition : 2016

Third Edition : 2017

EDITIONS
© Copyright by MADE EASY Publications Pvt. Ltd. Fourth Edition : 2018
All rights are reserved. No part of this publication may be Fifth Edition : 2019
reproduced, stored in or introduced into a retrieval system, Sixth Edition : 2020
or transmitted in any form or by any means (electronic, Seventh Edition : 2021
mechanical, photo-copying, recording or otherwise), Eighth Edition : 2022
without the prior written permission of the above mentioned Ninth Edition : 2023
publisher of this book.
Tenth Edition : 2024

MADE EASY Publications Pvt. Ltd. has taken due care

in collecting the data and providing the solutions, before
publishing this book. Inspite of this, if any inaccuracy or
printing error occurs then MADE EASY Publications Pvt.
Ltd. owes no responsibility. We will be grateful if you could
point out any such error. Your suggestions will be appreciated.
Algorithms
CHAPTER 1 CHAPTER 4

Asymptotic Analysis of Algorithms.............. 3-30 Greedy Techniques......................................90-138

1.1 Need for Performance Analysis............................................. 3 4.1 Introduction...............................................................................90

1.2 Worst, Average and Best Cases.............................................. 4 4.2 Basic Examples of Greedy Techniques..............................91

1.3 Asymptotic Notations............................................................... 5 4.3 Greedy Technique Formalization........................................92

1.4 Analysis of Loops........................................................................ 9 4.4 Knapsack (Fractional) Problem............................................93

1.5 Comparisons of Functions....................................................19 4.5 Representations of Graphs....................................................96

1.6 Asymptotic Behaviour of Polynomials..............................20 4.6 Minimum Cost Spanning Tree (MCST) Problem................98

Student Assignments...............................................................23 4.7 Single Source Shortest Path Problem (SSSPP)................ 107
4.8 Huffman Coding.................................................................... 117

CHAPTER 2 Student Assignments............................................................. 121

Recurrence Relations�� 31-54

CHAPTER 5
2.1 Introduction...............................................................................31
2.2 Substitution Method...............................................................32 Graph Based Algorithms......................... 139-162
2.3 Master Theorem........................................................................43 5.1 Introduction............................................................................ 139
Student Assignments................................................................46 5.2 Graph Searching.................................................................... 139
5.3 Directed Acyclic Graphs (DAG)......................................... 151
CHAPTER 3 5.4 Topological Sorting.............................................................. 152
Student Assignments............................................................. 155
Divide and Conquer�� 55-89
3.1 Introduction...............................................................................55
CHAPTER 6
3.2 Quick Sort....................................................................................55

3.3 Strassen’s Matrix Multiplication...........................................60

Dynamic Programing............................... 163-195
6.1 Introduction............................................................................ 163
3.4 Merge Sort..................................................................................63
6.2 Fibonacci Numbers............................................................... 163
3.5 Insertion Sort.............................................................................66
6.3 All-Pairs Shortest Paths Problem...................................... 166
3.6 Counting Inversions................................................................67
6.4 Matrix Chain Multiplication............................................... 170
3.7 Binary Search.............................................................................69
6.5 The 0/1 Knapsack Problem................................................ 183
3.8 Bubble Sort.................................................................................72
6.6 Multistage Graph................................................................... 187
3.9 Finding Min and Max..............................................................73
6.7 Traveling-Salesman Problem............................................. 189
3.10 Power of An Element...............................................................76
Student Assignments................................................................78 Student Assignments............................................................. 192

iii