Problem Solving in Data Structures & Algorithms Using C

Problem Solving in

Data Structures &

Algorithms

Using C

First Edition

By Hemant Jain

Book Title: Problems Solving in Data Structures & Algorithms Using C

Book Author: Hemant Jain

Published by Hemant Jain

HIG 4, Samarth Tower, Sarvadharm, D Sector, Bhopal, India, Pin Code:

462042

Published in Bhopal, India

This edition published March 2017

Copyright © Hemant Jain 2017. All Right Reserved.

Hemant Jain asserts the moral right to be identified as the author of this

work.

All rights reserved. No part of this publication may be reproduced, stored

in or introduced into a retrieval system, or transmitted, in any form, or by

any means (electrical, mechanical, photocopying, recording or otherwise)

without the prior written permission of the author, except in the case of

very brief quotations embodied in critical reviews and certain other non￾commercial uses permitted by copyright law. Any person who does any

unauthorized act in relation to this publication may be liable to criminal

prosecution and civil claims for damages.

ACKNOWLEDGEMENT

The author is very grateful to GOD ALMIGHTY for his grace and blessing.

Deepest gratitude for the help and support of my brother Dr. Sumant Jain.

This book would not have been possible without the support and

encouragement he provided.

I would like to express profound gratitude to my guide/ my friend Naveen

Kaushik for his invaluable encouragement, supervision and useful

suggestion throughout this book writing work. His support and continuous

guidance enable me to complete my work successfully.

Finally yet importantly, I am thankful to Love Singhal, Anil Berry and

Others who helped me directly or indirectly in completing this book.

Hemant Jain

TABLE OF CONTENTS

TABLE OFCONTENTS

CHAPTER 0: HOW TO USE THIS BOOK

WHAT THIS BOOK IS ABOUT

PREPARATION PLANS

SUMMARY

CHAPTER 1: INTRODUCTION - PROGRAMMING OVERVIEW

INTRODUCTION

VARIABLE

POINTERS

ARRAY

TWO DIMENSIONALARRAY

ARRAY INTERVIEW QUESTIONS

STRUCTURE

POINTER TO STRUCTURE

DYNAMIC MEMORY ALLOCATION

FUNCTION

CONCEPT OF STACK

SYSTEM STACK AND FUNCTION CALLS

PARAMETER PASSING, CALLBY VALUE

PARAMETER PASSING, CALLBY REFERENCE

RECURSIVE FUNCTION

EXERCISES

CHAPTER 2: ALGORITHMS ANALYSIS

INTRODUCTION

ASYMPTOTIC ANALYSIS

BIG-O NOTATION

OMEGA-Ω NOTATION

THETA-Θ NOTATION

COMPLEXITY ANALYSIS OF ALGORITHMS

TIME COMPLEXITY ORDER

DERIVING THE RUNTIME FUNCTION OF AN ALGORITHM

TIME COMPLEXITY EXAMPLES

MASTER THEOREM

MODIFIED MASTER THEOREM

EXERCISE

CHAPTER 3: APPROACH TO SOLVE ALGORITHM DESIGN PROBLEMS

INTRODUCTION

CONSTRAINTS

IDEA GENERATION

COMPLEXITIES

CODING

TESTING

EXAMPLE

SUMMARY

CHAPTER 4: ABSTRACT DATA TYPE

ABSTRACT DATA TYPE (ADT)

DATA-STRUCTURE

ARRAY

LINKED LIST

STACK

QUEUE

TREES

BINARY TREE

BINARY SEARCH TREES (BST)

PRIORITY QUEUE (HEAP)

HASH-TABLE

DICTIONARY / SYMBOLTABLE

GRAPHS

GRAPH ALGORITHMS

SORTING ALGORITHMS

COUNTING SORT

END NOTE

CHAPTER 5: SEARCHING

INTRODUCTION

WHY SEARCHING?

DIFFERENT SEARCHING ALGORITHMS

LINEAR SEARCH – UNSORTED INPUT

LINEAR SEARCH – SORTED

BINARY SEARCH

STRING SEARCHING ALGORITHMS

HASHING AND SYMBOLTABLES

HOW SORTING IS USEFULIN SELECTION ALGORITHM?

PROBLEMS IN SEARCHING

EXERCISE

CHAPTER 6: SORTING

INTRODUCTION

TYPE OF SORTING

BUBBLE-SORT

MODIFIED (IMPROVED) BUBBLE-SORT

INSERTION-SORT

SELECTION-SORT

MERGE-SORT

QUICK-SORT

QUICK SELECT

BUCKET SORT

GENERALIZED BUCKET SORT

HEAP-SORT

TREE SORTING

EXTERNALSORT (EXTERNALMERGE-SORT)

COMPARISONS OF THE VARIOUS SORTING ALGORITHMS.

SELECTION OF BEST SORTING ALGORITHM

EXERCISE

CHAPTER 7: LINKED LIST

INTRODUCTION

LINKED LIST

TYPES OF LINKED LIST

SINGLY LINKED LIST

DOUBLY LINKED LIST

CIRCULAR LINKED LIST

DOUBLY CIRCULAR LIST

EXERCISE

CHAPTER 8: STACK

INTRODUCTION

THE STACK ABSTRACT DATA TYPE

STACK USING ARRAY (MACRO)

STACK USING ARRAY (DYNAMIC MEMORY)

STACK USING ARRAY (GROWING CAPACITY IMPLEMENTATION)

STACK USING ARRAY (GROWING-REDUCING CAPACITY IMPLEMENTATION)

STACK USING LINKED LIST

PROBLEMS IN STACK

PROS AND CONS OF ARRAY AND LINKED LIST IMPLEMENTATION OF STACK.

USES OF STACK

EXERCISE

CHAPTER 9: QUEUE

INTRODUCTION

THE QUEUE ABSTRACT DATA TYPE

QUEUE USING ARRAY

QUEUE USING LINKED LIST

PROBLEMS IN QUEUE

EXERCISE

CHAPTER 10: TREE

INTRODUCTION

TERMINOLOGY IN TREE

BINARY TREE

TYPES OF BINARY TREES

PROBLEMS IN BINARY TREE

BINARY SEARCH TREE (BST)

PROBLEMS IN BINARY SEARCH TREE (BST)

EXERCISE

CHAPTER 11: PRIORITYQUEUE

INTRODUCTION

TYPES OF HEAP

HEAP ADT OPERATIONS

OPERATION ON HEAP

HEAP-SORT

USES OF HEAP

PROBLEMS IN HEAP

EXERCISE

CHAPTER 12: HASH-TABLE

INTRODUCTION

HASH-TABLE

HASHING WITH OPEN ADDRESSING

HASHING WITH SEPARATE-CHAINING

PROBLEMS IN HASHING

EXERCISE

CHAPTER 13: GRAPHS

INTRODUCTION

GRAPH REPRESENTATION

ADJACENCY MATRIX

ADJACENCY LIST

GRAPH TRAVERSALS

DEPTH FIRST TRAVERSAL

BREADTH FIRST TRAVERSAL

PROBLEMS IN GRAPH

DIRECTED ACYCLIC GRAPH

TOPOLOGICALSORT

MINIMUM SPANNING TREES (MST)

SHORTEST PATH ALGORITHMS IN GRAPH

EXERCISE

CHAPTER 14: STRING ALGORITHMS

INTRODUCTION

STRING MATCHING

DICTIONARY / SYMBOLTABLE

PROBLEMS IN STRING

MEMMOVE FUNCTION

EXERCISE

CHAPTER 15: ALGORITHM DESIGN TECHNIQUES

INTRODUCTION

BRUTE FORCE ALGORITHM

GREEDY ALGORITHM

DIVIDE-AND-CONQUER, DECREASE-AND-CONQUER

DYNAMIC PROGRAMMING

REDUCTION / TRANSFORM-AND-CONQUER

BACKTRACKING

BRANCH-AND-BOUND

A* ALGORITHM

CONCLUSION

CHAPTER 16: BRUTE FORCE ALGORITHM

INTRODUCTION

PROBLEMS IN BRUTE FORCE ALGORITHM

CONCLUSION

CHAPTER 17: GREEDYALGORITHM

INTRODUCTION

PROBLEMS ON GREEDY ALGORITHM

CHAPTER 18: DIVIDE-AND-CONQUER, DECREASE-AND-CONQUER

INTRODUCTION

GENERALDIVIDE-AND-CONQUER RECURRENCE

MASTER THEOREM

PROBLEMS ON DIVIDE-AND-CONQUER ALGORITHM

CHAPTER 19: DYNAMIC PROGRAMMING

INTRODUCTION

PROBLEMS ON DYNAMIC PROGRAMMING ALGORITHM

CHAPTER 20: BACKTRACKING AND BRANCH-AND-BOUND

INTRODUCTION

PROBLEMS ON BACKTRACKING ALGORITHM

CHAPTER 21: COMPLEXITYTHEORYAND NP COMPLETENESS

INTRODUCTION

DECISION PROBLEM

COMPLEXITY CLASSES

CLASS P PROBLEMS

CLASS NP PROBLEMS

CLASS CO-NP

NP–HARD:

NP–COMPLETE PROBLEMS

REDUCTION

END NOTE

CHAPTER 22: INTERVIEW STRATEGY

INTRODUCTION

RESUME

NONTECHNICALQUESTIONS

TECHNICALQUESTIONS

CHAPTER 23: SYSTEM DESIGN

SYSTEM DESIGN

SYSTEM DESIGN PROCESS

SCALABILITY THEORY

DESIGN SIMPLIFIED FACEBOOK

DESIGN FACEBOOK FRIENDS SUGGESTION FUNCTION

DESIGN A SHORTENING SERVICE LIKE BITLY

STOCK QUERY SERVER

DESIGN A BASIC SEARCH ENGINE DATABASE

DESIGN A BASIC SEARCH ENGINE CACHING

DUPLICATE INTEGER IN MILLIONS OF DOCUMENTS

ZOMATO

YOUTUBE

DESIGN IRCTC

ALARM CLOCK

DESIGN FOR ELEVATOR OF A BUILDING

VALET PARKING SYSTEM

OO DESIGN FOR A MCDONALDS SHOP

OBJECT ORIENTED DESIGN FOR A RESTAURANT

OBJECT ORIENTED DESIGN FOR A LIBRARY SYSTEM

SUGGEST A SHORTEST PATH

EXERCISE

APPENDIX

APPENDIX A

CHAPTER 0: HOW TO USE THIS BOOK