3333399
3333 3333333338888899993333
The Magical Guide to
,k
Algorithm Analysis and
Design
Rosina S Khan
Dedicated to:
1
Dedicated to You,
The Valued Reader
2
Copyright Information
Copyright © 2024 by Rosina S Khan. All rights reserved. No part(s) of this eBook may be used or reproduced in any form whatsoever, without written permission by the author.
https://rosinaskhan.weebly.com
3
Table of Contents
Preface ................................................................................. 8
C H A P T E R 1 .................................................................10
Introduction ........................................................................ 10
1. Introduction to Algorithms ........................................................... 10
1.1 Algorithms as Opposed to Programs ........................................... 10
1.2 Fundamental Questions About Algorithms .................................. 11
C H A P T E R 2 .................................................................12
Data Structures ................................................................... 12
2. Introduction ............................................................................... 12
2.1 Basic Terminology ..................................................................... 12
2.2 The Need for Data Structure ...................................................... 12
2.3 The Goals of Data Structure ...................................................... 13
2.4 Steps in Selecting a Data Structure ............................................ 13
2.5 Classification of Data Structures ................................................. 13
2.6 Primitive Data Structure ............................................................ 14
2.7 Non-Primitive Data Structures .................................................... 14
2.8 Operations on Data Structures ................................................... 19
2.9 Abstract Data Type ................................................................... 19
2.10 Advantage using Abstract Data Trees ....................................... 19
C H A P T E R 3 .................................................................21
Why Algorithms? ................................................................. 21
3. Defining an Algorithm ................................................................. 21
3.1 Features of an Algorithm ........................................................... 21
4
3.2 Advantages and Disadvantages of an Algorithm .......................... 22
3.3 Different Approaches to Designing an Algorithm ......................... 22
3.4 How to Write an Algorithm ........................................................ 22
3.5 Algorithmic Complexity .............................................................. 23
3.6 Space Complexity...................................................................... 24
3.7 Time Complexity ....................................................................... 24
3.8 Analysis of Algorithms ............................................................... 25
3.9 Mathematical Notations ............................................................. 26
C H A P T E R 4 .................................................................33
Searching ............................................................................ 33
4. Introduction to Searching Algorithm ............................................. 33
4.1 Specification of the Search Problem ........................................... 33
4.2 A Simple Algorithm on Linear Search .......................................... 34
4.3 A More Efficient algorithm: Binary Search ................................... 34
C H A P T E R 5 .................................................................37
Trees .................................................................................. 37
5. Introduction to Trees .................................................................. 37
5.1 Specification of Trees ................................................................ 37
5.2 Quadtrees ................................................................................ 38
5.3 Binary Trees ............................................................................. 40
C H A P T E R 6 .................................................................46
Binary Search Tree .............................................................. 46
6. Definition ................................................................................... 46
6.1 Building Binary Search Trees ..................................................... 46
6.2 Searching a Binary Search Tree ................................................. 47
6.3 Time Complexity of Insertion and Search ................................... 48
5
6.4 Deleting Nodes from a Binary Search Tree.................................. 48
6.5 Checking Whether a Binary Tree Is a Binary Search Tree ............ 51
6.6 Sorting Using Binary Search Trees ............................................. 51
6.7 Balancing Binary Search Trees ................................................... 52
6.8 B-trees ..................................................................................... 53
C H A P T E R 7 .................................................................55
Priority Queues and Heap Trees ........................................... 55
7. Trees Stored in Arrays................................................................. 55
7.1 Priority Queues and Binary Heap Trees ...................................... 56
7.2 Basic Operations on Binary Heap Trees .................................... 58
7.3 Inserting a New Heap Tree Node ............................................... 59
7.4 Deleting a Heap Tree Node ........................................................ 60
7.5 Building a New Heap Tree from Scratch ..................................... 61
7.6 Merging Binary Heap Trees ........................................................ 64
C H A P T E R 8 .................................................................66
Sorting ................................................................................ 66
8. Introduction to Sorting ................................................................ 66
8.1 Sorting Techniques ................................................................... 66
C H A P T E R 9 .................................................................88
Graphs ................................................................................ 88
9. Introduction to Graphs ................................................................ 88
9.1 Basic Concepts of Graphs .......................................................... 88
9.2 Types of Graphs ....................................................................... 90
9.3 Representing Graphs ................................................................. 92
9.4 Operations on Graphs ............................................................... 95
9.5 Graph Traversals ....................................................................... 97
6
C H A P T E R 10 ............................................................ 101
Graph Algorithms ............................................................... 101
10. Spanning Tree .........................................................................101
10.1 The Minimum Spanning Tree ..................................................102
10.2 Graph Algorithms ...................................................................103
C H A P T E R 11 ............................................................ 110
Algorithm Design Techniques ............................................. 110
11. Introduction ............................................................................110
11.1 What Are Algorithm Design Techniques? .................................110
11.2. Objectives ............................................................................111
11.3 Brute Force Method (BF) ........................................................111
11.4 Divide and Conquer Strategy (D&Q) ........................................111
11.5 Backtracking (BT) ..................................................................113
11.6 Dynamic programming (DP) ....................................................115
11.7 Greedy Methods (GM) ............................................................117
11.8 Comparisons Among the Algorithmic Techniques .....................119
11.9 Discussion of Algorithmic Complexities for Particular Problems
Using Algorithm Design Techniques ................................................122
About the Author ............................................................... 126
Valuable Free Resources .................................................... 127
7
