Enables readers to learn how to design and implement algorithms for efficient and secure smart technologies
Algorithms for Smart World Technologies explains the fundamentals of key algorithms and their application in a variety of use cases, covering the factors, assumptions, and models essential for the design of a real-world algorithm and discussing the importance of advanced algorithms in the use of modern world technologies such as AI, IoT, and Blockchain.
Each chapter is written to provide a self-contained treatment of one major topic. Collectively, the chapters have been designed and carefully integrated to be entirely complementary with respect to definitions, terminology, and notation. Chapters are divided into three parts—complexities, paradigms, and recent applications—and at the beginning of each part, a detailed introduction explaining each subject area is provided. The foundational subjects are supported by end-of-chapter exercises and case studies, while the application-focused chapters are supported by projects to give worked experience.
Written by two highly qualified authors in academia, sample topics covered in Algorithms for Smart World Technologies include:
- Complexities, including complex systems and algorithms, measuring efficiency, types of systems, and types of complexities
- Ethics bounds, including algorithms ethics maps, algorithmic traceability, social ethics, environmental ethics, and parameters and thresholds
- Algorithmic paradigms, including the design of an algorithm, the divide and conquer algorithm, backtracking, exhaustive search, solvability, and reducibility
- Intelligent search algorithms, including solution space, uninformed, and informed search algorithms, evolutionary algorithms, and nature-inspired algorithms
- Smart transportation, including scheduling algorithms for vehicular traffic and opportunistic communication for VANET
Written for developers and domain experts who want to explore the opportunities and challenges of designing and developing algorithms and protocols for Smart-world problems, Algorithms for Smart World Technologies is an authoritative resource on the topic that provides both foundational knowledge and guidance on practical applications.
Table of Contents:
Foreword xv
Preface xvii
Acknowledgments xix
Acronyms xxi
Introduction xxv
Part I Complexities of Smart Algorithms 1
1 Introduction to Complexities 3
1.1 Complex Systems and Algorithms 4
1.2 Complex Systems 4
1.2.1 Key Features of Complex Systems 4
1.2.2 Examples of Complex Systems 5
1.2.3 The Role of Algorithms in Complex Systems 5
1.2.4 Modeling and Simulation 5
1.2.5 Data Analysis 5
1.2.6 Optimization 5
1.2.7 Machine Learning 5
1.2.8 Challenges and Opportunities in Algorithmic Design 5
1.2.9 Future Directions 5
1.3 Efficiency Metrics for Complex Systems 6
1.3.1 Challenges in Measuring Efficiency 6
1.3.2 Techniques for Measuring Efficiency 7
1.3.3 Defining Efficiency in Complex Systems: A Holistic Approach 7
1.3.4 The Path Forward: Toward a Unified Framework 8
1.4 Applications of Complexity 8
1.4.1 Complexity in Practice 8
1.4.2 Complexity Management 8
1.4.3 Complexity Economics 8
1.4.4 Complexity and Education 9
1.4.5 Complexity and Modeling 9
1.4.6 Complexity and Chaos Theory 9
1.4.7 Complexity and Network Science 9
1.4.8 Complexity and Future Research Directions 10
1.5 Types of Complexities 10
1.6 Exercises 11
2 Computational Complexity 13
2.1 Computability 13
2.2 Computational Models 15
2.3 Complexity Classes 16
2.4 Probabilistic Complexity 17
2.4.1 The BPP Complexity Class 17
2.4.2 Examples of Probabilistic Complexity 17
2.4.3 BPP: Efficient Probabilistic Computation 17
2.4.4 Future Directions in Probabilistic Complexity 18
2.5 Quantum Complexity 18
2.5.1 BQP: Power and Intrigue 18
2.5.2 The P, NP, and BQP 19
2.5.3 BQP: Efficient Quantum Computation 19
2.5.4 Future Directions in Quantum Complexity 19
2.6 Exercises 20
3 Communication Complexity 23
3.1 Deterministic Communication 24
3.2 Deterministic Communication Complexity 24
3.3 Nondeterministic Communication 26
3.4 Nondeterministic Communication Complexity 26
3.5 Randomized Communication Complexity 27
3.5.1 Approximate Rank 28
3.6 Exercises 28
4 Data Complexity 31
4.1 Algorithmic Information Theory 32
4.1.1 Philosophy of Mathematics: Randomness Within Mathematics 32
4.1.2 Philosophy of Probability: Understanding Randomness of Individual Sequences 32
4.2 Occam’s Razor and Inductive Inference 33
4.3 Philosophy of Information 33
4.4 Lessons for the Philosophy of Information 34
4.5 Kolmogorov Complexity: Measuring Randomness 35
4.5.1 Defining Descriptions and Complexity 35
4.5.2 Compression and Invariance 35
4.5.3 Randomness and Compressibility 36
4.5.4 Connection to Gödel’s Theorem 36
4.6 VC Dimension: Measuring Model Complexity 36
4.6.1 VC Dimension of Set Families 36
4.6.2 VC Dimension of Classification Models 36
4.7 Rademacher Complexity 37
4.7.1 Rademacher Complexity of a Set 37
4.7.2 Rademacher Complexity of a Function Class 37
4.7.3 Example 37
4.7.4 Generalization Bound 38
4.7.5 Using Rademacher Complexity 38
4.7.6 Representativeness of a Sample 38
4.8 Exercises 38
5 Risk Measures 41
5.1 Addressing Algorithmic Bias 41
5.2 Risk Measures 42
5.3 Algorithmic Fairness Measures 43
5.4 Risks in Algorithmic Monoculture 44
5.5 Green Efficiency 45
5.5.1 Green Internet Technologies 46
5.5.2 Green RFID Tags 46
5.5.3 Green Wireless Sensor Networks 47
5.5.4 Green Cloud Computing 47
5.5.5 Green Data Centers 47
5.6 Conclusion 47
5.7 Exercises 47
6 Ethics and Algorithmic Boundaries 49
6.1 Introduction 49
6.2 Objectives 50
6.3 Algorithmic Decision-making 50
6.3.1 Background 50
6.3.2 Algorithmic Decision-making in Public Discourse 51
6.3.3 Ethical Challenges in Algorithmic Decision-making 51
6.3.4 ml and Autonomous Decision-making 51
6.4 Algorithmic Morality 52
6.4.1 Artificial Life and Emerging Ethical Behavior 52
6.4.2 Unbiased Learning Machines 52
6.4.3 Associative Learning and Moral Training 53
6.4.4 Ethical Risks of Learning Systems 53
6.5 Ethics as a Service 53
6.5.1 Service Model Analogies for Ethical Governance 53
6.5.2 Implementing the Ethics-as-a-Service Model 54
6.5.3 Case Study: Digital Catapult Pilot 54
6.5.4 Future Research Directions 54
6.6 Current Discussions and Future Research Directions 54
6.7 Conclusion 55
6.8 Exercises 55
Part II Algorithmic Paradigms for Smart World Technologies 57
7 Introduction to Paradigms of Smart Algorithms 59
7.1 Introduction to Smart Paradigms 60
7.2 Important Algorithms in Smart Paradigms 60
7.2.1 ML Algorithms 60
7.2.2 Optimization Algorithms 60
7.2.3 IoT and Distributed Algorithms 61
7.3 Roadmap for Future Advancements 61
7.3.1 Enhancing Scalability 61
7.3.2 Data Privacy and Security 61
7.3.3 Autonomous and Intelligent Decision-making 61
7.3.4 Green Computing and Energy Efficiency 61
7.4 Conclusion 62
8 Optimization Algorithms 63
8.1 Constrained Optimization: Optimization with Limitations 63
8.2 Convex Optimization: Finding the Global Minimum 64
8.3 Solving Linear Equations 65
8.3.1 Steepest Descent: Gradient-based Minimization 66
8.3.2 Improving Convergence 66
8.3.3 Preconditioning with Trees 67
8.4 Linear Programming Duality 67
8.4.1 Complementary Slackness 68
8.4.2 Congestion Minimization 69
8.4.3 Maximum Weight Matching 69
8.4.4 Games and Strategic Solutions 69
8.4.5 The Minimax Theorem 70
8.5 Network Problems 72
8.5.1 Key Definitions 72
8.5.2 The Minimum-cost Flow Problem 72
8.5.3 The Transportation Problem 73
8.5.4 The Maximum Flow Problem 79
8.6 Exercises 82
9 Decision-making Algorithms 85
9.1 Markov Decision Process 85
9.1.1 Discrete MDPs 86
9.1.2 Nondiscrete MDPs: General Constructions 90
9.1.3 Discrete State MDPs 92
9.1.4 Classical Borel MDPs 92
9.1.5 Assumptions for Borel MDPs 93
9.1.6 Universally Measurable Borel MDPs 94
9.1.7 Assumptions for Universally Measurable MDPs 94
9.2 Reinforcement Learning 95
9.3 Value Iteration 96
9.4 Q-learning 97
9.5 TD Learning 98
9.6 Exercises 99
10 Prediction Algorithms 101
10.1 Regression 101
10.1.1 Least Squares and Nearest-neighbor Methods 101
10.1.2 Prediction Theory 102
10.1.3 Curse of Dimensionality 102
10.1.4 Learning as Function Approximation 102
10.1.5 Key Formulas 102
10.1.6 Linear Regression and Least Squares 103
10.1.7 Variable Selection 104
10.1.8 Best Subset Selection and Forward and Backward Stepwise Selection 104
10.1.9 Smoothly Clipped Absolute Deviation 106
10.1.10 Consistency and Oracle Property 106
10.1.11 Selecting a Group of Variables 107
10.1.12 Least Squares, Penalized Likelihood, and Bayesian Inference 107
10.2 Classifications 108
10.2.1 Issues with Linear Regression Approach 108
10.2.2 Linear Discriminant Analysis 108
10.2.3 Reduced-rank LDA 109
10.2.4 Comparison Between Logistic Regression and LDA 110
10.2.5 Piecewise Polynomial Functions 111
10.2.6 Smoothing Splines 111
10.2.7 Choosing Smoothing Parameters 112
10.2 8 Hilbert Space 113
10.2.9 Generalized Additive Models 114
10.2.10 Fitting GAMs 115
10.2.11 Illustration: Predicting Email Spam 115
10.2.12 Tree-based Regression and Classification 116
10.2.13 Regression Trees 116
10.2.14 Classification Trees 116
10.2.15 Challenges in Tree-based Methods 117
10.2.16 Illustrative Example: Spam Prediction 117
10.2.17 Hierarchical Mixtures of Experts and Missing Values 118
10.2.18 One-dimensional Kernel Smoothers 118
10.2.19 Considerations in Kernel Smoothing 119
10.2.20 Local Regression and Local Likelihood Method 119
10.2.21 Selecting the Width of the Kernel 120
10.2.22 Structured Kernels and Local Likelihood Methods 120
10.2.23 Kernel Density Estimation 120
10.2.24 Application to Classification 121
10.2.25 Mixture Models 122
10.3 Model Complexity 122
10.3.1 Bia-variance Decomposition 123
10.3.2 Estimate the Errors 124
10.3.3 Cross-validation 125
10.3.4 Bootstrap 126
10.3.5 The EM Algorithm 126
10.3.6 Two Other Interpretations of EM Algorithm 127
10.4 Bayesian Algorithms 129
10.4.1 Variational Bayes 129
10.4.2 The Key Identity 129
10.4.3 Variational Inference 130
10.4.4 Improvements and Variants 131
10.4.5 Approximate Bayesian Computation 131
10.4.6 The Discrete Version 131
10.4.7 The Continuous Version 131
10.4.8 Issues 132
10.5 Neural Networks 132
10.5.1 Fitting Neural Networks 132
10.5.2 Some Issues with Neural Networks 133
10.6 Support Vector Machines 134
10.6.1 Separating Hyperplane 134
10.6.2 Support Vectors 134
10.7 Cluster Analysis 135
10.7.1 Clustering Algorithms: Combinatorial 136
10.7.2 Clustering Algorithms: k-means 136
10.7.3 Clustering Algorithms: Hierarchical Clustering 136
10.7.4 Principal Components, Curves, and Surfaces 137
10.7.5 Procrustes Transform and Shape Averaging 138
10.7.6 Factor Model and Independent Component Analysis 139
10.7.7 Independent Component Analysis 139
10.7.8 Principal Curve and Multidimensional Scaling 139
10.8 Graphical Models 140
10.8.1 False Discovery Rate 140
10.8.2 Markov Graphs and Gaussian Graphical Models 141
10.8.3 Undirected Graphs for Discrete Variables 142
10.8.4 Exponential Random Graphs 143
10.8.5 Eigen-statistics of Sample Covariance Matrices 143
10.8.6 Bulk Universality: Marchenko–Pastur Law (or Quartercircle Law) 143
10.8.7 Edge Universality: Tracy–Widom Law 144
10.9 Exercises 144
11 Secure Algorithms 147
11.1 Low-power Cryptography 148
11.2 Secret-key Cryptography 148
11.3 Public-key Cryptography 148
11.3.1 Key Exchange Protocol 149
11.3.2 Trapdoor Functions 150
11.3.3 md 5 154
11.3.4 Secure Sockets Layer 155
11.3.5 Blockchain 156
11.3.6 Digital Signature 157
11.4 Exercises 158
Part III Smart World Applications 161
12 Introduction to Smart World Applications 163
12.1 Interesting Applications 164
13 Smart Education 167
13.1 Examples of Smart Education Tools 167
13.2 Personalized Learning 168
13.2.1 Key Algorithms 168
13.2.2 Application Example 169
13.3 Intelligent Content Delivery 169
13.3.1 Key Algorithms 169
13.3.2 Application Example 170
13.4 Learning Analytics and Insights 170
13.4.1 Key Algorithms 170
13.4.2 Application Example 170
13.5 Data Analytics in Education 170
13.5.1 Key Algorithms 170
13.5.2 Application Example 171
13.6 AI Tutors and Assistants in Education 171
13.6.1 Key Algorithms 171
13.6.2 Application Example 171
13.7 Assessment and Feedback in Education 171
13.7.1 Key Algorithms 172
13.7.2 Application Example 172
13.8 Assessment and Feedback in Education 172
13.8.1 Key Algorithms 172
13.8.2 Application Example 172
13.9 Collaborative Learning 173
13.9.1 Key Algorithms 173
13.9.2 Application Example 173
13.10 Exercises 174
14 Smart World Algorithms in Healthcare 175
14.1 Patient Flow Scheduling and Capacity Planning 175
14.1.1 Queueing Theory 176
14.1.2 Simulation Algorithms 176
14.1.3 Linear Programming 176
14.2 Drug Packaging in the Healthcare Industry 177
14.2.1 Robotic Process Automation 177
14.2.2 Optical Character Recognition 177
14.2.3 Predictive Analytics 177
14.3 Data Security of Smart Healthcare 178
14.3.1 Encryption Algorithms 178
14.3.2 Blockchain Technology 178
14.3.3 Machine Learning for Anomaly Detection 178
14.4 Automated Nutrition Monitoring System 178
14.4.1 Dietary Assessment Algorithms 179
14.4.2 Recommendation Systems 179
14.4.3 Image Recognition 179
14.5 Exercises 179
15 Modern Approach Algorithms in Environmental and Energy I nfrastructure 181
15.1 Crowdsensing for Urban Air Pollution Monitoring 181
15.1.1 Algorithms 181
15.1.2 Application Example 182
15.2 Green Energy Scheduling for Demand Side Management 182
15.2.1 Algorithms 182
15.2.2 Application Example 183
15.3 Smart Grid 183
15.3.1 Application Example 184
15.4 Smart Waste Management Systems 184
15.4.1 Application Example 185
15.5 Drone Monitoring 185
15.5.1 Application Example 186
15.6 Exercises 187
16 Smart Agriculture 189
16.1 Precision Farming 189
16.1.1 Key Algorithms 190
16.1.2 Application Example 190
16.2 Soil Health Monitoring 191
16.2.1 Key Algorithms 191
16.2.2 Application Example 192
16.3 Irrigation Management 192
16.3.1 Application Example 193
16.4 Crop Yield Prediction 193
16.4.1 Key Algorithms 193
16.4.2 Application Example 194
16.5 Exercises 194
17 Smart Transportation 197
17.1 Smart Traffic Management 198
17.1.1 Key Algorithms and Applications 198
17.2 Intelligent Transportation Systems 199
17.2.1 Key Algorithms and Applications 199
17.3 Public Transportation 200
17.3.1 Key Algorithms and Applications 200
17.4 Smart Parking 201
17.4.1 Key Algorithms and Applications 201
17.5 Autonomous Vehicles 202
17.5.1 Key Algorithms and Applications 202
17.6 Infrastructure Monitoring and Maintenance 202
17.6.1 Key Algorithms 202
17.7 Electric and Connected Vehicles 203
17.7.1 Key Algorithms and Applications 203
17.8 Emergency Response 204
17.8.1 Key Algorithms and Applications 204
17.9 Exercises 204
18 Information Technology and Society 207
18.1 Introduction 207
18.2 Missing Person Identification 207
18.2.1 Key Algorithms 207
18.2.2 Applications 208
18.3 Social Contagions 208
18.3.1 Key Algorithms 208
18.3.2 Applications 208
18.4 Disease Propagation 208
18.4.1 Key Algorithms 208
18.4.2 Applications 208
18.5 Crime Monitoring 209
18.5.1 Key Algorithms 209
18.5.2 Applications 209
18.6 Exercises 209
19 Smart Government 211
19.1 E-government Services 211
19.1.1 Key Algorithms 211
19.1.2 Applications 212
19.2 Smart Utilities 212
19.2.1 Key Algorithms 212
19.2.2 Applications 213
19.3 Public Safety Enhancements 214
19.3.1 Key Algorithms 214
19.3.2 Applications 214
19.4 Environmental Monitoring 214
19.4.1 Key Algorithms 214
19.4.2 Applications 215
19.5 Exercises 215
20 Disaster Management 217
20.1 Introduction 218
20.2 Postaccident Mine Communications and Tracking Systems 219
20.2.1 Leaky-feeder System 219
20.3 Data Mining for Disaster Information Management 220
20.4 Algorithms for Smart Sensor Networks in Disaster Management 221
20.4.1 RSSI-based Localization with Mobile Anchors 222
20.5 Exercises 223
21 Communication Algorithms 225
21.1 Communication Algorithms for WSN 225
21.1.1 Key Algorithms 226
21.1.2 Applications 226
21.2 Store-carry-forward Based Communication Algorithm for DTN 226
21.2.1 Key Algorithms 227
21.2.2 Applications 227
21.3 Low Power-based Communication Algorithms for LLN 227
21.3.1 Key Algorithms 227
21.3.2 Applications 227
21.4 Software-defined Networking Algorithms 227
21.4.1 Key Algorithms 228
21.4.2 Applications 228
21.5 Peer-to-peer Network Algorithm 228
21.5.1 Key Algorithms 228
21.5.2 Applications 228
21.6 Exercises 228
References 231
Index 243
About the Author :
Suman Saha is an Associate Professor in the Department of Computer Science and Engineering at JK Laxmipat University, India. He has spent the last 15 years working in data and information science.
Shailendra Shukla is an Assistant Professor in the Department of Computer Science and Engineering at the Motilal Nehru National Institute of Technology, India. He obtained his PhD in Computer Science from the Indian Institute of Technology Patna.
