COVER TABLE OF CONTENTS HOW TO USE THIS BOOK WHAT THIS BOOK IS ABOUT PREPARATION PLANS CODE DOWNLOADS SUMMARY 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 ARRAY BASED QUESTIONS RECURSIVE FUNCTION EXERCISE APPROACH TO SOLVE ALGORITHM DESIGN PROBLEMS INTRODUCTION CONSTRAINTS IDEA GENERATION COMPLEXITIES CODING TESTING EXAMPLE SUMMARY ABSTRACT DATA TYPE & C# COLLECTIONS ABSTRACT DATA TYPE (ADT) DATA-STRUCTURE C# COLLECTION FRAMEWORK ARRAY LINKED LIST STACK QUEUE TREE BINARY TREE BINARY SEARCH TREES (BST) PRIORITY QUEUE (HEAP) HASH-TABLE CHOOSING THE RIGHT COLLECTION CLASS DICTIONARY / SYMBOL TABLE GRAPHS GRAPH ALGORITHMS SORTING ALGORITHMS END NOTE 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) STABLE SORTING COMPARISONS OF THE VARIOUS SORTING ALGORITHMS SELECTION OF BEST SORTING ALGORITHM PROBLEMS BASED ON SORTING EXERCISE 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 LINKED LIST INTRODUCTION LINKED LIST TYPES OF LINKED LIST SINGLY LINKED LIST DOUBLY LINKED LIST CIRCULAR LINKED LIST DOUBLY CIRCULAR LIST EXERCISE STACK INTRODUCTION THE STACK ABSTRACT DATA TYPE STACK USING ARRAY STACK USING ARRAY WITH MEMORY MANAGEMENT STACK USING LINKED LIST SYSTEM STACK AND METHOD CALLS PROBLEMS IN STACK USES OF STACK EXERCISE QUEUE INTRODUCTION THE QUEUE ABSTRACT DATA TYPE QUEUE USING ARRAY QUEUE USING LINKED LIST PROBLEMS IN QUEUE EXERCISE 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) SEGMENT TREE AVL TREES RED-BLACK TREE SPLAY TREE B-TREE B+ TREE B* TREE EXERCISE PRIORITY QUEUE/ HEAPS INTRODUCTION TYPES OF HEAP HEAP ADT OPERATIONS OPERATION ON HEAP HEAP-SORT PRIORITYQUEUE / GENERIC HEAP IMPLEMENTATION USES OF HEAP PROBLEMS IN HEAP EXERCISE HASH-TABLE INTRODUCTION HASH-TABLE HASHING WITH SEPARATE CHAINING PROBLEMS IN HASHING EXERCISE GRAPHS INTRODUCTION GRAPH TERMINOLOGY GRAPH REPRESENTATION GRAPH TRAVERSALS DEPTH FIRST TRAVERSAL BREADTH FIRST TRAVERSAL USES OF BFS AND DFS DFS & BFS BASED PROBLEMS MINIMUM SPANNING TREES (MST) SHORTEST PATH ALGORITHMS IN GRAPH HAMILTONIAN PATH AND HAMILTONIAN CIRCUIT EULER PATH AND EULER CIRCUIT TRAVELLING SALESMAN PROBLEM (TSP) EXERCISE STRING ALGORITHMS INTRODUCTION STRING MATCHING DICTIONARY / SYMBOL TABLE PROBLEMS IN STRING EXERCISE 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 BRUTE FORCE ALGORITHM INTRODUCTION PROBLEMS IN BRUTE FORCE ALGORITHM CONCLUSION GREEDY ALGORITHM INTRODUCTION PROBLEMS ON GREEDY ALGORITHM DIVIDE-AND-CONQUER, DECREASE-AND-CONQUER INTRODUCTION GENERAL DIVIDE-AND-CONQUER RECURRENCE PROBLEMS ON DIVIDE-AND-CONQUER ALGORITHM DYNAMIC PROGRAMMING INTRODUCTION PROBLEMS ON DYNAMIC PROGRAMMING ALGORITHM BACKTRACKING INTRODUCTION PROBLEMS ON BACKTRACKING ALGORITHM COMPLEXITY THEORY INTRODUCTION DECISION PROBLEM COMPLEXITY CLASSES CLASS P PROBLEMS CLASS NP PROBLEMS CLASS CO-NP NP–HARD: NP–COMPLETE PROBLEMS REDUCTION END NOTE APPENDIX APPENDIX A
