Problem Solving in Data Structures & Algorithms Using C++ First Edition By Hemant Jain Problems Solving in Data Structures & Algorithms Using C++ HEMANT JAIN Copyright © 2016 by HEMANT JAIN. All Right Reserved. No part of this publication may be reproduced, distributed, or transmitted in any form or by any means, including photocopying, recording, or other electronic or mechanical methods, or by any information storage and retrieval system 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. 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. Last but not least, I am thankful to Anil Berry and Others who helped me directly or indirectly in completing this book. Hemant Jain TABLE OF CONTENTS TABLE OF CONTENTS TABLE OF CONTENTS CHAPTER 0: HOW TO USE THIS BOOK WHAT THIS BOOK IS ABOUT PREPARATION PLANS SUMMARY CHAPTER 1: INTRODUCTION - PROGRAMMING OVERVIEW INTRODUCTION FIRST C++ PROGRAM OBJECT VARIABLE PARAMETER PASSING, CALL BY VALUE PARAMETER PASSING, CALL BY REFERENCE PARAMETER PASSING, CALL BY POINTER KINDS OF VARIABLES METHODS ACCESS MODIFIERS ABSTRACT CLASS RELATIONSHIP GENERAL PROTOTYPE OF A CLASS NESTED CLASS ENUMS CONSTANTS CONDITIONS AND LOOPS ARRAY VECTOR ARRAY INTERVIEW QUESTIONS CONCEPT OF STACK SYSTEM STACK AND METHOD CALLS 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 & C++ COLLECTIONS ABSTRACT DATA TYPE (ADT) DATA-STRUCTURE C++ COLLECTION FRAMEWORK ARRAY LINKED LIST STACK QUEUE TREES BINARY TREE BINARY SEARCH TREES (BST) PRIORITY QUEUE (HEAP) HASH-TABLE DICTIONARY / SYMBOL TABLE 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 SYMBOL TABLES HOW SORTING IS USEFUL IN 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 EXTERNAL SORT (EXTERNAL MERGE-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 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: PRIORITY QUEUE 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 COUNT MAP 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 TOPOLOGICAL SORT MINIMUM SPANNING TREES (MST) SHORTEST PATH ALGORITHMS IN GRAPH EXERCISE CHAPTER 14: STRING ALGORITHMS INTRODUCTION STRING MATCHING DICTIONARY / SYMBOL TABLE PROBLEMS IN STRING 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: GREEDY ALGORITHM INTRODUCTION PROBLEMS ON GREEDY ALGORITHM CHAPTER 18: DIVIDE-AND-CONQUER, DECREASE-AND-CONQUER INTRODUCTION GENERAL DIVIDE-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