Algorithms for Smart World Technologies

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.

• Foreword xvPreface xviiAcknowledgments xixAcronyms xxiIntroduction xxvPart I Complexities of Smart Algorithms 11 Introduction to Complexities 31.1 Complex Systems and Algorithms 41.2 Complex Systems 41.2.1 Key Features of Complex Systems 41.2.2 Examples of Complex Systems 51.2.3 The Role of Algorithms in Complex Systems 51.2.4 Modeling and Simulation 51.2.5 Data Analysis 51.2.6 Optimization 51.2.7 Machine Learning 51.2.8 Challenges and Opportunities in Algorithmic Design 51.2.9 Future Directions 51.3 Efficiency Metrics for Complex Systems 61.3.1 Challenges in Measuring Efficiency 61.3.2 Techniques for Measuring Efficiency 71.3.3 Defining Efficiency in Complex Systems: A Holistic Approach 71.3.4 The Path Forward: Toward a Unified Framework 81.4 Applications of Complexity 81.4.1 Complexity in Practice 81.4.2 Complexity Management 81.4.3 Complexity Economics 81.4.4 Complexity and Education 91.4.5 Complexity and Modeling 91.4.6 Complexity and Chaos Theory 91.4.7 Complexity and Network Science 91.4.8 Complexity and Future Research Directions 101.5 Types of Complexities 101.6 Exercises 112 Computational Complexity 132.1 Computability 132.2 Computational Models 152.3 Complexity Classes 162.4 Probabilistic Complexity 172.4.1 The BPP Complexity Class 172.4.2 Examples of Probabilistic Complexity 172.4.3 BPP: Efficient Probabilistic Computation 172.4.4 Future Directions in Probabilistic Complexity 182.5 Quantum Complexity 182.5.1 BQP: Power and Intrigue 182.5.2 The P, NP, and BQP 192.5.3 BQP: Efficient Quantum Computation 192.5.4 Future Directions in Quantum Complexity 192.6 Exercises 203 Communication Complexity 233.1 Deterministic Communication 243.2 Deterministic Communication Complexity 243.3 Nondeterministic Communication 263.4 Nondeterministic Communication Complexity 263.5 Randomized Communication Complexity 273.5.1 Approximate Rank 283.6 Exercises 284 Data Complexity 314.1 Algorithmic Information Theory 324.1.1 Philosophy of Mathematics: Randomness Within Mathematics 324.1.2 Philosophy of Probability: Understanding Randomness of Individual Sequences 324.2 Occam’s Razor and Inductive Inference 334.3 Philosophy of Information 334.4 Lessons for the Philosophy of Information 344.5 Kolmogorov Complexity: Measuring Randomness 354.5.1 Defining Descriptions and Complexity 354.5.2 Compression and Invariance 354.5.3 Randomness and Compressibility 364.5.4 Connection to Gödel’s Theorem 364.6 VC Dimension: Measuring Model Complexity 364.6.1 VC Dimension of Set Families 364.6.2 VC Dimension of Classification Models 364.7 Rademacher Complexity 374.7.1 Rademacher Complexity of a Set 374.7.2 Rademacher Complexity of a Function Class 374.7.3 Example 374.7.4 Generalization Bound 384.7.5 Using Rademacher Complexity 384.7.6 Representativeness of a Sample 384.8 Exercises 385 Risk Measures 415.1 Addressing Algorithmic Bias 415.2 Risk Measures 425.3 Algorithmic Fairness Measures 435.4 Risks in Algorithmic Monoculture 445.5 Green Efficiency 455.5.1 Green Internet Technologies 465.5.2 Green RFID Tags 465.5.3 Green Wireless Sensor Networks 475.5.4 Green Cloud Computing 475.5.5 Green Data Centers 475.6 Conclusion 475.7 Exercises 476 Ethics and Algorithmic Boundaries 496.1 Introduction 496.2 Objectives 506.3 Algorithmic Decision-making 506.3.1 Background 506.3.2 Algorithmic Decision-making in Public Discourse 516.3.3 Ethical Challenges in Algorithmic Decision-making 516.3.4 ml and Autonomous Decision-making 516.4 Algorithmic Morality 526.4.1 Artificial Life and Emerging Ethical Behavior 526.4.2 Unbiased Learning Machines 526.4.3 Associative Learning and Moral Training 536.4.4 Ethical Risks of Learning Systems 536.5 Ethics as a Service 536.5.1 Service Model Analogies for Ethical Governance 536.5.2 Implementing the Ethics-as-a-Service Model 546.5.3 Case Study: Digital Catapult Pilot 546.5.4 Future Research Directions 546.6 Current Discussions and Future Research Directions 546.7 Conclusion 556.8 Exercises 55Part II Algorithmic Paradigms for Smart World Technologies 577 Introduction to Paradigms of Smart Algorithms 597.1 Introduction to Smart Paradigms 607.2 Important Algorithms in Smart Paradigms 607.2.1 ML Algorithms 607.2.2 Optimization Algorithms 607.2.3 IoT and Distributed Algorithms 617.3 Roadmap for Future Advancements 617.3.1 Enhancing Scalability 617.3.2 Data Privacy and Security 617.3.3 Autonomous and Intelligent Decision-making 617.3.4 Green Computing and Energy Efficiency 617.4 Conclusion 628 Optimization Algorithms 638.1 Constrained Optimization: Optimization with Limitations 638.2 Convex Optimization: Finding the Global Minimum 648.3 Solving Linear Equations 658.3.1 Steepest Descent: Gradient-based Minimization 668.3.2 Improving Convergence 668.3.3 Preconditioning with Trees 678.4 Linear Programming Duality 678.4.1 Complementary Slackness 688.4.2 Congestion Minimization 698.4.3 Maximum Weight Matching 698.4.4 Games and Strategic Solutions 698.4.5 The Minimax Theorem 708.5 Network Problems 728.5.1 Key Definitions 728.5.2 The Minimum-cost Flow Problem 728.5.3 The Transportation Problem 738.5.4 The Maximum Flow Problem 798.6 Exercises 829 Decision-making Algorithms 859.1 Markov Decision Process 859.1.1 Discrete MDPs 869.1.2 Nondiscrete MDPs: General Constructions 909.1.3 Discrete State MDPs 929.1.4 Classical Borel MDPs 929.1.5 Assumptions for Borel MDPs 939.1.6 Universally Measurable Borel MDPs 949.1.7 Assumptions for Universally Measurable MDPs 949.2 Reinforcement Learning 959.3 Value Iteration 969.4 Q-learning 979.5 TD Learning 989.6 Exercises 9910 Prediction Algorithms 10110.1 Regression 10110.1.1 Least Squares and Nearest-neighbor Methods 10110.1.2 Prediction Theory 10210.1.3 Curse of Dimensionality 10210.1.4 Learning as Function Approximation 10210.1.5 Key Formulas 10210.1.6 Linear Regression and Least Squares 10310.1.7 Variable Selection 10410.1.8 Best Subset Selection and Forward and Backward Stepwise Selection 10410.1.9 Smoothly Clipped Absolute Deviation 10610.1.10 Consistency and Oracle Property 10610.1.11 Selecting a Group of Variables 10710.1.12 Least Squares, Penalized Likelihood, and Bayesian Inference 10710.2 Classifications 10810.2.1 Issues with Linear Regression Approach 10810.2.2 Linear Discriminant Analysis 10810.2.3 Reduced-rank LDA 10910.2.4 Comparison Between Logistic Regression and LDA 11010.2.5 Piecewise Polynomial Functions 11110.2.6 Smoothing Splines 11110.2.7 Choosing Smoothing Parameters 11210.2 8 Hilbert Space 11310.2.9 Generalized Additive Models 11410.2.10 Fitting GAMs 11510.2.11 Illustration: Predicting Email Spam 11510.2.12 Tree-based Regression and Classification 11610.2.13 Regression Trees 11610.2.14 Classification Trees 11610.2.15 Challenges in Tree-based Methods 11710.2.16 Illustrative Example: Spam Prediction 11710.2.17 Hierarchical Mixtures of Experts and Missing Values 11810.2.18 One-dimensional Kernel Smoothers 11810.2.19 Considerations in Kernel Smoothing 11910.2.20 Local Regression and Local Likelihood Method 11910.2.21 Selecting the Width of the Kernel 12010.2.22 Structured Kernels and Local Likelihood Methods 12010.2.23 Kernel Density Estimation 12010.2.24 Application to Classification 12110.2.25 Mixture Models 12210.3 Model Complexity 12210.3.1 Bia-variance Decomposition 12310.3.2 Estimate the Errors 12410.3.3 Cross-validation 12510.3.4 Bootstrap 12610.3.5 The EM Algorithm 12610.3.6 Two Other Interpretations of EM Algorithm 12710.4 Bayesian Algorithms 12910.4.1 Variational Bayes 12910.4.2 The Key Identity 12910.4.3 Variational Inference 13010.4.4 Improvements and Variants 13110.4.5 Approximate Bayesian Computation 13110.4.6 The Discrete Version 13110.4.7 The Continuous Version 13110.4.8 Issues 13210.5 Neural Networks 13210.5.1 Fitting Neural Networks 13210.5.2 Some Issues with Neural Networks 13310.6 Support Vector Machines 13410.6.1 Separating Hyperplane 13410.6.2 Support Vectors 13410.7 Cluster Analysis 13510.7.1 Clustering Algorithms: Combinatorial 13610.7.2 Clustering Algorithms: k-means 13610.7.3 Clustering Algorithms: Hierarchical Clustering 13610.7.4 Principal Components, Curves, and Surfaces 13710.7.5 Procrustes Transform and Shape Averaging 13810.7.6 Factor Model and Independent Component Analysis 13910.7.7 Independent Component Analysis 13910.7.8 Principal Curve and Multidimensional Scaling 13910.8 Graphical Models 14010.8.1 False Discovery Rate 14010.8.2 Markov Graphs and Gaussian Graphical Models 14110.8.3 Undirected Graphs for Discrete Variables 14210.8.4 Exponential Random Graphs 14310.8.5 Eigen-statistics of Sample Covariance Matrices 14310.8.6 Bulk Universality: Marchenko–Pastur Law (or Quartercircle Law) 14310.8.7 Edge Universality: Tracy–Widom Law 14410.9 Exercises 14411 Secure Algorithms 14711.1 Low-power Cryptography 14811.2 Secret-key Cryptography 14811.3 Public-key Cryptography 14811.3.1 Key Exchange Protocol 14911.3.2 Trapdoor Functions 15011.3.3 md 5 15411.3.4 Secure Sockets Layer 15511.3.5 Blockchain 15611.3.6 Digital Signature 15711.4 Exercises 158Part III Smart World Applications 16112 Introduction to Smart World Applications 16312.1 Interesting Applications 16413 Smart Education 16713.1 Examples of Smart Education Tools 16713.2 Personalized Learning 16813.2.1 Key Algorithms 16813.2.2 Application Example 16913.3 Intelligent Content Delivery 16913.3.1 Key Algorithms 16913.3.2 Application Example 17013.4 Learning Analytics and Insights 17013.4.1 Key Algorithms 17013.4.2 Application Example 17013.5 Data Analytics in Education 17013.5.1 Key Algorithms 17013.5.2 Application Example 17113.6 AI Tutors and Assistants in Education 17113.6.1 Key Algorithms 17113.6.2 Application Example 17113.7 Assessment and Feedback in Education 17113.7.1 Key Algorithms 17213.7.2 Application Example 17213.8 Assessment and Feedback in Education 17213.8.1 Key Algorithms 17213.8.2 Application Example 17213.9 Collaborative Learning 17313.9.1 Key Algorithms 17313.9.2 Application Example 17313.10 Exercises 17414 Smart World Algorithms in Healthcare 17514.1 Patient Flow Scheduling and Capacity Planning 17514.1.1 Queueing Theory 17614.1.2 Simulation Algorithms 17614.1.3 Linear Programming 17614.2 Drug Packaging in the Healthcare Industry 17714.2.1 Robotic Process Automation 17714.2.2 Optical Character Recognition 17714.2.3 Predictive Analytics 17714.3 Data Security of Smart Healthcare 17814.3.1 Encryption Algorithms 17814.3.2 Blockchain Technology 17814.3.3 Machine Learning for Anomaly Detection 17814.4 Automated Nutrition Monitoring System 17814.4.1 Dietary Assessment Algorithms 17914.4.2 Recommendation Systems 17914.4.3 Image Recognition 17914.5 Exercises 17915 Modern Approach Algorithms in Environmental and Energy I nfrastructure 18115.1 Crowdsensing for Urban Air Pollution Monitoring 18115.1.1 Algorithms 18115.1.2 Application Example 18215.2 Green Energy Scheduling for Demand Side Management 18215.2.1 Algorithms 18215.2.2 Application Example 18315.3 Smart Grid 18315.3.1 Application Example 18415.4 Smart Waste Management Systems 18415.4.1 Application Example 18515.5 Drone Monitoring 18515.5.1 Application Example 18615.6 Exercises 18716 Smart Agriculture 18916.1 Precision Farming 18916.1.1 Key Algorithms 19016.1.2 Application Example 19016.2 Soil Health Monitoring 19116.2.1 Key Algorithms 19116.2.2 Application Example 19216.3 Irrigation Management 19216.3.1 Application Example 19316.4 Crop Yield Prediction 19316.4.1 Key Algorithms 19316.4.2 Application Example 19416.5 Exercises 19417 Smart Transportation 19717.1 Smart Traffic Management 19817.1.1 Key Algorithms and Applications 19817.2 Intelligent Transportation Systems 19917.2.1 Key Algorithms and Applications 19917.3 Public Transportation 20017.3.1 Key Algorithms and Applications 20017.4 Smart Parking 20117.4.1 Key Algorithms and Applications 20117.5 Autonomous Vehicles 20217.5.1 Key Algorithms and Applications 20217.6 Infrastructure Monitoring and Maintenance 20217.6.1 Key Algorithms 20217.7 Electric and Connected Vehicles 20317.7.1 Key Algorithms and Applications 20317.8 Emergency Response 20417.8.1 Key Algorithms and Applications 20417.9 Exercises 20418 Information Technology and Society 20718.1 Introduction 20718.2 Missing Person Identification 20718.2.1 Key Algorithms 20718.2.2 Applications 20818.3 Social Contagions 20818.3.1 Key Algorithms 20818.3.2 Applications 20818.4 Disease Propagation 20818.4.1 Key Algorithms 20818.4.2 Applications 20818.5 Crime Monitoring 20918.5.1 Key Algorithms 20918.5.2 Applications 20918.6 Exercises 20919 Smart Government 21119.1 E-government Services 21119.1.1 Key Algorithms 21119.1.2 Applications 21219.2 Smart Utilities 21219.2.1 Key Algorithms 21219.2.2 Applications 21319.3 Public Safety Enhancements 21419.3.1 Key Algorithms 21419.3.2 Applications 21419.4 Environmental Monitoring 21419.4.1 Key Algorithms 21419.4.2 Applications 21519.5 Exercises 21520 Disaster Management 21720.1 Introduction 21820.2 Postaccident Mine Communications and Tracking Systems 21920.2.1 Leaky-feeder System 21920.3 Data Mining for Disaster Information Management 22020.4 Algorithms for Smart Sensor Networks in Disaster Management 22120.4.1 RSSI-based Localization with Mobile Anchors 22220.5 Exercises 22321 Communication Algorithms 22521.1 Communication Algorithms for WSN 22521.1.1 Key Algorithms 22621.1.2 Applications 22621.2 Store-carry-forward Based Communication Algorithm for DTN 22621.2.1 Key Algorithms 22721.2.2 Applications 22721.3 Low Power-based Communication Algorithms for LLN 22721.3.1 Key Algorithms 22721.3.2 Applications 22721.4 Software-defined Networking Algorithms 22721.4.1 Key Algorithms 22821.4.2 Applications 22821.5 Peer-to-peer Network Algorithm 22821.5.1 Key Algorithms 22821.5.2 Applications 22821.6 Exercises 228References 231Index 243