ANALYTICS, DATA SCIENCE, & ARTIFICIAL INTELLIGENCE

/in /by

ANALYTICS, DATA SCIENCE, & ARTIFICIAL INTELLIGENCE

SYSTEMS FOR DECISION SUPPORT

E L E V E N T H E D I T I O N

Ramesh Sharda Oklahoma State University

Dursun Delen Oklahoma State University

Efraim Turban University of Hawaii

 

 

 

Microsoft and/or its respective suppliers make no representations about the suitability of the information contained in the documents and related graphics published as part of the services for any purpose. All such documents and related graphics are provided “as is” without warranty of any kind. Microsoft and/or its respective suppliers hereby disclaim all warranties and conditions with regard to this information, including all warranties and conditions of merchantability, whether express, implied or statutory, fitness for a particular purpose, title and non-infringement. In no event shall Microsoft and/or its respective suppliers be liable for any special, indirect or consequential damages or any damages whatsoever resulting from loss of use, data or profits, whether in an action of contract, negligence or other tortious action, arising out of or in connection with the use or performance of information available from the services. The documents and related graphics contained herein could include technical inaccuracies or typographical errors. Changes are periodically added to the information herein. Microsoft and/or its respective suppliers may make improvements and/or changes in the product(s) and/or the program(s) described herein at any time. Partial screen shots may be viewed in full within the software version specified. Microsoft® Windows® and Microsoft Office® are registered trademarks of Microsoft Corporation in the U.S.A. and other countries. This book is not sponsored or endorsed by or affiliated with the Microsoft Corporation.

Vice President of Courseware Portfolio Management: Andrew Gilfillan

Executive Portfolio Manager: Samantha Lewis Team Lead, Content Production: Laura Burgess Content Producer: Faraz Sharique Ali Portfolio Management Assistant: Bridget Daly Director of Product Marketing: Brad Parkins Director of Field Marketing: Jonathan Cottrell Product Marketing Manager: Heather Taylor Field Marketing Manager: Bob Nisbet Product Marketing Assistant: Liz Bennett Field Marketing Assistant: Derrica Moser Senior Operations Specialist: Diane Peirano Senior Art Director: Mary Seiner

Interior and Cover Design: Pearson CSC Cover Photo: Phonlamai Photo/Shutterstock Senior Product Model Manager: Eric Hakanson Manager, Digital Studio: Heather Darby Course Producer, MyLab MIS: Jaimie Noy Digital Studio Producer: Tanika Henderson Full-Service Project Manager: Gowthaman

Sadhanandham Full Service Vendor: Integra Software Service

Pvt. Ltd. Manufacturing Buyer: LSC Communications,

Maura Zaldivar-Garcia Text Printer/Bindery: LSC Communications Cover Printer: Phoenix Color

ISBN 10: 0-13-519201-3 ISBN 13: 978-0-13-519201-6

Copyright © 2020, 2015, 2011 by Pearson Education, Inc. 221 River Street, Hoboken, NJ 07030. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permissions, request forms and the appropriate contacts within the Pearson Education Global Rights & Permissions Department, please visit www.pearsoned.com/permissions. Acknowledgments of third-party content appear on the appropriate page within the text, which constitutes an extension of this copyright page. Unless otherwise indicated herein, any third-party trademarks that may appear in this work are the property of their respective owners and any references to third-party trademarks, logos or other trade dress are for demonstrative or descriptive purposes only. Such references are not intended to imply any sponsorship, endorsement, authorization, or promotion of Pearson’s products by the owners of such marks, or any relationship between the owner and Pearson Education, Inc. or its affiliates, authors, licensees or distributors.

Library of Congress Cataloging-in-Publication Data

Library of Congress Cataloging in Publication Control Number: 2018051774

 

 

iii

Preface xxv About the Authors xxxiv

PART I Introduction to Analytics and AI 1 Chapter 1 Overview of Business Intelligence, Analytics,

Data Science, and Artificial Intelligence: Systems for Decision Support 2

Chapter 2 Artificial Intelligence: Concepts, Drivers, Major Technologies, and Business Applications 73

Chapter 3 Nature of Data, Statistical Modeling, and Visualization 117

PART II Predictive Analytics/Machine Learning 193 Chapter 4 Data Mining Process, Methods, and Algorithms 194 Chapter 5 Machine-Learning Techniques for Predictive

Analytics 251 Chapter 6 Deep Learning and Cognitive Computing 315 Chapter 7 Text Mining, Sentiment Analysis, and Social

Analytics 388

PART III Prescriptive Analytics and Big Data 459 Chapter 8 Prescriptive Analytics: Optimization and

Simulation 460 Chapter 9 Big Data, Cloud Computing, and Location Analytics:

Concepts and Tools 509

PART IV Robotics, Social Networks, AI and IoT 579 Chapter 10 Robotics: Industrial and Consumer Applications 580 Chapter 11 Group Decision Making, Collaborative Systems, and

AI Support 610 Chapter 12 Knowledge Systems: Expert Systems, Recommenders,

Chatbots, Virtual Personal Assistants, and Robo Advisors 648

Chapter 13 The Internet of Things as a Platform for Intelligent Applications 687

PART V Caveats of Analytics and AI 725 Chapter 14 Implementation Issues: From Ethics and Privacy to

Organizational and Societal Impacts 726 Glossary 770 Index 785

BRIEF CONTENTS

 

 

iv

CONTENTS

Preface xxv

About the Authors xxxiv

PART I Introduction to Analytics and AI 1

Chapter 1 Overview of Business Intelligence, Analytics, Data Science, and Artificial Intelligence: Systems for Decision Support 2 1.1 Opening Vignette: How Intelligent Systems Work for

KONE Elevators and Escalators Company 3 1.2 Changing Business Environments and Evolving Needs for

Decision Support and Analytics 5 Decision-Making Process 6 The Influence of the External and Internal Environments on the Process 6 Data and Its Analysis in Decision Making 7 Technologies for Data Analysis and Decision Support 7

1.3 Decision-Making Processes and Computerized Decision Support Framework 9 Simon’s Process: Intelligence, Design, and Choice 9 The Intelligence Phase: Problem (or Opportunity) Identification 10 0 APPLICATION CASE 1.1 Making Elevators Go Faster! 11

The Design Phase 12 The Choice Phase 13 The Implementation Phase 13 The Classical Decision Support System Framework 14 A DSS Application 16 Components of a Decision Support System 18 The Data Management Subsystem 18 The Model Management Subsystem 19 0 APPLICATION CASE 1.2 SNAP DSS Helps OneNet Make

Telecommunications Rate Decisions 20

The User Interface Subsystem 20 The Knowledge-Based Management Subsystem 21

1.4 Evolution of Computerized Decision Support to Business Intelligence/Analytics/Data Science 22 A Framework for Business Intelligence 25 The Architecture of BI 25 The Origins and Drivers of BI 26 Data Warehouse as a Foundation for Business Intelligence 27 Transaction Processing versus Analytic Processing 27 A Multimedia Exercise in Business Intelligence 28

 

 

Contents v

1.5 Analytics Overview 30 Descriptive Analytics 32 0 APPLICATION CASE 1.3 Silvaris Increases Business with Visual

Analysis and Real-Time Reporting Capabilities 32 0 APPLICATION CASE 1.4 Siemens Reduces Cost with the Use of Data

Visualization 33

Predictive Analytics 33 0 APPLICATION CASE 1.5 Analyzing Athletic Injuries 34 Prescriptive Analytics 34 0 APPLICATION CASE 1.6 A Specialty Steel Bar Company Uses Analytics

to Determine Available-to-Promise Dates 35

1.6 Analytics Examples in Selected Domains 38 Sports Analytics—An Exciting Frontier for Learning and Understanding Applications of Analytics 38 Analytics Applications in Healthcare—Humana Examples 43 0 APPLICATION CASE 1.7 Image Analysis Helps Estimate Plant Cover 50

1.7 Artificial Intelligence Overview 52 What Is Artificial Intelligence? 52 The Major Benefits of AI 52 The Landscape of AI 52 0 APPLICATION CASE 1.8 AI Increases Passengers’ Comfort and

Security in Airports and Borders 54

The Three Flavors of AI Decisions 55 Autonomous AI 55 Societal Impacts 56 0 APPLICATION CASE 1.9 Robots Took the Job of Camel-Racing Jockeys

for Societal Benefits 58

1.8 Convergence of Analytics and AI 59 Major Differences between Analytics and AI 59 Why Combine Intelligent Systems? 60 How Convergence Can Help? 60 Big Data Is Empowering AI Technologies 60 The Convergence of AI and the IoT 61 The Convergence with Blockchain and Other Technologies 62 0 APPLICATION CASE 1.10 Amazon Go Is Open for Business 62 IBM and Microsoft Support for Intelligent Systems Convergence 63

1.9 Overview of the Analytics Ecosystem 63 1.10 Plan of the Book 65 1.11 Resources, Links, and the Teradata University Network

Connection 66 Resources and Links 66 Vendors, Products, and Demos 66 Periodicals 67 The Teradata University Network Connection 67

 

 

vi Contents

The Book’s Web Site 67 Chapter Highlights 67 • Key Terms 68 Questions for Discussion 68 • Exercises 69 References 70

Chapter 2 Artificial Intelligence: Concepts, Drivers, Major Technologies, and Business Applications 73 2.1 Opening Vignette: INRIX Solves Transportation

Problems 74 2.2 Introduction to Artificial Intelligence 76

Definitions 76 Major Characteristics of AI Machines 77 Major Elements of AI 77 AI Applications 78 Major Goals of AI 78 Drivers of AI 79 Benefits of AI 79 Some Limitations of AI Machines 81 Three Flavors of AI Decisions 81 Artificial Brain 82

2.3 Human and Computer Intelligence 83 What Is Intelligence? 83 How Intelligent Is AI? 84 Measuring AI 85 0 APPLICATION CASE 2.1 How Smart Can a Vacuum Cleaner Be? 86

2.4 Major AI Technologies and Some Derivatives 87 Intelligent Agents 87 Machine Learning 88 0 APPLICATION CASE 2.2 How Machine Learning Is Improving Work

in Business 89

Machine and Computer Vision 90 Robotic Systems 91 Natural Language Processing 92 Knowledge and Expert Systems and Recommenders 93 Chatbots 94 Emerging AI Technologies 94

2.5 AI Support for Decision Making 95 Some Issues and Factors in Using AI in Decision Making 96 AI Support of the Decision-Making Process 96 Automated Decision Making 97 0 APPLICATION CASE 2.3 How Companies Solve Real-World Problems

Using Google’s Machine-Learning Tools 97

Conclusion 98

 

 

Contents vii

2.6 AI Applications in Accounting 99 AI in Accounting: An Overview 99 AI in Big Accounting Companies 100 Accounting Applications in Small Firms 100 0 APPLICATION CASE 2.4 How EY, Deloitte, and PwC Are Using AI 100

Job of Accountants 101 2.7 AI Applications in Financial Services 101

AI Activities in Financial Services 101 AI in Banking: An Overview 101 Illustrative AI Applications in Banking 102 Insurance Services 103 0 APPLICATION CASE 2.5 US Bank Customer Recognition and

Services 104

2.8 AI in Human Resource Management (HRM) 105 AI in HRM: An Overview 105 AI in Onboarding 105 0 APPLICATION CASE 2.6 How Alexander Mann Solutions (AMS) Is

Using AI to Support the Recruiting Process 106

Introducing AI to HRM Operations 106 2.9 AI in Marketing, Advertising, and CRM 107

Overview of Major Applications 107 AI Marketing Assistants in Action 108 Customer Experiences and CRM 108 0 APPLICATION CASE 2.7 Kraft Foods Uses AI for Marketing

and CRM 109

Other Uses of AI in Marketing 110 2.10 AI Applications in Production-Operation

Management (POM) 110 AI in Manufacturing 110 Implementation Model 111 Intelligent Factories 111 Logistics and Transportation 112 Chapter Highlights 112 • Key Terms 113 Questions for Discussion 113 • Exercises 114 References 114

Chapter 3 Nature of Data, Statistical Modeling, and Visualization 117 3.1 Opening Vignette: SiriusXM Attracts and Engages a

New Generation of Radio Consumers with Data-Driven Marketing 118

3.2 Nature of Data 121 3.3 Simple Taxonomy of Data 125

0 APPLICATION CASE 3.1 Verizon Answers the Call for Innovation: The Nation’s Largest Network Provider uses Advanced Analytics to Bring the Future to its Customers 127

 

 

viii Contents

3.4 Art and Science of Data Preprocessing 129 0 APPLICATION CASE 3.2 Improving Student Retention with

Data-Driven Analytics 133

3.5 Statistical Modeling for Business Analytics 139 Descriptive Statistics for Descriptive Analytics 140 Measures of Centrality Tendency (Also Called Measures of Location or Centrality) 140 Arithmetic Mean 140 Median 141 Mode 141 Measures of Dispersion (Also Called Measures of Spread or Decentrality) 142 Range 142 Variance 142 Standard Deviation 143 Mean Absolute Deviation 143 Quartiles and Interquartile Range 143 Box-and-Whiskers Plot 143 Shape of a Distribution 145 0 APPLICATION CASE 3.3 Town of Cary Uses Analytics to Analyze Data

from Sensors, Assess Demand, and Detect Problems 150

3.6 Regression Modeling for Inferential Statistics 151 How Do We Develop the Linear Regression Model? 152 How Do We Know If the Model Is Good Enough? 153 What Are the Most Important Assumptions in Linear Regression? 154 Logistic Regression 155 Time-Series Forecasting 156 0 APPLICATION CASE 3.4 Predicting NCAA Bowl Game Outcomes 157

3.7 Business Reporting 163 0 APPLICATION CASE 3.5 Flood of Paper Ends at FEMA 165

3.8 Data Visualization 166 Brief History of Data Visualization 167 0 APPLICATION CASE 3.6 Macfarlan Smith Improves Operational

Performance Insight with Tableau Online 169

3.9 Different Types of Charts and Graphs 171 Basic Charts and Graphs 171 Specialized Charts and Graphs 172 Which Chart or Graph Should You Use? 174

3.10 Emergence of Visual Analytics 176 Visual Analytics 178 High-Powered Visual Analytics Environments 180

3.11 Information Dashboards 182

 

 

Contents ix

0 APPLICATION CASE 3.7 Dallas Cowboys Score Big with Tableau and Teknion 184

Dashboard Design 184 0 APPLICATION CASE 3.8 Visual Analytics Helps Energy Supplier Make

Better Connections 185

What to Look for in a Dashboard 186 Best Practices in Dashboard Design 187 Benchmark Key Performance Indicators with Industry Standards 187 Wrap the Dashboard Metrics with Contextual Metadata 187 Validate the Dashboard Design by a Usability Specialist 187 Prioritize and Rank Alerts/Exceptions Streamed to the Dashboard 188 Enrich the Dashboard with Business-User Comments 188 Present Information in Three Different Levels 188 Pick the Right Visual Construct Using Dashboard Design Principles 188 Provide for Guided Analytics 188 Chapter Highlights 188 • Key Terms 189 Questions for Discussion 190 • Exercises 190 References 192

PART II Predictive Analytics/Machine Learning 193

Chapter 4 Data Mining Process, Methods, and Algorithms 194 4.1 Opening Vignette: Miami-Dade Police Department Is Using

Predictive Analytics to Foresee and Fight Crime 195 4.2 Data Mining Concepts 198

0 APPLICATION CASE 4.1 Visa Is Enhancing the Customer Experience while Reducing Fraud with Predictive Analytics and Data Mining 199

Definitions, Characteristics, and Benefits 201 How Data Mining Works 202 0 APPLICATION CASE 4.2 American Honda Uses Advanced Analytics to

Improve Warranty Claims 203

Data Mining Versus Statistics 208 4.3 Data Mining Applications 208

0 APPLICATION CASE 4.3 Predictive Analytic and Data Mining Help Stop Terrorist Funding 210

4.4 Data Mining Process 211 Step 1: Business Understanding 212 Step 2: Data Understanding 212 Step 3: Data Preparation 213 Step 4: Model Building 214 0 APPLICATION CASE 4.4 Data Mining Helps in Cancer Research 214

Step 5: Testing and Evaluation 217

 

 

x Contents

Step 6: Deployment 217 Other Data Mining Standardized Processes and Methodologies 217

4.5 Data Mining Methods 220 Classification 220 Estimating the True Accuracy of Classification Models 221 Estimating the Relative Importance of Predictor Variables 224 Cluster Analysis for Data Mining 228 0 APPLICATION CASE 4.5 Influence Health Uses Advanced Predictive

Analytics to Focus on the Factors That Really Influence People’s Healthcare Decisions 229

Association Rule Mining 232 4.6 Data Mining Software Tools 236

0 APPLICATION CASE 4.6 Data Mining goes to Hollywood: Predicting Financial Success of Movies 239

4.7 Data Mining Privacy Issues, Myths, and Blunders 242 0 APPLICATION CASE 4.7 Predicting Customer Buying Patterns—The

Target Story 243

Data Mining Myths and Blunders 244 Chapter Highlights 246 • Key Terms 247 Questions for Discussion 247 • Exercises 248 References 250

Chapter 5 Machine-Learning Techniques for Predictive Analytics 251 5.1 Opening Vignette: Predictive Modeling Helps

Better Understand and Manage Complex Medical Procedures 252

5.2 Basic Concepts of Neural Networks 255 Biological versus Artificial Neural Networks 256 0 APPLICATION CASE 5.1 Neural Networks are Helping to Save

Lives in the Mining Industry 258

5.3 Neural Network Architectures 259 Kohonen’s Self-Organizing Feature Maps 259 Hopfield Networks 260 0 APPLICATION CASE 5.2 Predictive Modeling Is Powering the Power

Generators 261

5.4 Support Vector Machines 263 0 APPLICATION CASE 5.3 Identifying Injury Severity Risk Factors in

Vehicle Crashes with Predictive Analytics 264

Mathematical Formulation of SVM 269 Primal Form 269 Dual Form 269 Soft Margin 270 Nonlinear Classification 270 Kernel Trick 271

 

 

Contents xi

5.5 Process-Based Approach to the Use of SVM 271 Support Vector Machines versus Artificial Neural Networks 273

5.6 Nearest Neighbor Method for Prediction 274 Similarity Measure: The Distance Metric 275 Parameter Selection 275 0 APPLICATION CASE 5.4 Efficient Image Recognition and

Categorization with knn 277

5.7 Naïve Bayes Method for Classification 278 Bayes Theorem 279 Naïve Bayes Classifier 279 Process of Developing a Naïve Bayes Classifier 280 Testing Phase 281 0 APPLICATION CASE 5.5 Predicting Disease Progress in Crohn’s

Disease Patients: A Comparison of Analytics Methods 282

5.8 Bayesian Networks 287 How Does BN Work? 287 How Can BN Be Constructed? 288

5.9 Ensemble Modeling 293 Motivation—Why Do We Need to Use Ensembles? 293 Different Types of Ensembles 295 Bagging 296 Boosting 298 Variants of Bagging and Boosting 299 Stacking 300 Information Fusion 300 Summary—Ensembles are not Perfect! 301 0 APPLICATION CASE 5.6 To Imprison or Not to Imprison:

A Predictive Analytics-Based Decision Support System for Drug Courts 304

Chapter Highlights 306 • Key Terms 308 Questions for Discussion 308 • Exercises 309 Internet Exercises 312 • References 313

Chapter 6 Deep Learning and Cognitive Computing 315 6.1 Opening Vignette: Fighting Fraud with Deep Learning

and Artificial Intelligence 316 6.2 Introduction to Deep Learning 320

0 APPLICATION CASE 6.1 Finding the Next Football Star with Artificial Intelligence 323

6.3 Basics of “Shallow” Neural Networks 325 0 APPLICATION CASE 6.2 Gaming Companies Use Data Analytics to

Score Points with Players 328 0 APPLICATION CASE 6.3 Artificial Intelligence Helps Protect Animals

from Extinction 333

 

 

xii Contents

6.4 Process of Developing Neural Network–Based Systems 334 Learning Process in ANN 335 Backpropagation for ANN Training 336

6.5 Illuminating the Black Box of ANN 340 0 APPLICATION CASE 6.4 Sensitivity Analysis Reveals Injury Severity

Factors in Traffic Accidents 341

6.6 Deep Neural Networks 343 Feedforward Multilayer Perceptron (MLP)-Type Deep Networks 343 Impact of Random Weights in Deep MLP 344 More Hidden Layers versus More Neurons? 345 0 APPLICATION CASE 6.5 Georgia DOT Variable Speed Limit Analytics

Help Solve Traffic Congestions 346

6.7 Convolutional Neural Networks 349 Convolution Function 349 Pooling 352 Image Processing Using Convolutional Networks 353 0 APPLICATION CASE 6.6 From Image Recognition to Face

Recognition 356

Text Processing Using Convolutional Networks 357 6.8 Recurrent Networks and Long Short-Term Memory

Networks 360 0 APPLICATION CASE 6.7 Deliver Innovation by Understanding

Customer Sentiments 363

LSTM Networks Applications 365 6.9 Computer Frameworks for Implementation of Deep

Learning 368 Torch 368 Caffe 368 TensorFlow 369 Theano 369 Keras: An Application Programming Interface 370

6.10 Cognitive Computing 370 How Does Cognitive Computing Work? 371 How Does Cognitive Computing Differ from AI? 372 Cognitive Search 374 IBM Watson: Analytics at Its Best 375 0 APPLICATION CASE 6.8 IBM Watson Competes against the

Best at Jeopardy! 376

How Does Watson Do It? 377 What Is the Future for Watson? 377 Chapter Highlights 381 • Key Terms 383 Questions for Discussion 383 • Exercises 384 References 385

 

 

Contents xiii

Chapter 7 Text Mining, Sentiment Analysis, and Social Analytics 388 7.1 Opening Vignette: Amadori Group Converts Consumer

Sentiments into Near-Real-Time Sales 389 7.2 Text Analytics and Text Mining Overview 392

0 APPLICATION CASE 7.1 Netflix: Using Big Data to Drive Big Engagement: Unlocking the Power of Analytics to Drive Content and Consumer Insight 395

7.3 Natural Language Processing (NLP) 397 0 APPLICATION CASE 7.2 AMC Networks Is Using Analytics to

Capture New Viewers, Predict Ratings, and Add Value for Advertisers in a Multichannel World 399

7.4 Text Mining Applications 402 Marketing Applications 403 Security Applications 403 Biomedical Applications 404 0 APPLICATION CASE 7.3 Mining for Lies 404 Academic Applications 407 0 APPLICATION CASE 7.4 The Magic Behind the Magic: Instant Access

to Information Helps the Orlando Magic Up their Game and the Fan’s Experience 408

7.5 Text Mining Process 410 Task 1: Establish the Corpus 410 Task 2: Create the Term–Document Matrix 411 Task 3: Extract the Knowledge 413 0 APPLICATION CASE 7.5 Research Literature Survey with Text

Mining 415

7.6 Sentiment Analysis 418 0 APPLICATION CASE 7.6 Creating a Unique Digital Experience to

Capture Moments That Matter at Wimbledon 419

Sentiment Analysis Applications 422 Sentiment Analysis Process 424 Methods for Polarity Identification 426 Using a Lexicon 426 Using a Collection of Training Documents 427 Identifying Semantic Orientation of Sentences and Phrases 428 Identifying Semantic Orientation of Documents 428

7.7 Web Mining Overview 429 Web Content and Web Structure Mining 431

7.8 Search Engines 433 Anatomy of a Search Engine 434 1. Development Cycle 434 2. Response Cycle 435 Search Engine Optimization 436 Methods for Search Engine Optimization 437

 

 

xiv Contents

0 APPLICATION CASE 7.7 Delivering Individualized Content and Driving Digital Engagement: How Barbour Collected More Than 49,000 New Leads in One Month with Teradata Interactive 439

7.9 Web Usage Mining (Web Analytics) 441 Web Analytics Technologies 441 Web Analytics Metrics 442 Web Site Usability 442 Traffic Sources 443 Visitor Profiles 444 Conversion Statistics 444

7.10 Social Analytics 446 Social Network Analysis 446 Social Network Analysis Metrics 447 0 APPLICATION CASE 7.8 Tito’s Vodka Establishes Brand Loyalty with

an Authentic Social Strategy 447

Connections 450 Distributions 450 Segmentation 451 Social Media Analytics 451 How Do People Use Social Media? 452 Measuring the Social Media Impact 453 Best Practices in Social Media Analytics 453 Chapter Highlights 455 • Key Terms 456 Questions for Discussion 456 • Exercises 456 References 457

PART III Prescriptive Analytics and Big Data 459

Chapter 8 Prescriptive Analytics: Optimization and Simulation 460 8.1 Opening Vignette: School District of Philadelphia Uses

Prescriptive Analytics to Find Optimal Solution for Awarding Bus Route Contracts 461

8.2 Model-Based Decision Making 462 0 APPLICATION CASE 8.1 Canadian Football League Optimizes Game

Schedule 463

Prescriptive Analytics Model Examples 465 Identification of the Problem and Environmental Analysis 465 0 APPLICATION CASE 8.2 Ingram Micro Uses Business Intelligence

Applications to Make Pricing Decisions 466

Model Categories 467 8.3 Structure of Mathematical Models for Decision

Support 469 The Components of Decision Support Mathematical Models 469 The Structure of Mathematical Models 470

 

 

Contents xv

8.4 Certainty, Uncertainty, and Risk 471 Decision Making under Certainty 471 Decision Making under Uncertainty 472 Decision Making under Risk (Risk Analysis) 472 0 APPLICATION CASE 8.3 American Airlines Uses Should-Cost

Modeling to Assess the Uncertainty of Bids for Shipment Routes 472

8.5 Decision Modeling with Spreadsheets 473 0 APPLICATION CASE 8.4 Pennsylvania Adoption Exchange Uses

Spreadsheet Model to Better Match Children with Families 474 0 APPLICATION CASE 8.5 Metro Meals on Wheels Treasure Valley Uses

Excel to Find Optimal Delivery Routes 475

8.6 Mathematical Programming Optimization 477 0 APPLICATION CASE 8.6 Mixed-Integer Programming Model

Helps the University of Tennessee Medical Center with Scheduling Physicians 478

Linear Programming Model 479 Modeling in LP: An Example 480 Implementation 484

8.7 Multiple Goals, Sensitivity Analysis, What-If Analysis, and Goal Seeking 486 Multiple Goals 486 Sensitivity Analysis 487 What-If Analysis 488 Goal Seeking 489

8.8 Decision Analysis with Decision Tables and Decision Trees 490 Decision Tables 490 Decision Trees 492

8.9 Introduction to Simulation 493 Major Characteristics of Simulation 493 0 APPLICATION CASE 8.7 Steel Tubing Manufacturer Uses a

Simulation-Based Production Scheduling System 493

Advantages of Simulation 494 Disadvantages of Simulation 495 The Methodology of Simulation 495 Simulation Types 496 Monte Carlo Simulation 497 Discrete Event Simulation 498 0 APPLICATION CASE 8.8 Cosan Improves Its Renewable Energy

Supply Chain Using Simulation 498

8.10 Visual Interactive Simulation 500 Conventional Simulation Inadequacies 500 Visual Interactive Simulation 500

 

 

xvi Contents

Visual Interactive Models and DSS 500 Simulation Software 501 0 APPLICATION CASE 8.9 Improving Job-Shop Scheduling Decisions

through RFID: A Simulation-Based Assessment 501 Chapter Highlights 505 • Key Terms 505 Questions for Discussion 505 • Exercises 506 References 508

Chapter 9 Big Data, Cloud Computing, and Location Analytics: Concepts and Tools 509 9.1 Opening Vignette: Analyzing Customer Churn in a Telecom

Company Using Big Data Methods 510 9.2 Definition of Big Data 513

The “V”s That Define Big Data 514 0 APPLICATION CASE 9.1 Alternative Data for Market Analysis or

Forecasts 517

9.3 Fundamentals of Big Data Analytics 519 Business Problems Addressed by Big Data Analytics 521 0 APPLICATION CASE 9.2 Overstock.com Combines Multiple Datasets

to Understand Customer Journeys 522

9.4 Big Data Technologies 523 MapReduce 523 Why Use MapReduce? 523 Hadoop 524 How Does Hadoop Work? 525 Hadoop Technical Components 525 Hadoop: The Pros and Cons 527 NoSQL 528 0 APPLICATION CASE 9.3 eBay’s Big Data Solution 529 0 APPLICATION CASE 9.4 Understanding Quality and Reliability

of Healthcare Support Information on Twitter 531

9.5 Big Data and Data Warehousing 532 Use Cases for Hadoop 533 Use Cases for Data Warehousing 534 The Gray Areas (Any One of the Two Would Do the Job) 535 Coexistence of Hadoop and Data Warehouse 536

9.6 In-Memory Analytics and Apache Spark™ 537 0 APPLICATION CASE 9.5 Using Natural Language Processing to

analyze customer feedback in TripAdvisor reviews 538

Architecture of Apache SparkTM 538 Getting Started with Apache SparkTM 539

9.7 Big Data and Stream Analytics 543 Stream Analytics versus Perpetual Analytics 544 Critical Event Processing 545 Data Stream Mining 546 Applications of Stream Analytics 546

 

 

Contents xvii

e-Commerce 546 Telecommunications 546 0 APPLICATION CASE 9.6 Salesforce Is Using Streaming Data to

Enhance Customer Value 547

Law Enforcement and Cybersecurity 547 Power Industry 548 Financial Services 548 Health Sciences 548 Government 548

9.8 Big Data Vendors and Platforms 549 Infrastructure Services Providers 550 Analytics Solution Providers 550 Business Intelligence Providers Incorporating Big Data 551 0 APPLICATION CASE 9.7 Using Social Media for Nowcasting

Flu Activity 551 0 APPLICATION CASE 9.8 Analyzing Disease Patterns from an

Electronic Medical Records Data Warehouse 554

9.9 Cloud Computing and Business Analytics 557 Data as a Service (DaaS) 558 Software as a Service (SaaS) 559 Platform as a Service (PaaS) 559 Infrastructure as a Service (IaaS) 559 Essential Technologies for Cloud Computing 560 0 APPLICATION CASE 9.9 Major West Coast Utility Uses Cloud-Mobile

Technology to Provide Real-Time Incident Reporting 561

Cloud Deployment Models 563 Major Cloud Platform Providers in Analytics 563 Analytics as a Service (AaaS) 564 Representative Analytics as a Service Offerings 564 Illustrative Analytics Applications Employing the Cloud Infrastructure 565 Using Azure IOT, Stream Analytics, and Machine Learning to Improve Mobile Health Care Services 565 Gulf Air Uses Big Data to Get Deeper Customer Insight 566 Chime Enhances Customer Experience Using Snowflake 566

9.10 Location-Based Analytics for Organizations 567 Geospatial Analytics 567 0 APPLICATION CASE 9.10 Great Clips Employs Spatial Analytics to

Shave Time in Location Decisions 570

0 APPLICATION CASE 9.11 Starbucks Exploits GIS and Analytics to Grow Worldwide 570

Real-Time Location Intelligence 572 Analytics Applications for Consumers 573 Chapter Highlights 574 • Key Terms 575

Questions for Discussion 575 • Exercises 575 References 576

 

 

xviii Contents

PART IV Robotics, Social Networks, AI and IoT 579

Chapter 10 Robotics: Industrial and Consumer Applications 580 10.1 Opening Vignette: Robots Provide Emotional Support

to Patients and Children 581 10.2 Overview of Robotics 584 10.3 History of Robotics 584 10.4 Illustrative Applications of Robotics 586

Changing Precision Technology 586 Adidas 586 BMW Employs Collaborative Robots 587 Tega 587 San Francisco Burger Eatery 588 Spyce 588 Mahindra & Mahindra Ltd. 589 Robots in the Defense Industry 589 Pepper 590 Da Vinci Surgical System 592 Snoo – A Robotic Crib 593 MEDi 593 Care-E Robot 593 AGROBOT 594

10.5 Components of Robots 595 10.6 Various Categories of Robots 596 10.7 Autonomous Cars: Robots in Motion 597

Autonomous Vehicle Development 598 Issues with Self-Driving Cars 599

10.8 Impact of Robots on Current and Future Jobs 600 10.9 Legal Implications of Robots and Artificial Intelligence 603

Tort Liability 603 Patents 603 Property 604 Taxation 604 Practice of Law 604 Constitutional Law 605 Professional Certification 605 Law Enforcement 605 Chapter Highlights 606 • Key Terms 606 Questions for Discussion 606 • Exercises 607 References 607

 

 

Contents xix

Chapter 11 Group Decision Making, Collaborative Systems, and AI Support 610 11.1 Opening Vignette: Hendrick Motorsports Excels with

Collaborative Teams 611 11.2 Making Decisions in Groups: Characteristics, Process,

Benefits, and Dysfunctions 613 Characteristics of Group Work 613 Types of Decisions Made by Groups 614 Group Decision-Making Process 614 Benefits and Limitations of Group Work 615

11.3 Supporting Group Work and Team Collaboration with Computerized Systems 616 Overview of Group Support Systems (GSS) 617 Time/Place Framework 617 Group Collaboration for Decision Support 618

11.4 Electronic Support for Group Communication and Collaboration 619 Groupware for Group Collaboration 619 Synchronous versus Asynchronous Products 619 Virtual Meeting Systems 620 Collaborative Networks and Hubs 622 Collaborative Hubs 622 Social Collaboration 622 Sample of Popular Collaboration Software 623

11.5 Direct Computerized Support for Group Decision Making 623 Group Decision Support Systems (GDSS) 624 Characteristics of GDSS 625 Supporting the Entire Decision-Making Process 625 Brainstorming for Idea Generation and Problem Solving 627 Group Support Systems 628

11.6 Collective Intelligence and Collaborative Intelligence 629 Definitions and Benefits 629 Computerized Support to Collective Intelligence 629 0 APPLICATION CASE 11.1 Collaborative Modeling for Optimal

Water Management: The Oregon State University Project 630

How Collective Intelligence May Change Work and Life 631 Collaborative Intelligence 632 How to Create Business Value from Collaboration: The IBM Study 632

 

 

xx Contents

11.7 Crowdsourcing as a Method for Decision Support 633 The Essentials of Crowdsourcing 633 Crowdsourcing for Problem-Solving and Decision Support 634 Implementing Crowdsourcing for Problem Solving 635 0 APPLICATION CASE 11.2 How InnoCentive Helped GSK Solve a

Difficult Problem 636

11.8 Artificial Intelligence and Swarm AI Support of Team Collaboration and Group Decision Making 636 AI Support of Group Decision Making 637 AI Support of Team Collaboration 637 Swarm Intelligence and Swarm AI 639 0 APPLICATION CASE 11.3 XPRIZE Optimizes Visioneering 639

11.9 Human–Machine Collaboration and Teams of Robots 640 Human–Machine Collaboration in Cognitive Jobs 641 Robots as Coworkers: Opportunities and Challenges 641 Teams of collaborating Robots 642 Chapter Highlights 644 • Key Terms 645 Questions for Discussion 645 • Exercises 645 References 646

Chapter 12 Knowledge Systems: Expert Systems, Recommenders, Chatbots, Virtual Personal Assistants, and Robo Advisors 648 12.1 Opening Vignette: Sephora Excels with Chatbots 649 12.2 Expert Systems and Recommenders 650

Basic Concepts of Expert Systems (ES) 650 Characteristics and Benefits of ES 652 Typical Areas for ES Applications 653 Structure and Process of ES 653 0 APPLICATION CASE 12.1 ES Aid in Identification of Chemical,

Biological, and Radiological Agents 655

Why the Classical Type of ES Is Disappearing 655 0 APPLICATION CASE 12.2 VisiRule 656 Recommendation Systems 657 0 APPLICATION CASE 12.3 Netflix Recommender: A Critical Success

Factor 658

12.3 Concepts, Drivers, and Benefits of Chatbots 660 What Is a Chatbot? 660 Chatbot Evolution 660 Components of Chatbots and the Process of Their Use 662 Drivers and Benefits 663 Representative Chatbots from Around the World 663

12.4 Enterprise Chatbots 664 The Interest of Enterprises in Chatbots 664

 

 

Contents xxi

Enterprise Chatbots: Marketing and Customer Experience 665 0 APPLICATION CASE 12.4 WeChat’s Super Chatbot 666 0 APPLICATION CASE 12.5 How Vera Gold Mark Uses Chatbots to

Increase Sales 667

Enterprise Chatbots: Financial Services 668 Enterprise Chatbots: Service Industries 668 Chatbot Platforms 669 0 APPLICATION CASE 12.6 Transavia Airlines Uses Bots for

Communication and Customer Care Delivery 669

Knowledge for Enterprise Chatbots 671 12.5 Virtual Personal Assistants 672

Assistant for Information Search 672 If You Were Mark Zuckerberg, Facebook CEO 672 Amazon’s Alexa and Echo 672 Apple’s Siri 675 Google Assistant 675 Other Personal Assistants 675 Competition Among Large Tech Companies 675 Knowledge for Virtual Personal Assistants 675

12.6 Chatbots as Professional Advisors (Robo Advisors) 676 Robo Financial Advisors 676 Evolution of Financial Robo Advisors 676 Robo Advisors 2.0: Adding the Human Touch 676 0 APPLICATION CASE 12.7 Betterment, the Pioneer of Financial Robo

Advisors 677

Managing Mutual Funds Using AI 678 Other Professional Advisors 678 IBM Watson 680

12.7 Implementation Issues 680 Technology Issues 680 Disadvantages and Limitations of Bots 681 Quality of Chatbots 681 Setting Up Alexa’s Smart Home System 682 Constructing Bots 682 Chapter Highlights 683 • Key Terms 683 Questions for Discussion 684 • Exercises 684 References 685

Chapter 13 The Internet of Things as a Platform for Intelligent Applications 687 13.1 Opening Vignette: CNH Industrial Uses the Internet of

Things to Excel 688 13.2 Essentials of IoT 689

Definitions and Characteristics 690

 

 

xxii Contents

The IoT Ecosystem 691 Structure of IoT Systems 691

13.3 Major Benefits and Drivers of IoT 694 Major Benefits of IoT 694 Major Drivers of IoT 695 Opportunities 695

13.4 How IoT Works 696 IoT and Decision Support 696

13.5 Sensors and Their Role in IoT 697 Brief Introduction to Sensor Technology 697 0 APPLICATION CASE 13.1 Using Sensors, IoT, and AI for

Environmental Control at the Athens, Greece, International Airport 697

How Sensors Work with IoT 698 0 APPLICATION CASE 13.2 Rockwell Automation

Monitors Expensive Oil and Gas Exploration Assets to Predict Failures 698

Sensor Applications and Radio-Frequency Identification (RFID) Sensors 699 13.6 Selected IoT Applications 701

A Large-scale IoT in Action 701 Examples of Other Existing Applications 701

13.7 Smart Homes and Appliances 703 Typical Components of Smart Homes 703 Smart Appliances 704 A Smart Home Is Where the Bot Is 706 Barriers to Smart Home Adoption 707

13.8 Smart Cities and Factories 707 0 APPLICATION CASE 13.3 Amsterdam on the Road to Become a

Smart City 708

Smart Buildings: From Automated to Cognitive Buildings 709 Smart Components in Smart Cities and Smart Factories 709 0 APPLICATION CASE 13.4 How IBM Is Making Cities Smarter

Worldwide 711

Improving Transportation in the Smart City 712 Combining Analytics and IoT in Smart City Initiatives 713 Bill Gates’ Futuristic Smart City 713 Technology Support for Smart Cities 713

13.9 Autonomous (Self-Driving) Vehicles 714 The Developments of Smart Vehicles 714 0 APPLICATION CASE 13.5 Waymo and Autonomous Vehicles 715 Flying Cars 717 Implementation Issues in Autonomous Vehicles 717

 

 

Contents xxiii

13.10 Implementing IoT and Managerial Considerations 717 Major Implementation Issues 718 Strategy for Turning Industrial IoT into Competitive Advantage 719 The Future of the IoT 720 Chapter Highlights 721 • Key Terms 721 Questions for Discussion 722 • Exercises 722 References 722

PART V Caveats of Analytics and AI 725

Chapter 14 Implementation Issues: From Ethics and Privacy to Organizational and Societal Impacts 726 14.1 Opening Vignette: Why Did Uber Pay $245 Million to

Waymo? 727 14.2 Implementing Intelligent Systems: An Overview 729

The Intelligent Systems Implementation Process 729 The Impacts of Intelligent Systems 730

14.3 Legal, Privacy, and Ethical Issues 731 Legal Issues 731 Privacy Issues 732 Who Owns Our Private Data? 735 Ethics Issues 735 Ethical Issues of Intelligent Systems 736 Other Topics in Intelligent Systems Ethics 736

14.4 Successful Deployment of Intelligent Systems 737 Top Management and Implementation 738 System Development Implementation Issues 738 Connectivity and Integration 739 Security Protection 739 Leveraging Intelligent Systems in Business 739 Intelligent System Adoption 740

14.5 Impacts of Intelligent Systems on Organizations 740 New Organizational Units and Their Management 741 Transforming Businesses and Increasing Competitive Advantage 741 0 APPLICATION CASE 14.1 How 1-800-Flowers.com Uses Intelligent

Systems for Competitive Advantage 742

Redesign of an Organization Through the Use of Analytics 743 Intelligent Systems’ Impact on Managers’ Activities, Performance, and Job Satisfaction 744 Impact on Decision Making 745 Industrial Restructuring 746

 

 

xxiv Contents

14.6 Impacts on Jobs and Work 747 An Overview 747 Are Intelligent Systems Going to Take Jobs—My Job? 747 AI Puts Many Jobs at Risk 748 0 APPLICATION CASE 14.2 White-Collar Jobs That Robots Have

Already Taken 748

Project Management Presentation

/in /by

Project Management Presentation

Overview

For this assignment, you will demonstrate your knowledge of the role of project management in information systems and why it is such an important component.

Imagine you are currently working in an information systems field at a small company in which projects have been typically managed by the senior employee working on them without any real plan or specific direction, and each employee has a very different style of management (or lack thereof). The company has recently considered improving in this area and might even consider hiring a project manager or adopting some kind of software or process for managing the project it takes on. There is obviously a need for change, but not everyone is on board.

In an effort to help everyone see the value of project management improvements, you have been asked to create a presentation on why the company might need a more formalized process for project management. You will need to explain what project management really and why it is such a significant part of information systems work. You will also need to make some recommendations on what types of project management strategies the company might want to adopt.

Instructions

Your presentation should include:

  • 10–12 slides.
  • A title slide (not included in the required number of slides).
  • A reference slide (not included in the required number of slides).
  • Three examples of some of the pitfalls that occur in projects when there is no project management.
  • Three examples of how project management can prevent pitfalls when there is no project management.
  • Three examples of how using project management can benefit the creation of an information system.
  • A detailed list of at least three recommendations for project management tools or strategies the company should adopt and an explanation of why those were chosen.
  • Use the Basic Search: Strayer University Online Library to find at least three academic resources. Note: Wikipedia and similar Websites are not considered quality references.

This course requires the use of Strayer Writing Standards. For assistance and information, please refer to the Strayer Writing Standards link in the left-hand menu of your course. Check with your professor for any additional instructions.

The specific course learning outcome associated with this assignment is:

  • Explain how project management is used to enhance productivity and optimize an organization’s resources.

Java Programming Take Home Final Exam Write definition for a class called Rainfall that will store the amount of rainfall per month in array called rain.

/in /by

CSP26A – Java Programming Take Home Final Exam Write definition for a class called Rainfall that will store the amount of rainfall per month in array called rain. The beginning of the clss is shown below. public class Rainfall

{

private double[] rain; // Array to hold rainfall data

 

….

}

Your Rainfall class should have the following: a) A constructor that will initialize the rain array using values from an

array that has 12 values for rainfall amount for 12 months of the year. b) A method called getTotalRainfall to return the total rainfall for the year

– total of all values in the rain array. c) A method called getAverageRainfall to return the average of rainfall for

the year. d) A method called getHighestMonth to return the month number that has the

highest rainfall for the year. e) A method called getLowestMonth to return the month number that has the

lowest rainfall for the year. f) A method called print to print all the rainfall amount for all months with

values separated by a blank or a tab. Your test program can be something like this. public class RainfallTest

{

public static void main(String[] args)

{

// Create an array of rainfall figures.

double[] thisYear = {1.6, 2.1, 1.7, 3.5, 2.6, 3.7,

3.9, 2.6, 2.9, 4.3, 2.4, 3.7 };

 

 

 

2

 

What to submit? In a Word document:

• Copy paste your Java code below this label

• followed by your output. • Also, give link to your repl.it project if you used repl.it

Lastly, convert document to pdf format and submit this pdf file. ONLY ONE file to be submiteed

Music Retrieval Techniques

/in /by

CSC475 / SENG480B Music Retrieval Techniques

Assignment 5 Fall 2020

J. Shier

November 18, 2020

1 Introduction

In this assignment we will explore similarity and self-similarity matrices, dynamic time warping as well as sound source separation and transcription. There are three levels of engagement: Minimum, Expected, Advanced. Minimum is the least amount of work you can do to keep up with the course. If you are not able to complete the minimum work suggested then this course is probably not for you. Expected is what a typical student of the course should work on – the goal is to provide a solid foundation and understanding but not go deeper into more interesting questions and research topics. Advanced is what students who are particularly interested in the topic of MIR, students who want a high grade, students interested in graduate school, and graduate students should work on. Each level of en- gagement includes the previous one so a student who is very interested in the topic should complete all three levels of engagement (Minimum, Expected, Advanced).

The assignment is worth 10% of the final grade. There is some variance in the amount of time each question probably will require. Please provide your answers as a single Jupyter Python notebook (.ipynb) uploaded through the BrightSpace website for the course. Also please answer the questions in order and explicitly mention if you have decided to skip a question. For the questions that do not require programming use the ability to write Mark- down in Jupyter notebooks for your answer. You are also welcome to do the assignment in any other programming language/framework. If you do so please include a PDF file with plots and figures for questions that re- quire them, as well as answers for questions that don’t require coding. Also include the code itself with instructions on how to run it in a README file.

1

 

 

Note: Please upload your completed notebook as a zip file with all audio files used to complete your assignment. Only include the audio files that you used to keep the upload size as small as possible. (i.e. do not upload all of GTZAN or any other dataset)

2 Problems

The coding problems mention specific libraries/frameworks for Python that can help you with implementation. However you should be able to find corresponding libraries or code for most programming languages if you want to try using a different programming language or environment.

1. For this question use a 30 second clip of audio that you like. You can either use you own or use any of the clips in the GTZAN dataset. Try to select a clip that has a repeating rhythm, phrase, or harmonic struc- ture that you can identify in a self-similarity matrix – you may need to experiment with a few different audio files to find one that works well. You can download GTZAN here: https://drive.google.com/ file/d/16qBM8tYXn2z5LOl82mjnRAxQyZsJ0xdP/view?usp=sharing

• a) Repeat the 30 second recording to create a one minute record- ing. Plot the cross-similarity matrix1 for this new one minute long clip with the original 30 second recording. Describe how the repetition can be seen in a plot of the cross-similarity matrix. Use MFCC features and the affinity mode. (Minimum: 1pt)

• b) Plot the self-similarity matrix for your original 30 second clip (i.e the cross-similarity to itself). Visually identify a repeating structure (it could be a bar, a phrase, a segment) on the self- similarity matrix, describe it, and generate two audio fragments that demonstrate this repetition. Hint: repetition shows as block structure, you will need to map the dimensions of the repeating block to time to select the audio fragments. (Minimum: 1pt)

• c) Use time stretching2 on your audio recording to create the following modified signal: the first 10 seconds should be slowed down (rate 0.75), the middle 10 seconds should remain the same,

1 https://librosa.org/doc/latest/generated/librosa.segment.cross_

similarity.html 2 https://librosa.org/doc/latest/generated/librosa.effects.time_stretch.

html

2

 

 

and the last 10 seconds should be sped up (rate 1.25). Plot the cross-similarity matrix between the original and modified record- ing (use MFCC features and the affinity mode) and describe how the time-stretching can be observed visually.

• d) Use harmonic/percussive sound source separation3 to generate a percussive track and a harmonic track from your 30 second ex- ample. Plot the self-similarity matrices using affinity for the per- cussive and harmonic versions using MFCCs as well as Chroma (use chroma cqt4 or chroma stft5). Based on the resulting four plots discuss feature set works better for each configuration (har- monic/percussive). (Expected: 1pt)

• e) Use Dynamic Time Warping6 using the original and modified (time-stretched) recording you created in the previous subques- tion. Plot the cost matrix and associated optimal path and de- scribe how the optimal path reflects the time stretching. Show how you can estimate the time-stretching rates from the opti- mal path. You can assume that you know that the rate is going to change every 10 seconds but you dont know what the corre- sponding rates are. Test your procedure with a set of different time stretching rates. (Expected: 1pt)

2. In this question you will be using a state-of-the art deep learning sound source separation library: https://github.com/deezer/spleeter to explore sound source separation, and transcription. For answering the question you can either select a track that you like or use one of the tracks from musdb (a database for sound source separation for music for which spleeter performs quite well): https://sigsep.github.io/ datasets/musdb.html.

• a) Run the sound source separation with the 4 stem model on your example audio recording. Listen and plot the time-domain waveforms of the 4 individual stems. Comment on what you hear. (Minimum: 1pt)

• b) Pitch shift the vocal stem by a major third (4 semitones) using librosa.effects.pitch_shift and mix the pitch shifted audio

3 https://librosa.org/doc/latest/generated/librosa.effects.hpss.html

4 https://librosa.org/doc/latest/generated/librosa.feature.chroma_cqt.html

5 https://librosa.org/doc/latest/generated/librosa.feature.chroma_stft.

html 6 https://librosa.org/doc/latest/generated/librosa.sequence.dtw.html

3

 

 

with the other stems. Listen to the result and comment on it. (Minimum: 1pt)

• c) Run monophonic pitch detection (either your own implemen- tation or using some library like librosa) on the vocal stem, sonify it using a sinusoid (you can use the sonification code provided in the template) and mix with the drum track. Listen to the result and comment on whether you still recognize the song. (Expected: 1pt)

• d) Inspect the magnitude spectrogram of the drum track and try to identify features that characterize the kick sound and the snare sound. Based on your visual inspection write a simple kick and snare detection method that outputs the times where a kick or snare drum occurs. Your method only needs to work for the specific example you are examining and does not need to be per- fect. Create a new track by placing the kick.wav and snare.wav samples from the resources folder in the detected locations. Mix your synthetic toy drum track and sinusoid sonification from the previous question and listen to the result. Can you still identify the song? (Advanced: 1pt)

• e) Run beat tracking on the drum track (result from spleeter) and then use the resulting beat onsets combined with the extracted pitch from the vocal melody to transcribe the vocal melody to music notation using music21. For each beat map the median MIDI pitch of the vocals to a tiny notation string. Listen to the generated MIDI melody using Music21. Can you still identify the melody? (Advanced: 1pt)

 Portfolio Assignment

/in /by

1. Week 6 Assignment

Complete the following assignment in one MS word document: Chapter 10 –discussion question #1-2 & exercise 1 & 7Chapter 11- discussion question #1-4 & exercise 4When submitting work, be sure to include an APA cover page and include at least two APA formatted references (and APA in-text citations) to support the work this week. All work must be original (not copied from any source).

2.  Portfolio Assignment

Portfolio Project: This week discuss a current business process in a specific industry.  Note the following:-The current business process itself.-The industry the business process is utilized in. After explaining the current situation, take the current learning from the course and:

  • Explain a new technology that the business should deploy.  Be specific, don’t only note the type of technology but the specific instance of technology.  (For example, a type of technology is smart automation a specific type of automation is automated light-dimming technology).
  • Note the pros and cons of the technology selected.
  • Note various factors the business should consider prior to deploying the new technology

The above submission should be three pages in length.  Remember the total length does not include the APA approved cover page or the references.  There should be at least three APA approved references to support your work.

3.  Week 6: Discussion 1

Create a discussion thread (with your name) and answer the following question:  Discussion 1 (Chapter 10): There have been many books and opinion pieces writ-ten about the impact of AI on jobs and ideas for societal responses to address the issues. Two ideas were mentioned in the chapter – UBI and SIS. What are the pros and cons of these ideas? How would these be implemented?Your response should be 250-300 words.  Respond to two postings provided by your classmates.There must be at least one APA formatted reference (and APA in-text citation) to support the thoughts in the post.  Do not use direct quotes, rather rephrase the author’s words and continue to use in-text citations.

4.  Week 6: Discussion 2

Create a discussion thread (with your name) and answer the following question:

Discussion 2 (Chapter 11): Explain how GDSS can increase some benefits of collaboration and decision making in groups and eliminate or reduce some losses.

Note: The first post should be made by Wednesday 11:59 p.m., EST. I am looking for active engagement in the discussion.  Please engage early and often.

Your response should be 250-300 words.  Respond to two postings provided by your classmates.

There must be at least one APA formatted reference (and APA in-text citation) to support the thoughts in the post.  Do not use direct quotes, rather rephrase the author’s words and continue to use in-text citations.

Background:

Robotics, Group Decision Making, Collaborative Systems, and AI Support

Chapter 2 briefly introduced robotics, an early and practical application of concepts developed in AI. In this chapter 10, we present a number of applications of robots in industrial as well as personal settings. Besides learning about the already deployed and emerging applications, we identify the general components of a robot. In the spirit of managerial considerations, we also discuss the impact of robotics on jobs as well as related legal issues.The focus in this chapter is on physical robots, not just software-driven applications of AI.

In chapter11, several topics related to group decision support and collaboration were covered. People work together, and groups (or teams) make many of the complex decisions in organizations. The increase in organizational decision-making complexity drives the need for meetings and group work. Supporting group work in which team members may be in different locations and working at different times emphasizes the important aspects of communications, computer-mediated collaboration, and workplace methodologies. Group support is a critical aspect of decision support systems (DSS). Effective computer-supported group support systems have evolved to increase gains and decrease losses in task performance and underlying processes. New tools and methodology are used to support teamwork. These include collective intelligence, crowdsourcing, and different types of AI. Finally, human–machine and machine–machine collaboration are increasing the power of collaboration and problem solving.

Robots provide emotional support to patients and children

/in /by

Chapter 10 Slides

 

 

▪ Opening Vignette

▪ Robots provide emotional support to patients and children

 

 

▪ Automation

▪ Autonomy

▪ The first idea of robotics was conceptual-ized in 320 BC when Aristotle, a Greek philosopher, stated, “If every tool, when ordered, or even of its own accord, could do the work that befits it, then there would be no need either of apprentices for the master workers…

 

 

▪ Changing Precision Technology

▪ Examples based on industry

 

 

▪ Sensors

▪ CPU /Controllers

▪ Effectors

▪ Actuator System

▪ Power Supply

 

 

▪ Preset Robots

▪ Collaborative Robots

▪ Stand-Alone Robots

▪ Supplementary Robots

 

 

▪ Technologies to drive development of self-driving cars:

▪ Mobile phones

▪ Wireless internet

▪ Computer centers in cars

▪ Maps

▪ Deep learning

▪ Issues with self driving cars

 

 

▪ AI development

▪ Customer-Robot interactions

▪ Robot managers

▪ Data labelers

▪ Robot pilots and artists

▪ Test drivers and quality inspectors

▪ AI lab scientists

 

 

▪ Tort liability

▪ Patents

▪ Property

▪ Taxation

▪ Practice of Law

▪ Constitutional Law

▪ Professional Certification

▪ Law Enforcement

 

 

▪ Review the Chapter highlights

▪ Review the key terms

▪ Complete the weekly homework

SMP5: Scheduler with Signals 

/in /by

SMP5: Scheduler with Signals

In the last MP, we built a simulated OS process scheduler. The scheduler can

hold only a certain number of processes (workers) at one time. Once the process

has been accepted into the scheduler, the scheduler decides in what order the

processes execute. We implemented two scheduling algorithms: FIFO and Round

Robin.

In this MP, we are to simulate a time-sharing system by using signals and

timers. We will only implement the Round Robin algorithm. Instead of using

iterations to model the concept of “time slices” (as in the last MP), we use

interval timers.  The scheduler is installed with an interval timer. The timer

starts ticking when the scheduler picks a thread to use the CPU which in turn

signals the thread when its time slice is finished thus allowing the scheduler

to pick another thread and so on. When a thread has completely finished its work

it leaves the scheduler to allow a waiting thread to enter. Please note that in

this MP, only the timer and scheduler send signals. The threads passively handle

the signals without signaling back to the scheduler.

The program takes a number of arguments. Arg1 determines the number of jobs

(threads in our implementation) created; arg2 specifies the queue size of the

scheduler. Arg3 through argN gives the duration (the required time slices to

complete a job) of each job. Hence if we create 2 jobs, we should supply arg3

and arg4 for the required duration. You can assume that the autograder will

always supply the correct number of arguments and hence you do not have to

detect invalid input.

Here is an example of program output, once the program is complete:

% scheduler 3 2 3 2 3

Main: running 3 workers with queue size 2 for quanta:

3 2 3

Main: detaching worker thread 3075926960.

Main: detaching worker thread 3065437104.

Main: detaching worker thread 3054947248.

Main: waiting for scheduler 3086416816.

Scheduler: waiting for workers.

Thread 3075926960: in scheduler queue.

Thread 3075926960: suspending.

Thread 3065437104: in scheduler queue.

Thread 3065437104: suspending.

Scheduler: scheduling.

Scheduler: resuming 3075926960.

Thread 3075926960: resuming.

Scheduler: suspending 3075926960.

Scheduler: scheduling.

Scheduler: resuming 3065437104.

Thread 3065437104: resuming.

Thread 3075926960: suspending.

Scheduler: suspending 3065437104.

Scheduler: scheduling.

Scheduler: resuming 3075926960.

Thread 3075926960: resuming.

Thread 3065437104: suspending.

Scheduler: suspending 3075926960.

Scheduler: scheduling.

Scheduler: resuming 3065437104.

Thread 3065437104: resuming.

Thread 3075926960: suspending.

Scheduler: suspending 3065437104.

Thread 3065437104: leaving scheduler queue.

Scheduler: scheduling.

Scheduler: resuming 3075926960.

Thread 3075926960: resuming.

Thread 3065437104: terminating.

Thread 3054947248: in scheduler queue.

Thread 3054947248: suspending.

Scheduler: suspending 3075926960.

Thread 3075926960: leaving scheduler queue.

Scheduler: scheduling.

Scheduler: resuming 3054947248.

Thread 3054947248: resuming.

Thread 3075926960: terminating.

Scheduler: suspending 3054947248.

Scheduler: scheduling.

Scheduler: resuming 3054947248.

Thread 3054947248: suspending.

Thread 3054947248: resuming.

Scheduler: suspending 3054947248.

Scheduler: scheduling.

Scheduler: resuming 3054947248.

Thread 3054947248: suspending.

Thread 3054947248: resuming.

Scheduler: suspending 3054947248.

Thread 3054947248: leaving scheduler queue.

Thread 3054947248: terminating.

The total wait time is 12.062254 seconds.

The total run time is 7.958618 seconds.

The average wait time is 4.020751 seconds.

The average run time is 2.652873 seconds.

The goal of this MP is to help you understand (1) how signals and timers work,

and (2) how to evaluate the performance of your program. You will first

implement the time-sharing system using timers and signals. Then, you will

evaluate the overall performance of your program by keeping track of how long

each thread is idle, running, etc.

The program will use these four signals:

SIGALRM: sent by the timer to the scheduler, to indicate another time

quantum has passed.

SIGUSR1: sent by the scheduler to a worker, to tell it to suspend.

SIGUSR2: sent by the scheduler to a suspended worker, to tell it to resume.

SIGTERM: sent by the scheduler to a worker, to tell it to cancel.

You will need to set up the appropriate handlers and masks for these signals.

You will use these functions:

clock_gettime

pthread_sigmask

pthread_kill

sigaction

sigaddset

sigemptyset

sigwait

timer_settime

timer_create

Also, make sure you understand how the POSIX:TMR interval timer works.

There are two ways you can test your code.  You can run the built-in grading

tests by running “scheduler -test -f0 rr”.  This runs 5 tests, each of which can

be run individually.  You can also test you program with specific parameters by

running “scheduler -test gen …” where the ellipsis contains the parameters you

would pass to scheduler.

Programming

===========

Part I: Modify the scheduler code (scheduler.c)

———————————————–

We use the scheduler thread to setup the timer and handle the scheduling for the

system.  The scheduler handles the SIGALRM events that come from the timer, and

sends out signals to the worker threads.

Step 1.

Modify the code in init_sched_queue() function in scheduler.c to initialize the

scheduler with a POSIX:TMR interval timer. Use CLOCK_REALTIME in timer_create().

The timer will be stored in the global variable “timer”, which will be started

in scheduler_run() (see Step 4 below).

Step 2.

Implement setup_sig_handlers().  Use sigaction() to install signal handlers for

SIGALRM, SIGUSR1, and SIGTERM.  SIGALRM should trigger timer_handler(), SIGUSR1

should trigger suspend_thread(), and SIGTERM should trigger cancel_thread().

Notice no handler is installed for SIGUSR2; this signal will be handled

differently, in step 8.

Step 3.

In the scheduler_run() function, start the timer.  Use timer_settime().  The

time quantum (1 second) is given in scheduler.h.  The timer should go off

repeatedly at regular intervals defined by the timer quantum.

In Round-Robin, whenever the timer goes off, the scheduler suspends the

currently running thread, and tells the next thread to resume its operations

using signals. These steps are listed in timer_handler(), which is called every

time the timer goes off.  In this implementation, the timer handler makes use of

suspend_worker() and resume_worker() to accomplush these steps.

Step 4.

Complete the suspend_worker() function.  First, update the info->quanta value.

This is the number of quanta that remain for this thread to execute.  It is

initialized to the value passed on the command line, and decreases as the thread

executes.  If there is any more work for this worker to do, send it a signal to

suspend, and update the scheduler queue.  Otherwise, cancel the thread.

Step 5.

Complete the cancel_worker() function by sending the appropriate signal to the

thread, telling it to kill itself.

Step 6.

Complete the resume_worker() function by sending the appropriate signal to the

thread, telling it to resume execution.

Part II: Modify the worker code (worker.c)

——————————————

In this section, you will modify the worker code to correctly handle the signals

from the scheduler that you implemented in the previous section.

You need to modify the thread functions so that it immediately suspends the

thread, waiting for a resume signal from the scheduler. You will need to use

sigwait() to force the thread to suspend itself and wait for a resume signal.

You need also to implement a signal handler in worker.c to catch and handle the

suspend signals.

Step 7.

Modify start_worker() to (1) block SIGUSR2 and SIGALRM, and (2) unblock SIGUSR1

and SIGTERM.

Step 8.

Implement suspend_thread(), the handler for the SIGUSR1 signal.  The

thread should block until it receives a resume (SIGUSR2) signal.

Part III: Modify the evaluation code (scheduler.c)

————————————————–

This program keeps track of run time, and wait time.  Each thread saves these

two values regarding its own execution in its thread_info_t.  Tracking these

values requires also knowing the last time the thread suspended or resumed.

Therefore, these two values are also kept in thread_info_t.  See scheduler.h.

In this section, you will implement the functions that calculate run time and

wait time.  All code that does this will be in scheduler.c.  When the program

is done, it will collect all these values, and print out the total and average

wait time and run time.  For your convenience, you are given a function

time_difference() to compute the difference between two times in microseconds.

Step 9.

Modify create_workers() to initialize the various time variables.

Step 10.

Implement update_run_time().  This is called by suspend_worker().

Step 11.

Implement update_wait_time().  This is called by resume_worker().

Questions

==========

Question 1.

Why do we block SIGUSR2 and SIGALRM in worker.c?  Why do we unblock SIGUSR1 and

SIGTERM in worker.c?

Question 2.

We use sigwait() and sigaction() in our code. Explain the difference between the

two. (Please explain from the aspect of thread behavior rather than syntax).

Question 3.

When we use POSIX:TMR interval timer, we are using relative time. What is the

alternative? Explain the difference between the two.

Question 4.

Look at start_worker() in worker.c, a worker thread is executing within an

infinite loop at the end. When does a worker thread terminate?

Question 5.

When does the scheduler finish?  Why does it not exit when the scheduler queue

is empty?

Question 6.

After a thread is scheduled to run, is it still in the sched_queue? When is it

removed from the head of the queue? When is it removed from the queue completely?

Question 7.

We’ve removed all other condition variables in SMP4, and replaced them with a

timer and signals. Why do we still use the semaphore queue_sem?

Question 8.

What’s the purpose of the global variable “completed” in scheduler.c? Why do we

compare “completed” with thread_count before we wait_for_queue() in

next_worker()?

Question 9.

We only implemented Round Robin in this SMP. If we want to implement a FIFO

scheduling algorithm and keep the modification as minimum, which function in

scheduler.c is the one that you should modify? Briefly describe how you would

modify this function.

Question 10.

In this implementation, the scheduler only changes threads when the time quantum

expires.  Briefly explain how you would use an additional signal to allow the

scheduler to change threads in the middle of a time quantum.  In what situations

would this be useful?

MACOSX/assign3/assign3_part2/._Makefile

/in /by

__MACOSX/._assign3

assign3/.DS_Store

__MACOSX/assign3/._.DS_Store

assign3/assign3_part2/list.c

#include <stdio.h> #include “list.h” /* list helper functions */ int list_size(thread_info_list *list) { int cnt = 0; if (!list) return -1; pthread_mutex_lock(&list->lock); list_elem *le = list->head; while (le) { cnt++; le = le->next; } pthread_mutex_unlock(&list->lock); return cnt; } int list_insert_head(thread_info_list *list, list_elem *new) { if (!list || !new) return -1; pthread_mutex_lock(&list->lock); new->next = list->head; new->prev = 0; if (new->next) { new->next->prev = new; } list->head = new; if (list->tail == 0) { list->tail = new; } pthread_mutex_unlock(&list->lock); return 0; } int list_insert_tail(thread_info_list *list, list_elem *new) { if (!list || !new) return -1; pthread_mutex_lock(&list->lock); new->prev = list->tail; new->next = 0; if (new->prev) { new->prev->next = new; } list->tail = new; if (list->head == 0) { list->head = new; } pthread_mutex_unlock(&list->lock); return 0; } int list_remove(thread_info_list *list, list_elem *old) { if (!old || !list) return -1; pthread_mutex_lock(&list->lock); if (old->next) { old->next->prev = old->prev; } if (old->prev) { old->prev->next = old->next; } if (list->tail == old) { list->tail = old->prev; } if (list->head == old) { list->head = old->next; } old->next = old->prev = 0; pthread_mutex_unlock(&list->lock); return 0; } void print_list(thread_info_list *list) { pthread_mutex_lock(&list->lock); list_elem *le = list->head; while (le) { printf(“0x%X,”, (unsigned int)le->info); le = le->next; } pthread_mutex_unlock(&list->lock); printf(“\n”); }

__MACOSX/assign3/assign3_part2/._list.c

assign3/assign3_part2/worker.c

#include <stdio.h> #include <errno.h> #include <stdlib.h> #include <string.h> #include <signal.h> #include “scheduler.h” /******************************************************************************* * * Implement these functions. * ******************************************************************************/ /* Handler for SIGTERM signal */ void cancel_thread() { printf(“Thread %u: terminating.\n”, (unsigned int)pthread_self()); /* signal that done in queue */ sem_post(&queue_sem); pthread_exit(NULL); } /* TODO: Handle the SIGUSR1 signal */ void suspend_thread() { printf(“Thread %u: suspending.\n”, (unsigned int)pthread_self()); /*add your code here to wait for a resume signal from the scheduler*/ printf(“Thread %u: resuming.\n”,(unsigned int) pthread_self()); } /******************************************************************************* * * * ******************************************************************************/ /* * waits to gain access to the scheduler queue. */ static int enter_scheduler_queue(thread_info_t *info) { /* * wait for available room in queue. * create a new list entry for this thread * store this thread info in the new entry. */ sem_wait(&queue_sem); list_elem *item = (list_elem*)malloc(sizeof(list_elem)); info->le = item; item->info = info; item->prev = 0; item->next = 0; list_insert_tail(&sched_queue, item); return 0; } /* * leaves the scheduler queue */ void leave_scheduler_queue(thread_info_t *info) { printf(“Thread %lu: leaving scheduler queue.\n”, info->thrid); /* * remove the given worker from queue * clean up the memory that we malloc’d for the list * clean up the memory that was passed to us */ list_remove(&sched_queue, info->le); free(info->le); free(info); } /* * Initialize thread, enter scheduling queue, and execute instructions. * arg is a pointer to thread_info_t */ void *start_worker(void *arg) { thread_info_t *info = (thread_info_t *) arg; float calc = 0.8; int j = 0; /* TODO: Block SIGALRM and SIGUSR2. */ /* TODO: Unblock SIGUSR1 and SIGTERM. */ /* compete with other threads to enter queue. */ if (enter_scheduler_queue(info)) { printf(“Thread %lu: failure entering scheduler queue – %s\n”, info->thrid, strerror(errno)); free (info); pthread_exit(0); } printf(“Thread %lu: in scheduler queue.\n”, info->thrid); suspend_thread(); while (1) { /* do some meaningless work… */ for (j = 0; j < 10000000; j++) { calc = 4.0 * calc * (1.0 – calc); } } }

__MACOSX/assign3/assign3_part2/._worker.c

assign3/assign3_part2/Makefile

CC = gcc CCOPTS = -c -g -Wall LINKOPTS = -g -pthread -Wall EXEC=scheduler OBJECTS=scheduler.o worker.o list.o smp5_tests.o testrunner.o all: $(EXEC) $(EXEC): $(OBJECTS) $(CC) $(LINKOPTS) -o $@ $^ -lrt %.o:%.c $(CC) $(CCOPTS) -o $@ $^ clean: – $(RM) $(EXEC) – $(RM) $(OBJECTS) – $(RM) *~ – $(RM) core.* test: scheduler – ./scheduler -test -f0 rr – killall -q -KILL scheduler; true pretty: indent *.c *.h -kr

__MACOSX/assign3/assign3_part2/._Makefile

assign3/assign3_part2/scheduler.h

#ifndef __SCHEDULER_H_ #define __SCHEDULER_H_ #include <pthread.h> #include <semaphore.h> #include “list.h” #define QUANTUM 1 /* typedefs */ typedef struct thread_info { pthread_t thrid; int quanta; list_elem* le; /*added for evalution bookkeeping*/ struct timespec suspend_time; struct timespec resume_time; long wait_time; long run_time; } thread_info_t; /* functions */ void *start_worker(void *); long time_difference(const struct timespec*, const struct timespec*); int smp5_main(int argc, const char** argv); /* shared variables */ extern sem_t queue_sem; /* semaphore for scheduler queue */ extern thread_info_list sched_queue; /* list of current workers */ #endif /* __SCHEDULER_H_ */

__MACOSX/assign3/assign3_part2/._scheduler.h

assign3/assign3_part2/smp5_tests.c

/*************** YOU SHOULD NOT MODIFY ANYTHING IN THIS FILE ***************/ #define _GNU_SOURCE #include <stdio.h> #undef _GNU_SOURCE #include <stdlib.h> #include <string.h> #include <unistd.h> #include <signal.h> #include <sys/types.h> #include <sys/wait.h> #include “testrunner.h” #include “list.h” #include “scheduler.h” #include “worker.h” //#define quit_if(cond) do {if (cond) exit(EXIT_FAILURE);} while(0) #define quit_if(cond) do {if (cond) {printf(“Line %d.”,__LINE__);exit(EXIT_FAILURE);}} while(0) void args_to_nums(int argc, const char **argv, int *num_workers, int *queue_size, int **quanta) { int i; quit_if(argc < 4); *num_workers = atoi(argv[1]); *queue_size = atoi(argv[2]); *quanta = malloc(*num_workers * sizeof(int)); quit_if(*quanta == NULL); for(i=3;i<argc;i++) quanta[0][i-3] = atoi(argv[i]); } void nums_to_args(int num_workers, int queue_size, int *quanta, int *argc, char ***argv) { int i; *argc = num_workers+3; *argv = malloc(*argc*sizeof(char *)); quit_if(*argv==NULL); argv[0][0] = “scheduler”; argv[0][1] = malloc(3*sizeof(char)); quit_if(argv[0][1]==NULL); sprintf(argv[0][1],”%d”,num_workers); argv[0][2] = malloc(3*sizeof(char)); quit_if(argv[0][2]==NULL); sprintf(argv[0][2],”%d”,queue_size); for(i=0;i<num_workers;i++) { argv[0][i+3] = malloc(3*sizeof(char)); quit_if(argv[0][i+3]==NULL); sprintf(argv[0][i+3],”%d”,quanta[i]); } argv[0][i+3]=NULL; } /* Prepare input, reroute file descriptors, and run the program. */ void run_test(int argc, const char **argv) { //int fork_pid = fork(); //if (fork_pid == 0) { /* Reroute standard file descriptors */ freopen(“smp5.out”, “w”, stdout); /* Run the program */ quit_if(smp5_main(argc, argv) != EXIT_SUCCESS); fclose(stdout); //} else if (fork_pid > 0) { //waitpid(fork_pid, 0, 0); //} else { //fprintf(stderr, “run_test: fork() error\n”); //} } int test_output(FILE *stream, int nw, int qs, int *q) { int queue_size, queue_index; int num_workers, worker_index; int rv, in_queue, term, susp; unsigned long *queue, *workers, tid, prev, newwork, dummyl; int *remaining, *quanta; char dummyc; float tot_wait, tot_run, ave_wait, ave_run; int my_run, my_wait; rv = fscanf(stream,”Main: running %d workers with queue size %d for quanta:\n”,&num_workers, &queue_size); quit_if(rv != 2 || num_workers != nw || queue_size != qs); queue = malloc(queue_size*sizeof(long)); workers = malloc(num_workers*sizeof(long)); quanta = malloc(num_workers*sizeof(int)); remaining = malloc(queue_size*sizeof(int)); for(worker_index=0;worker_index<num_workers;worker_index++) { quit_if(fscanf(stream, ” %d”, quanta+worker_index) != 1); quit_if(quanta[worker_index]!=q[worker_index]); } fscanf(stream,”\n”); for(worker_index=0;worker_index<num_workers;worker_index++) { quit_if(fscanf(stream, “Main: detaching worker thread %lu.\n”,workers+worker_index) != 1); } quit_if(fscanf(stream, “Main: waiting for scheduler %lu.\n”,&dummyl) != 1); for(;queue_index<queue_size;queue[queue_index++]=0); worker_index = queue_index=0; in_queue = 0; quit_if(fscanf(stream, “Scheduler: waiting for workers.%c”,&dummyc)!=1 || dummyc != ‘\n’); for(queue_index = 0;queue_index < queue_size && queue_index < num_workers;queue_index++) { quit_if(fscanf(stream, “Thread %lu: in scheduler queue.\n”,&tid)!= 1 || tid != workers[worker_index]); quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid)!= 1 || tid != workers[worker_index]); queue[queue_index]=tid; remaining[queue_index] = quanta[worker_index]; worker_index++; in_queue++; } my_run=0; my_wait = num_workers; queue_index = 0; term = susp = 0; while(worker_index < num_workers || in_queue > 0) { while(!queue[queue_index]) queue_index= (queue_index+1)%queue_size; quit_if(fscanf(stream, “Scheduler: scheduling.%c”,&dummyc)!=1 || dummyc != ‘\n’); quit_if(fscanf(stream, “Scheduler: resuming %lu.\n”,&tid) != 1); quit_if( tid != queue[queue_index]); if (prev == tid) { if(term) { quit_if(fscanf(stream, “Thread %lu: terminating.\n”,&tid) != 1 || tid != prev); } else if (susp){ quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid) != 1); quit_if( tid != prev); } quit_if(fscanf(stream, “Thread %lu: resuming.\n”,&tid) != 1); quit_if(tid != queue[queue_index]); } else { quit_if(fscanf(stream, “Thread %lu: resuming.\n”,&tid) != 1 || tid != queue[queue_index]); if(term) { if(queue_size == 1) quit_if(fscanf(stream, “Scheduler: waiting for workers.%c”,&dummyc)!=1 || dummyc!=’\n’); quit_if(fscanf(stream, “Thread %lu: terminating.\n”,&tid) != 1 || tid != prev); if (in_queue == queue_size) { quit_if(fscanf(stream, “Thread %lu: in scheduler queue.\n”,&tid)!=1||tid != newwork); quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid)!=1 || tid!=newwork); } } else if (susp && in_queue>1){ quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid) != 1); quit_if( tid != prev); prev = tid; } } quit_if(fscanf(stream, “Scheduler: suspending %lu.\n”,&tid) != 1); quit_if(tid != queue[queue_index]); if(!–remaining[queue_index]) { quit_if(fscanf(stream, “Thread %lu: leaving scheduler queue.\n”,&tid)!=1 || tid != queue[queue_index]); term = 1; if(worker_index < num_workers) { queue[queue_index] = workers[worker_index]; remaining[queue_index] = quanta[worker_index]; newwork = workers[worker_index]; worker_index++; if(queue_size == 1) { prev = tid; quit_if(fscanf(stream, “Scheduler: waiting for workers.%c”,&dummyc)!=1 || dummyc!=’\n’); quit_if(fscanf(stream, “Thread %lu: terminating.\n”,&tid) != 1 || tid != prev); quit_if(fscanf(stream, “Thread %lu: in scheduler queue.\n”,&tid)!= 1 || tid != newwork); quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid)!= 1 || tid != newwork); term = 0; susp = 0; my_wait++; } } else { queue[queue_index] = 0; in_queue–; } } else { term = 0; susp = 1; } prev = tid; my_run++; my_wait += in_queue+(num_workers-worker_index)-1+term; queue_index= (queue_index+1)%queue_size; } quit_if(fscanf(stream, “Th%c”,&dummyc) != 1); if (dummyc==’r’) { quit_if(fscanf(stream, “ead %lu: terminating.\nThe”,&tid)!=1 || tid != prev); } quit_if(fscanf(stream, ” total wait time is %f seconds.\n”,&tot_wait) != 1); quit_if(fscanf(stream, “The total run time is %f seconds.\n”,&tot_run) != 1); quit_if(fscanf(stream, “The average wait time is %f seconds.\n”,&ave_wait) != 1); quit_if(fscanf(stream, “The average run time is %f seconds.\n”,&ave_run) != 1); if (dummyc==’e’) quit_if(fscanf(stream, “Thread %lu: terminating.\nThe”,&tid) != 1|| tid != prev); quit_if(abs(tot_wait-my_wait)>1); quit_if(abs(tot_run-my_run)>1); quit_if(abs(tot_wait/num_workers-ave_wait)>.5); quit_if(abs(tot_run/num_workers-ave_run)>.5); return 0; } int general_test(int argc, const char **argv) { FILE *f; int nw, qs, *q; run_test(argc,argv); f = fopen(“smp5.out”,”r”); args_to_nums(argc,argv,&nw,&qs,&q); test_output(f,nw,qs,q); return EXIT_SUCCESS; } int specific_test(int nw, int qs, int *q) { FILE *f; int argc; char **argv; nums_to_args(nw,qs,q,&argc,&argv); run_test(argc,(const char **)argv); f = fopen(“smp5.out”,”r”); test_output(f,nw,qs,q); return EXIT_SUCCESS; } int test_3_1_2_2_2() { int q[3] = {2,2,2}; return specific_test(3,1,q); } int test_2_2_2_2() { int q[2]={2,2}; return specific_test(2,2,q); } int test_5_7_1_2_1_2_1() { int q[5] = {1,2,1,2,1}; return specific_test(5,7,q); } int test_4_1_1_2_3_4() { int q[4] = {1,2,3,4}; return specific_test(4,1,q); } int test_3_3_4_3_2() { int q[3] = {4,3,2}; return specific_test(3,3,q); } /* * Main entry point for SMP% test harness */ int run_smp5_tests(int argc, const char **argv) { /* Tests can be invoked by matching their name or their suite name * or ‘all’ */ testentry_t tests[] = { {“test_3_1_2_2_2”, “rr”, test_3_1_2_2_2}, {“test_2_2_2_2”, “rr”, test_2_2_2_2}, {“test_5_7_1_2_1_2_1”, “rr”, test_5_7_1_2_1_2_1}, {“test_4_1_1_2_3_4”, “rr”, test_4_1_1_2_3_4}, {“test_3_3_4_3_2”, “rr”, test_3_3_4_3_2}, {“general”, “gen”, general_test} }; int result = run_testrunner(argc, argv, tests, sizeof(tests) / sizeof(testentry_t)); unlink(“smp5.out”); return result; } /* The real main function. */ int main(int argc, const char **argv) { if (argc > 1 && !strcmp(argv[1], “-test”)) { return run_smp5_tests(argc – 1, argv + 1); } else { return smp5_main(argc, argv); } }

__MACOSX/assign3/assign3_part2/._smp5_tests.c

assign3/assign3_part2/testrunner.h

/*************** YOU SHOULD NOT MODIFY ANYTHING IN THIS FILE ***************/ typedef int (*test_fp) (int, const char **); typedef struct { const char *name; const char *suite; test_fp test_function; } testentry_t; int run_testrunner(int argc, const char **argv, testentry_t * entries, int entry_count); void set_testrunner_default_timeout(int s); void set_testrunner_timeout(int s);

__MACOSX/assign3/assign3_part2/._testrunner.h

assign3/assign3_part2/worker.h

#ifndef __WORKER_H_ #define __WORKER_H_ void cancel_thread(); void suspend_thread(); void leave_scheduler_queue(thread_info_t*); #endif

__MACOSX/assign3/assign3_part2/._worker.h

assign3/assign3_part2/list.h

#ifndef __LIST_H_ #define __LIST_H_ #include <pthread.h> typedef struct list_elem { struct list_elem *prev; struct list_elem *next; void *info; } list_elem; typedef struct thread_info_list { list_elem *head; list_elem *tail; pthread_mutex_t lock; } thread_info_list; int list_size(thread_info_list *list); int list_insert_head(thread_info_list *list, list_elem *new); int list_insert_tail(thread_info_list *list, list_elem *new); int list_remove(thread_info_list *list, list_elem *new); void print_list(thread_info_list *list); #endif /* __LIST_H_ */

__MACOSX/assign3/assign3_part2/._list.h

assign3/assign3_part2/README.txt

SMP5: Scheduler with Signals ============================ This MP is a variation of SMP4. In the last MP, we built a simulated OS process scheduler. The scheduler can hold only a certain number of processes (workers) at one time. Once the process has been accepted into the scheduler, the scheduler decides in what order the processes execute. We implemented two scheduling algorithms: FIFO and Round Robin. In this MP, we are to simulate a time-sharing system by using signals and timers. We will only implement the Round Robin algorithm. Instead of using iterations to model the concept of “time slices” (as in the last MP), we use interval timers. The scheduler is installed with an interval timer. The timer starts ticking when the scheduler picks a thread to use the CPU which in turn signals the thread when its time slice is finished thus allowing the scheduler to pick another thread and so on. When a thread has completely finished its work it leaves the scheduler to allow a waiting thread to enter. Please note that in this MP, only the timer and scheduler send signals. The threads passively handle the signals without signaling back to the scheduler. The program takes a number of arguments. Arg1 determines the number of jobs (threads in our implementation) created; arg2 specifies the queue size of the scheduler. Arg3 through argN gives the duration (the required time slices to complete a job) of each job. Hence if we create 2 jobs, we should supply arg3 and arg4 for the required duration. You can assume that the autograder will always supply the correct number of arguments and hence you do not have to detect invalid input. Here is an example of program output, once the program is complete: % scheduler 3 2 3 2 3 Main: running 3 workers with queue size 2 for quanta: 3 2 3 Main: detaching worker thread 3075926960. Main: detaching worker thread 3065437104. Main: detaching worker thread 3054947248. Main: waiting for scheduler 3086416816. Scheduler: waiting for workers. Thread 3075926960: in scheduler queue. Thread 3075926960: suspending. Thread 3065437104: in scheduler queue. Thread 3065437104: suspending. Scheduler: scheduling. Scheduler: resuming 3075926960. Thread 3075926960: resuming. Scheduler: suspending 3075926960. Scheduler: scheduling. Scheduler: resuming 3065437104. Thread 3065437104: resuming. Thread 3075926960: suspending. Scheduler: suspending 3065437104. Scheduler: scheduling. Scheduler: resuming 3075926960. Thread 3075926960: resuming. Thread 3065437104: suspending. Scheduler: suspending 3075926960. Scheduler: scheduling. Scheduler: resuming 3065437104. Thread 3065437104: resuming. Thread 3075926960: suspending. Scheduler: suspending 3065437104. Thread 3065437104: leaving scheduler queue. Scheduler: scheduling. Scheduler: resuming 3075926960. Thread 3075926960: resuming. Thread 3065437104: terminating. Thread 3054947248: in scheduler queue. Thread 3054947248: suspending. Scheduler: suspending 3075926960. Thread 3075926960: leaving scheduler queue. Scheduler: scheduling. Scheduler: resuming 3054947248. Thread 3054947248: resuming. Thread 3075926960: terminating. Scheduler: suspending 3054947248. Scheduler: scheduling. Scheduler: resuming 3054947248. Thread 3054947248: suspending. Thread 3054947248: resuming. Scheduler: suspending 3054947248. Scheduler: scheduling. Scheduler: resuming 3054947248. Thread 3054947248: suspending. Thread 3054947248: resuming. Scheduler: suspending 3054947248. Thread 3054947248: leaving scheduler queue. Thread 3054947248: terminating. The total wait time is 12.062254 seconds. The total run time is 7.958618 seconds. The average wait time is 4.020751 seconds. The average run time is 2.652873 seconds. The goal of this MP is to help you understand (1) how signals and timers work, and (2) how to evaluate the performance of your program. You will first implement the time-sharing system using timers and signals. Then, you will evaluate the overall performance of your program by keeping track of how long each thread is idle, running, etc. The program will use these four signals: SIGALRM: sent by the timer to the scheduler, to indicate another time quantum has passed. SIGUSR1: sent by the scheduler to a worker, to tell it to suspend. SIGUSR2: sent by the scheduler to a suspended worker, to tell it to resume. SIGTERM: sent by the scheduler to a worker, to tell it to cancel. You will need to set up the appropriate handlers and masks for these signals. You will use these functions: clock_gettime pthread_sigmask pthread_kill sigaction sigaddset sigemptyset sigwait timer_settime timer_create Also, make sure you understand how the POSIX:TMR interval timer works. There are two ways you can test your code. You can run the built-in grading tests by running “scheduler -test -f0 rr”. This runs 5 tests, each of which can be run individually. You can also test you program with specific parameters by running “scheduler -test gen …” where the ellipsis contains the parameters you would pass to scheduler. Programming =========== Part I: Modify the scheduler code (scheduler.c) ———————————————– We use the scheduler thread to setup the timer and handle the scheduling for the system. The scheduler handles the SIGALRM events that come from the timer, and sends out signals to the worker threads. Step 1. Modify the code in init_sched_queue() function in scheduler.c to initialize the scheduler with a POSIX:TMR interval timer. Use CLOCK_REALTIME in timer_create(). The timer will be stored in the global variable “timer”, which will be started in scheduler_run() (see Step 4 below). Step 2. Implement setup_sig_handlers(). Use sigaction() to install signal handlers for SIGALRM, SIGUSR1, and SIGTERM. SIGALRM should trigger timer_handler(), SIGUSR1 should trigger suspend_thread(), and SIGTERM should trigger cancel_thread(). Notice no handler is installed for SIGUSR2; this signal will be handled differently, in step 8. Step 3. In the scheduler_run() function, start the timer. Use timer_settime(). The time quantum (1 second) is given in scheduler.h. The timer should go off repeatedly at regular intervals defined by the timer quantum. In Round-Robin, whenever the timer goes off, the scheduler suspends the currently running thread, and tells the next thread to resume its operations using signals. These steps are listed in timer_handler(), which is called every time the timer goes off. In this implementation, the timer handler makes use of suspend_worker() and resume_worker() to accomplush these steps. Step 4. Complete the suspend_worker() function. First, update the info->quanta value. This is the number of quanta that remain for this thread to execute. It is initialized to the value passed on the command line, and decreases as the thread executes. If there is any more work for this worker to do, send it a signal to suspend, and update the scheduler queue. Otherwise, cancel the thread. Step 5. Complete the cancel_worker() function by sending the appropriate signal to the thread, telling it to kill itself. Step 6. Complete the resume_worker() function by sending the appropriate signal to the thread, telling it to resume execution. Part II: Modify the worker code (worker.c) —————————————— In this section, you will modify the worker code to correctly handle the signals from the scheduler that you implemented in the previous section. You need to modify the thread functions so that it immediately suspends the thread, waiting for a resume signal from the scheduler. You will need to use sigwait() to force the thread to suspend itself and wait for a resume signal. You need also to implement a signal handler in worker.c to catch and handle the suspend signals. Step 7. Modify start_worker() to (1) block SIGUSR2 and SIGALRM, and (2) unblock SIGUSR1 and SIGTERM. Step 8. Implement suspend_thread(), the handler for the SIGUSR1 signal. The thread should block until it receives a resume (SIGUSR2) signal. Part III: Modify the evaluation code (scheduler.c) ————————————————– This program keeps track of run time, and wait time. Each thread saves these two values regarding its own execution in its thread_info_t. Tracking these values requires also knowing the last time the thread suspended or resumed. Therefore, these two values are also kept in thread_info_t. See scheduler.h. In this section, you will implement the functions that calculate run time and wait time. All code that does this will be in scheduler.c. When the program is done, it will collect all these values, and print out the total and average wait time and run time. For your convenience, you are given a function time_difference() to compute the difference between two times in microseconds. Step 9. Modify create_workers() to initialize the various time variables. Step 10. Implement update_run_time(). This is called by suspend_worker(). Step 11. Implement update_wait_time(). This is called by resume_worker(). Questions ========== Question 1. Why do we block SIGUSR2 and SIGALRM in worker.c? Why do we unblock SIGUSR1 and SIGTERM in worker.c? Question 2. We use sigwait() and sigaction() in our code. Explain the difference between the two. (Please explain from the aspect of thread behavior rather than syntax). Question 3. When we use POSIX:TMR interval timer, we are using relative time. What is the alternative? Explain the difference between the two. Question 4. Look at start_worker() in worker.c, a worker thread is executing within an infinite loop at the end. When does a worker thread terminate? Question 5. When does the scheduler finish? Why does it not exit when the scheduler queue is empty? Question 6. After a thread is scheduled to run, is it still in the sched_queue? When is it removed from the head of the queue? When is it removed from the queue completely? Question 7. We’ve removed all other condition variables in SMP4, and replaced them with a timer and signals. Why do we still use the semaphore queue_sem? Question 8. What’s the purpose of the global variable “completed” in scheduler.c? Why do we compare “completed” with thread_count before we wait_for_queue() in next_worker()? Question 9. We only implemented Round Robin in this SMP. If we want to implement a FIFO scheduling algorithm and keep the modification as minimum, which function in scheduler.c is the one that you should modify? Briefly describe how you would modify this function. Question 10. In this implementation, the scheduler only changes threads when the time quantum expires. Briefly explain how you would use an additional signal to allow the scheduler to change threads in the middle of a time quantum. In what situations would this be useful?

__MACOSX/assign3/assign3_part2/._README.txt

assign3/assign3_part2/scheduler.c

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <errno.h> #include <time.h> #include <signal.h> #include “scheduler.h” #include “worker.h” /* * define the extern global variables here. */ sem_t queue_sem; /* semaphore for scheduler queue */ thread_info_list sched_queue; /* list of current workers */ static int quit = 0; static timer_t timer; static thread_info_t *currentThread= 0; static long wait_times; static long run_times; static int completed = 0; static int thread_count = 0; static void exit_error(int); /* helper function. */ static void wait_for_queue(); /******************************************************************************* * * Implement these functions. * ******************************************************************************/ /* * This function intializes the queue semaphore and the queue itself. */ /* * Update the worker’s current running time. * This function is called every time the thread is suspended. */ void update_run_time(thread_info_t *info) { /* TODO: implement this function */ } /* * Update the worker’s current waiting time. * This function is called every time the thread resumes. */ void update_wait_time(thread_info_t *info) { /* TODO: implement this function */ } static void init_sched_queue(int queue_size) { /* set up a semaphore to restrict access to the queue */ sem_init(&queue_sem, 0, queue_size); /* initialize the scheduler queue */ sched_queue.head = sched_queue.tail = 0; pthread_mutex_init(&sched_queue.lock, NULL); /* TODO: initialize the timer */ } /* * signal a worker thread that it can resume. */ static void resume_worker(thread_info_t *info) { printf(“Scheduler: resuming %lu.\n”, info->thrid); /* * TODO: signal the worker thread that it can resume */ /* update the wait time for the thread */ update_wait_time(info); } /*send a signal to the thread, telling it to kill itself*/ void cancel_worker(thread_info_t *info) { /* TODO: send a signal to the thread, telling it to kill itself*/ /* Update global wait and run time info */ wait_times += info->wait_time; run_times += info->run_time; completed++; /* Update schedule queue */ leave_scheduler_queue(info); if (completed >= thread_count) { sched_yield(); /* Let other threads terminate. */ printf(“The total wait time is %f seconds.\n”, (float)wait_times / 1000000); printf(“The total run time is %f seconds.\n”, (float)run_times / 1000000); printf(“The average wait time is %f seconds.\n”, (float)wait_times / 1000000 / thread_count); printf(“The average run time is %f seconds.\n”, (float)run_times / 1000000 / thread_count); } } /* * signals a worker thread that it should suspend. */ static void suspend_worker(thread_info_t *info) { int whatgoeshere = 0; printf(“Scheduler: suspending %lu.\n”, info->thrid); /*update the run time for the thread*/ update_run_time(info); /* TODO: Update quanta remaining. */ /* TODO: decide whether to cancel or suspend thread */ if(whatgoeshere) { /* * Thread still running: suspend. * TODO: Signal the worker thread that it should suspend. */ /* Update Schedule queue */ list_remove(&sched_queue,info->le); list_insert_tail(&sched_queue,info->le); } else { /* Thread done: cancel */ cancel_worker(info); } } /* * this is the scheduling algorithm * pick the next worker thread from the available list * you may need to add new information to the thread_info struct */ static thread_info_t *next_worker() { if (completed >= thread_count) return 0; wait_for_queue(); printf(“Scheduler: scheduling.\n”); /* return the thread_info_t for the next thread to run */ return sched_queue.head->info; } void timer_handler() { thread_info_t *info = 0; /* once the last worker has been removed, we’re done. */ if (list_size(&sched_queue) == 0) { quit = 1; return; } /*suspend the current worker*/ if (currentThread) suspend_worker(currentThread); //resume the next worker info = next_worker(); /* Update currentThread */ currentThread = info; if (info) resume_worker(info); else quit = 1; } /* * Set up the signal handlers for SIGALRM, SIGUSR1, and SIGTERM. * TODO: Implement this function. */ void setup_sig_handlers() { /* Setup timer handler for SIGALRM signal in scheduler */ /* Setup cancel handler for SIGTERM signal in workers */ /* Setup suspend handler for SIGUSR1 signal in workers */ } /******************************************************************************* * * * ******************************************************************************/ /* * waits until there are workers in the scheduling queue. */ static void wait_for_queue() { while(!list_size(&sched_queue)) { printf(“Scheduler: waiting for workers.\n”); sched_yield(); } } /* * runs at the end of the program just before exit. */ static void clean_up() { /* * destroy any mutexes/condition variables/semaphores that were created. * free any malloc’d memory not already free’d */ sem_destroy(&queue_sem); pthread_mutex_destroy(&sched_queue.lock); } /* * prints the program help message. */ static void print_help(const char *progname) { printf(“usage: %s <num_threads> <queue_size> <i_1, i_2 … i_numofthreads>\n”, progname); printf(“\tnum_threads: the number of worker threads to run\n”); printf(“\tqueue_size: the number of threads that can be in the scheduler at one time\n”); printf(“\ti_1, i_2 …i_numofthreads: the number of quanta each worker thread runs\n”); } /* * prints an error summary and exits. */ static void exit_error(int err_num) { fprintf(stderr, “failure: %s\n”, strerror(err_num)); exit(1); } /* * creates the worker threads. */ static void create_workers(int thread_count, int *quanta) { int i = 0; int err = 0; for (i = 0; i < thread_count; i++) { thread_info_t *info = (thread_info_t *) malloc(sizeof(thread_info_t)); info->quanta = quanta[i]; if ((err = pthread_create(&info->thrid, NULL, start_worker, (void *)info)) != 0) { exit_error(err); } printf(“Main: detaching worker thread %lu.\n”, info->thrid); pthread_detach(info->thrid); /* TODO: initialize the time variables for each thread for performance evalution*/ } } /* * runs the scheduler. */ static void *scheduler_run(void *unused) { wait_for_queue(); /* TODO: start the timer */ /*keep the scheduler thread alive*/ while( !quit ) sched_yield(); return NULL; } /* * starts the scheduler. * returns 0 on success or exits program on failure. */ static int start_scheduler(pthread_t *thrid) { int err = 0; if ((err = pthread_create(thrid, NULL, scheduler_run, 0)) != 0) { exit_error(err); } return err; } /* * reads the command line arguments and starts the scheduler & worker threads. */ int smp5_main(int argc, const char** argv) { int queue_size = 0; int ret_val = 0; int *quanta,i; pthread_t sched_thread; /* check the arguments. */ if (argc < 3) { print_help(argv[0]); exit(0); } thread_count = atoi(argv[1]); queue_size = atoi(argv[2]); quanta = (int*)malloc(sizeof(int)*thread_count); if (argc != 3 + thread_count) { print_help(argv[0]); exit(0); } for ( i = 0; i < thread_count; i++) quanta[i] = atoi(argv[i+3]); printf(“Main: running %d workers with queue size %d for quanta:\n”, thread_count, queue_size); for ( i = 0; i < thread_count; i++) printf(” %d”, quanta[i]); printf(“\n”); /*setup the sig handlers for scheduler and workers*/ setup_sig_handlers(); /* initialize anything that needs to be done for the scheduler queue. */ init_sched_queue(queue_size); /* creates a thread for the scheduler. */ start_scheduler(&sched_thread); /* creates the worker threads and returns. */ create_workers(thread_count, quanta); /* wait for scheduler to finish */ printf(“Main: waiting for scheduler %lu.\n”, sched_thread); pthread_join(sched_thread, (void **) &ret_val); /* clean up our resources */ clean_up(); /* this will wait for all other threads */ pthread_exit(0); } long time_difference(const struct timespec *time1, const struct timespec *time2) { return (time1->tv_sec – time2->tv_sec) * 1000000 + (time1->tv_nsec – time2->tv_nsec) / 1000; }

__MACOSX/assign3/assign3_part2/._scheduler.c

assign3/assign3_part2/testrunner.c

/*************** YOU SHOULD NOT MODIFY ANYTHING IN THIS FILE ***************/ /* A simple testrunner framework Original Author: L. Angrave */ #include <sys/types.h> #include <sys/wait.h> #include <errno.h> #include <stdio.h> #include <signal.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <unistd.h> #include “testrunner.h” /* Constants */ #define false (0) #define true (1) #define test_killed (2) /* defaults */ static int default_timeout_seconds = 15; static int timeout_seconds; void set_testrunner_default_timeout(int s) { assert(s > 0); default_timeout_seconds = s; } void set_testrunner_timeout(int s) { assert(s > 0); timeout_seconds = s; } /* — Helper macros and functions — */ #define DIE(mesg) {fprintf(stderr,”\n%s(%d):%s\n”,__fname__,__LINE__,mesg); exit(1);} static int eql(const char *s1, const char *s2) { return s1 && s2 && !strcmp(s1, s2); } /* Callback function for qsort on strings */ static int mystrcmp(const void *p1, const void *p2) { return eql((const char *) p1, (const char *) p2); } /* Stats of all tests run so far */ typedef struct { int ran, passed, failed; } stats_t; /* — Signal handlers — */ static pid_t child_pid; static int sent_child_timeout_kill_signal; static void kill_child_signal_handler(intsigno) { if (!child_pid) return; char m[] = “-Timeout(Killing test process)-“; write(0, m, sizeof(m) – 1); kill(child_pid, SIGKILL); sent_child_timeout_kill_signal = 1; } /* Internal function to run a test as a forked child. The child process is terminated if it runs for more than a few seconds */ static int invoke_test_with_timelimit(testentry_t * test, int redirect_stdouterr, int argc, const char **argv) { char fname[255]; int wait_status; pid_t wait_val; struct sigaction action; assert(!child_pid); assert(test && test->test_function && test->name); set_testrunner_timeout(default_timeout_seconds); errno = 0; child_pid = fork(); if (child_pid == -1) { fprintf(stderr, “-fork failed so running test inline-“); return test->test_function(argc, argv); } if (child_pid == 0) { if (redirect_stdouterr) { snprintf(fname, (int) sizeof(fname), “stdout-%s.txt”, test->name); fname[sizeof(fname) – 1] = 0; freopen(fname, “w”, stdout); memcpy(fname + 3, “err”, 3); freopen(fname, “w”, stderr); } exit(test->test_function(argc, argv)); } else { wait_status = -1; sigemptyset(&action.sa_mask); action.sa_handler = kill_child_signal_handler; sigaction(SIGALRM, &action, NULL); sent_child_timeout_kill_signal = 0; alarm(timeout_seconds); wait_val = waitpid(child_pid, &wait_status, 0); int child_exited_normally = WIFEXITED(wait_status); int child_exit_value = WEXITSTATUS(wait_status); int child_term_by_signal = WIFSIGNALED(wait_status); int child_term_signal = WTERMSIG(wait_status); if (child_term_by_signal) { fprintf(stderr, “testrunner:Test terminated by signal %d\n”, child_term_signal); fprintf(stderr, “testrunner:waitpid returned %d (child_pid=%d,wait_status=%d)”, wait_val, child_pid, wait_status); } if (child_pid != wait_val) fprintf(stderr, “testrunner: strange… wait_val != child_pid\n”); int passed = (child_pid == wait_val) && (child_exit_value == 0) && (child_exited_normally != 0); alarm(0); kill(child_pid, SIGKILL); child_pid = 0; return sent_child_timeout_kill_signal ? test_killed : passed ? 0 : 1; } } /* * run a test and update the stats. The main guts of this functionality is provided by invoke_test_with_timelimit * This outer wrapper updates thes output and statistics before and after running the test. */ static int run_one_test(stats_t * stats, testentry_t * test, int redirect_stdouterr, int argc, const char **argv) { int test_result; assert(stats && test->name && argc > 0 && argv && *argv); stats->ran++; stats->failed++; printf(“%2d.%-20s:”, stats->ran, test->name); fflush(stdout); test_result = invoke_test_with_timelimit(test, redirect_stdouterr, argc, argv); if (test_result == 0) { stats->failed–; stats->passed++; } printf(“:%s\n”, (test_result == 0 ? “pass” : test_result == 2 ? “TIMEOUT * ” : “FAIL *”)); return test_result != 0; } /* Help functionality to print out sorted list of test names and suite names */ static void print_targets(testentry_t tests[], int count) { const char **array; const char *previous; int i; array = (const char **) calloc(sizeof(const char *), count); /* Sort the test names and print unique entries */ for (i = 0; i < count; i++) array[i] = tests[i].name; qsort(array, count, sizeof(array[0]), mystrcmp); printf(“\nValid tests : all”); for (i = 0, previous = “”; i < count; i++) if (!eql(previous, array[i])) printf(” %s”, (previous = array[i])); /* Sort the suite names and print unique entries */ for (i = 0; i < count; i++) array[i] = tests[i].suite; qsort(array, count, sizeof(array[0]), mystrcmp); printf(“\nValid suites:”); for (i = 0, previous = “”; i < count; i++) if (!eql(previous, array[i])) printf(” %s”, (previous = array[i])); printf(“\n”); } /* * Main entry point for test harness */ int run_testrunner(int argc, const char **argv, testentry_t tests[], int test_count) { const char *test_name, *target; int i; stats_t stats; int target_matched, max_errors_before_quit, redirect_stdouterr; memset(&stats, 0, sizeof(stats)); max_errors_before_quit = 1; redirect_stdouterr = 0; assert(tests != NULL); assert(test_count > 0); assert(argc > 0 && argv && *argv); while (true) { target = argc > 1 ? argv[1] : “”; assert(target); if (*target != ‘-‘) break; argc–; argv++; if (target[1] == ‘f’ && target[2]) max_errors_before_quit = atoi(target + 1); else if (target[1] == ‘r’) redirect_stdouterr = 1; } target_matched = false; for (i = 0; i < test_count && (max_errors_before_quit < 1 || stats.failed != max_errors_before_quit); i++) { test_name = tests[i].name; assert(test_name); assert(tests[i].suite); assert(tests[i].test_function); if (eql(target, test_name) || eql(target, “all”) || eql(target, tests[i].suite)) { if (!target_matched) printf(“Running tests…\n”); target_matched = true; run_one_test(&stats, &tests[i], redirect_stdouterr, argc – 1, argv + 1); } } if (!target_matched) { fprintf(stderr, “Test ‘%s’ not found”, (strlen(target) > 0 ? target : “(empty)”)); print_targets(tests, test_count); } else { printf(“\nTest Results:%d tests,%d passed,%d failed.\n”, stats.ran, stats.passed, stats.failed); } return stats.passed == stats.ran && target_matched ? 0 : 1; }

__MACOSX/assign3/assign3_part2/._testrunner.c

 

From Case Project 8-6: Lake Point Security Consulting:

/in /by

From Case Project 8-6: Lake Point Security Consulting:

“Lake Point Consulting Services (LPCS) provides security consulting and assurance services to over 500 clients across a wide range of enterprises in more than 20 states. A new initiative at LPCS is for each of its seven regional offices to provide internships to students who are in
their final year of the security degree program at the local college.

Pomodoro Fresco is a regional Italian pizza chain that provides free open wireless access to its customers and secure wireless access for its staff. However, Pomodoro Fresco is concerned about the security of the WLAN. They have asked LPCS to make a presentation about wireless attacks and their options for security. LPCS has asked you to help them in the presentation.

You will create a PowerPoint presentation for a fictitious company regarding wireless security. Carefully read the case project statement and step number 1 to ensure you cover all of the requested topics. Refer to Tech Republic Article about Powerpoint (Links to an external site.) for proper use of developing presentations in PowerPoint.  I expect to see:

  • a few bulleted items on at least one slide
  • at least one applicable graphics (charts, graphs, clipart) to make the presentation interesting
  • you should have an introduction slide
  • presentation about wireless attacks and their options for security
  • a conclusion slide
  • a slide for the list of your sources
  • total of 10 to 20 slides (includes Introduction slide, Conclusion slide and Sources slide)

 

Homework for modifying the syntactic analyzer for the attached compiler by adding to the existing grammar. The full grammar of the language is shown below.

/in /by

Homework for modifying the syntactic analyzer for the attached compiler by adding to the existing grammar. The full grammar of the language is shown below. The highlighted portions of the grammar show what you must either modify or add to the existing grammar.

function:

function_header {variable} body

function_header:

FUNCTION IDENTIFIER [parameters] RETURNS type ;

variable:

IDENTIFIER : type IS statement

parameters:

parameter {, parameter}

parameter:

IDENTIFIER : type

type:

INTEGER | REAL | BOOLEAN

body:

BEGIN statement END ;

statement: expression ; |

REDUCE operator {statement} ENDREDUCE ; |

IF expression THEN statement ELSE statement ENDIF ; |

CASE expression IS {case} OTHERS ARROW statement ; ENDCASE ;

operator:

ADDOP | MULOP

case:

WHEN INT_LITERAL ARROW statement

expression:

( expression ) |

REAL_LITERAL

NOT expression

expression binary_operator expression |

|

INT_LITERAL | IDENTIFIER

| BOOL_LITERAL |

binary_operator: ADDOP | MULOP | REMOP | EXPOP | RELOP | ANDOP | OROP

In the above grammar, the red symbols are nonterminals, the blue symbols are terminals and the black punctuation are EBNF metasymbols. The braces denote repetition 0 or more times and the brackets denote optional.

You must rewrite the grammar to eliminate the EBNF brace and bracket metasymbols and to incorporate the significance of parentheses, operator precedence and associativity for all operators. Among arithmetic operators the exponentiation operator has highest precedence following by the multiplying operators and then the adding operators. All relational operators have the same precedence. Among the binary logical operators, and has higher precedence than or. Of the categories of operators, the unary logical operator has highest precedence, the arithmetic operators have next highest precedence, followed by the relational operators and finally the binary logical operators. All operators except the exponentiation operator are left associative. The directives to specify precedence and associativity, such as %prec and %left, may not be used

Your parser should be able to correctly parse any syntactically correct program without any problem.

You must modify the syntactic analyzer to detect and recover from additional syntax errors using the semicolon as the synchronization token. To accomplish detecting additional errors an error production must be added to the function header and another to the variable declaration.

Your bison input file should not produce any shift/reduce or reduce/reduce errors. Eliminating them can be difficult so the best strategy is not introduce any. That is best achieved by making small incremental additions to the grammar and ensuring that no addition introduces any such errors.

An example of compilation listing output containing syntax errors is shown below:

1 — Multiple errors 2

  1. function main a integer returns real; Syntax Error, Unexpected INTEGER, expecting ‘:’
  2. b: integer is * 2; Syntax Error, Unexpected MULOP
  3. c: real is 6.0;
  4. begin
  5. if a > c then 8      b   3.0;

Syntax Error, Unexpected REAL_LITERAL, expecting ‘;’

9      else

10          b = 4.;

11      endif;

12 ;

Syntax Error, Unexpected ‘;’, expecting END

Lexical Errors 0

Syntax Errors 4

Semantic Errors 0

————————————————————

listing.h

// This file contains the function prototypes for the functions that produce the // compilation listing

enum ErrorCategories {LEXICAL, SYNTAX, GENERAL_SEMANTIC, DUPLICATE_IDENTIFIER,
UNDECLARED};

void firstLine();
void nextLine();
int lastLine();
void appendError(ErrorCategories errorCategory, string message);

———————————————————————————-

makefile

compile: scanner.o parser.o listing.o
g++ -o compile scanner.o parser.o listing.o
scanner.o: scanner.c listing.h tokens.h
g++ -c scanner.c

scanner.c: scanner.l
flex scanner.l
mv lex.yy.c scanner.c

parser.o: parser.c listing.h
g++ -c parser.c

parser.c tokens.h: parser.y
bison -d -v parser.y
mv parser.tab.c parser.c
mv parser.tab.h tokens.h

listing.o: listing.cc listing.h
g++ -c listing.cc

———————————————————-

parser.y

%{

#include

using namespace std;

#include “listing.h”

int yylex();
void yyerror(const char* message);

%}

%error-verbose

%token IDENTIFIER
%token INT_LITERAL

%token ADDOP MULOP RELOP ANDOP

%token BEGIN_ BOOLEAN END ENDREDUCE FUNCTION INTEGER IS REDUCE RETURNS

%%

function:
function_header optional_variable body ;
function_header:
FUNCTION IDENTIFIER RETURNS type ‘;’ ;

optional_variable:
variable |
;

variable:
IDENTIFIER ‘:’ type IS statement_ ;

type:
INTEGER |
BOOLEAN ;

body:
BEGIN_ statement_ END ‘;’ ;
statement_:
statement ‘;’ |
error ‘;’ ;
statement:
expression |
REDUCE operator reductions ENDREDUCE ;

operator:
ADDOP |
MULOP ;

reductions:
reductions statement_ |
;
expression:
expression ANDOP relation |
relation ;

relation:
relation RELOP term |
term;

term:
term ADDOP factor |
factor ;
factor:
factor MULOP primary |
primary ;

primary:
‘(‘ expression ‘)’ |
INT_LITERAL |
IDENTIFIER ;
%%

void yyerror(const char* message)
{
appendError(SYNTAX, message);
}

int main(int argc, char *argv[])
{
firstLine();
yyparse();
lastLine();
return 0;
}
————————————————————————

scanner

/* Compiler Theory and Design
Dr. Duane J. Jarc */

/* This file contains flex input file */

%{
#include
#include

using namespace std;

#include “listing.h”
#include “tokens.h”

%}

%option noyywrap

ws       [ \t\r]+
comment       \-\-.*\n
line       [\n]
id       [A-Za-z][A-Za-z0-9]*
digit       [0-9]
int       {digit}+
punc       [\(\),:;]
%%

{ws}       { ECHO; }
{comment}   { ECHO; nextLine();}
{line}       { ECHO; nextLine();}
“<”       { ECHO; return(RELOP); }
“+”       { ECHO; return(ADDOP); }
“*”       { ECHO; return(MULOP); }
begin       { ECHO; return(BEGIN_); }
boolean       { ECHO; return(BOOLEAN); }
end       { ECHO; return(END); }
endreduce   { ECHO; return(ENDREDUCE); }
function   { ECHO; return(FUNCTION); }
integer       { ECHO; return(INTEGER); }
is       { ECHO; return(IS); }
reduce       { ECHO; return REDUCE; }
returns       { ECHO; return(RETURNS); }
and       { ECHO; return(ANDOP); }
{id}       { ECHO; return(IDENTIFIER);}
{int}       { ECHO; return(INT_LITERAL); }
{punc}       { ECHO; return(yytext[0]); }
.       { ECHO; appendError(LEXICAL, yytext); }

%%
—————————————————————-

listing.cc

// Compiler Theory and Design
// Dr. Duane J. Jarc

// This file contains the bodies of the functions that produces the compilation
// listing

#include
#include

using namespace std;

#include “listing.h”

static int lineNumber;
static string error = “”;
static int totalErrors = 0;

static void displayErrors();

void firstLine()
{
lineNumber = 1;
printf(“\n%4d “,lineNumber);
}

void nextLine()
{
displayErrors();
lineNumber++;
printf(“%4d “,lineNumber);
}

int lastLine()
{
printf(“\r”);
displayErrors();
printf(” \n”);
return totalErrors;
}
void appendError(ErrorCategories errorCategory, string message)
{
string messages[] = { “Lexical Error, Invalid Character “, “”,
“Semantic Error, “, “Semantic Error, Duplicate Identifier: “,
“Semantic Error, Undeclared ” };

error = messages[errorCategory] + message;
totalErrors++;
}

void displayErrors()
{
if (error != “”)
printf(“%s\n”, error.c_str());
error = “”;
}
———————————————————-