Lekh Raj Vermani - An Elementary Approach to Design and Analysis of Algorithms (Primers in Electronics and Computer Science)

Primers in Electronics and Computer Science

Print ISSN: 2516-6239

Online ISSN: 2516-6247

(formerly known as ICP Primers in Electronics and

Computer Science ISSN: 2054-4537)

Series Editor: Mark S. Nixon (University of Southampton, UK)

This series fills a gap in the market for concise student-friendly guides to the essentials of electronics and computer science. Each book will address a core elements of first year BEng and MEng courses and will stand out amongst the existing lengthy, dense and expensive US textbooks. The texts will cover the main elements of each topic, with clear illustrations and up-to-date references for further reading.

Published

Vol. 4An Elementary Approach to Design and Analysis of Algorithms
by Lekh Raj Vermani and Shalini Vermani

Vol. 3Image Processing and Analysis: A Primer
by Georgy Gimel'farb and Patrice Delmas

Vol. 2Programming: A Primer Coding for Beginners
by Tom Bell

Vol. 1Digital Electronics: A Primer Introductory Logic Circuit Design
by Mark S. Nixon

Published by

World Scientific Publishing Europe Ltd.

57 Shelton Street, Covent Garden, London WC2H 9HE

Head office: 5 Toh Tuck Link, Singapore 596224

USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601

Library of Congress Cataloging-in-Publication Data

Names: Vermani, L. R. (Lekh R.), author. | Vermani, Shalini, author.

Title: An elementary approach to design and analysis of algorithms / by Lekh Raj Vermani (Kurukshetra University, India) and Shalini Vermani (Apeejay School of Management, India).

Description: New Jersey : World Scientific, 2019. | Series: Primers in electronics and computer science ; volume 4 | Includes bibliographical references and index.

Identifiers: LCCN 2018056450 | ISBN 9781786346759 (hc : alk. paper)

Subjects: LCSH: Algorithms--Study and teaching.

Classification: LCC QA9.58 .V47 2019 | DDC 518/.1--dc23

LC record available at https://lccn.loc.gov/2018056450

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library.

Copyright 2019 by World Scientific Publishing Europe Ltd.

All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher.

For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher.

For any available supplementary material, please visit

https://www.worldscientific.com/worldscibooks/10.1142/Q0201#t=suppl

Desk Editors: Aanand Jayaraman/Jennifer Brough/Shi Ying Koe

Typeset by Stallion Press

Email:

Printed in Singapore

To the memory of my Parents

Lekh Raj Vermani

Informally speaking, an algorithm is a well-defined set of instructions or rules for solving a given problem. An algorithm accepts a value or a set of values as input and as the instructions are followed in a logical fashion, there results a value or a set of values as the final solution. The value or the set of values finally arrived at is called the output. Another important feature of an algorithm is that it must terminate in a finite number of steps. Euclids division algorithm is a most elementary algorithm which leads, besides many other things, to the greatest common divisor of two integers not both zero. Algorithms form an integral part of mathematics for solving problems in combinatorial mathematics. With the advent of computers, algorithms have become an integral and a very important part of theoretical computer science. For solving any problem simple or complex on computers, a programmer has to be extremely well versed in algorithms as he is the one who has to convert an algorithm, which may normally be written in simple English language, into computer program, i.e., he has to convert the algorithm into a language understood by the machine on which the problem is to be solved. In this text book, we are not concerned with programs written into machine language but will be content only with various algorithms. The number of recursive steps involved in the algorithm gives an estimate of time taken on the machine for solving a problem and is called the time complexity of the algorithm. How much memory of the machine is going to be involved is called the space complexity of the algorithm. However, in this book, the main concern is with time complexity and space complexity is not considered.

The design and analysis of algorithms today forms one of the core areas within computer science. This is clear from the fact that one to two one semester courses form a compulsory part of the study leading to a degree in computer science, computer engineering and information technology of almost every university.

The text begins with elementary sorting algorithms such as bubble sort, insertion sort, selection sort and quick sort, asymptotic notations are then introduced and are discussed at length. We then discuss the coloring problem and the n-queen problem by comprehensive method known as backtracking. As part of the divide and conquer approach the max-min problem and Strassens matrix multiplication algorithm are discussed. Job sequencing problem and Huffman code are studied as part of greedy algorithms. Matrix chain multiplication, multistage graphs and optimal binary search trees are discussed as part of dynamic programming. Among graph algorithms discussed are breadth first search, depth first search, Prims algorithm, Kruskals algorithm, Dijkstras algorithm and BellmanFord algorithm for single source shortest paths and FloydWarshall algorithm and Johnsons algorithm for all pairs shortest paths. Then flow networks, polynomial multiplication, FFT and DFT are discussed. The RabinKarp algorithm and KnuthMorrisPratt algorithm are discussed for string matching. Some other sorting networks are then discussed. Most problems we come across can, in general, be solved in polynomial time but not all. There may be problems which may need exponential time for their completion. Problems are classified as P, NP and NP-complete. The last chapter is devoted to study NP-completeness.

In the choice of topics discussed in the book we were guided by the course contents of the relevant paper(s) in computer science, computer engineering and information technology of some universities in the region. The relevance of the topics chosen is also evident from the fact that eight of these are among the 12 topics covered (may be at a much advanced level) in the 4 week courses (48 hours per week) as part of Algorithms Specialization Course of the Stanford University.

Our effort has been to present the material at an elementary level and in an easy to read and understand manner. In fact this has been our chief concern throughout. For the purpose, several solved examples have been given some as motivation for a topic and others as applications. Some exercises for the student to solve in order to further test the understanding of the subject are given. Maturity in logical mathematical reasoning including the principle of mathematical induction and knowledge of elementary algebra (not groups, rings and fields), some graph theory is required.