CS501 Outline Fall2020 2021 PDF

Preview

Summary

Course Outline Fall 2020-2021...

Description

Lahore University of Management Sciences CS501 Applied Probability (Cross-listed as: EE 515/MATH 439)

Fall 2020-2021 Instructor Office Location Office Hours Class Location Email Telephone TAs TA Office Hours Course URL (if any)

Zartash Afzal Uzmi SBASSE 9-219A Tuesday 4-5pm (alternate times may be set up) Online: zoom ink will be shared over email sent via zambeel/LMS

[email protected] +92 42 3560 8202 Anusheh, Muneef, Kinza TBA LMS (https://lms.lums.edu.pk)

Course Basics Credit Hours Lecture(s) Tutorial (optional)

3 2 Per Week 1 Per Week

Course Distribution Core Elective Open for Student Category Close for Student Category

MS Computer Science Computer Science, Electrical Engineering and Math majors All None

M W 2:00-3:15pm

Duration Duration

75 mins 60 mins

COURSE DESCRIPTION This is an intermediate level course focusing on the application of probability theory to science and engineering disciplines. The first portion of the course reviews the basic probability theory with some examples chosen from science and engineering. Later portion of the course deals with moderately advanced topics that signify the use of probability theory in these disciplines. The topics covered in the course should help the students building a background for understanding and conducting research in computer and data sciences, estimation and learning, and other more general engineering problems. In particular, we will discuss random variables and expectations, joint and conditional distributions, random processes, queueing systems and Markov chains, confidence intervals, and prediction/learning/estimation theory. One important application area we will cover in the course is queueing theory. Why queuing theory? Any system (e.g., a web server, a customer service center) that has finite capacity and provides a service can potentially be modeled using queuing theory, which provides us with tools to predict system performance as well as design systems that achieve high performance. For example, using queuing theory we can answer questions such as “What is the average delay experienced by requests arriving at a web server?” and “Given demand and a size of a given hospital, how many doctors should be hired to ensure that the no patient waits for longer than 10mins with high, say 98 percent, probability?”). We will also provide a brief introduction to machine learning, another important application area that has gained recent popularity. Why machine learning? Computers are increasingly being used as data analysis tools to obtain insights from the enormous amounts of data that is being collected in a variety of fields (now referred to as “big data”). Probability theory is now used as one of the key methods for designing new algorithms to model such data, allowing, for example, a computer to make predictions about uncertain or new events. A use case would be to predict the weather tomorrow given weather data for past 10 years. A key goal of this course is to act as a bridge between the theoretical foundations of probability and its applications.

Lahore University of Management Sciences COURSE PREREQUISITE(S) Good preparation in calculus and exposure to basic combinatorics/probability concepts • COURSE OBJECTIVES • To teach the fundamentals of probability theory To introduce real-world applications of probability theory • To train students in applying probability concepts for solving real world problems • Teaching Methodology Synchronous (Live) teaching during the scheduled class times • Lecture videos will be made available online • Office hours will be open zoom (just like office walk ins) link for which will be shared in class (during the first • lecture) Learning Outcomes • A clear understanding of key probability concepts Development of ability to apply probability concepts to model and solve real-world problems • Familiarity with several real-world applications of probability • Grading Breakup and Policy Assignments: 2-3% each (approx. 8 homework assignments) Tests (announced): about 8-10 mini-tests, normally soon after the homeworks are due (approx. 75% of grade) (Some flexibility will be shown if online mode of teaching is causing hardship for you; as determined by the teaching staff) Mini-project (tentative): 10%

Examination Detail Midterm Exam

Final Exam

No Duration: N/A Preferred Date: N/A

No Duration: N/A Date: As set by the Registrar’s office

Textbook(s)/Supplementary Readings Suggested Textbooks (Go to class lectures for details) I. Introduction to Probability and Statistics for Engineers and Scientists by Sheldon Ross II. Introduction to Probability by Bertsekas and Tsitsiklis (2nd Edition, 2008) III. Introduction to Probability Models by Sheldon Ross (11th Edition, 2014) IV. Performance Modeling for Computer Systems by Mor Harchol Balter (2013) V. Probability and Random Processes for Electrical Engineering by Alberto Leon Garcia (3rd Edition, 2007) VI. Mining of Massive Datasets by Jure Leskovec, Anand Rajaraman, Jeffrey David Ullman (2nd Edition, 2014) VII. Machine Learning: A Probabilistic Perspective by Kevin Murphy (2012)

Lahore University of Management Sciences Session Basics of Probability 1 2 3 Probability Distributions 4 5 6 7 8 9 Advanced Probability 10 11 12 13 14 Applied Topics in Probability 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Topics

Recommended Readings

Course Overview, Sample Space, Events, Counting Conditional Probability, Bayes’ Rule, Law of Total Probability Independence, Conditional Independence

Go to class Go to class Go to class

Discrete Random Variables (RVs): Basic Concepts, PMF, Bernoulli RV & Common Discrete RVs (Binomial, Geometric, Poisson) Functions of RVs, Expectation, Variance Joint PMFs and Conditional Distributions Continuous RVs: Basic Concepts, PDF, CDF, Uniform RV Common Continuous RVs (Uniform, Exponential) Common Continuous RVs (Normal), The Central Limit Theorem

Go to class

Joint PDFs, and Conditional PDFs Sums of RVs, Correlation, and Covariance Inequalities (Markov, Chebychev, and Chernoff) Sample paths, Convergence of RVs & Law of Large Numbers (Weak and Strong) MIDTERM EXAM

Go to class Go to class Go to class Go to class

Confidence Intervals Survey Sampling Estimation of parameters Estimation of distribution Intro to Random Processes Bernoulli Process: Inter-arrival Times, Kth Arrival Time, Splitting and Merging Poisson Process: Inter-arrival Times, Kth Arrival Time, Splitting and Merging Finite-state Discrete-Time Markov Chains (DTMC) Finite-state DTMCs Wrap-up + Infinite-state DTMCs Infinite-state DTMC Wrap-up Continuous-Time Markov Chains (CTMC): Translating CTMCs to DTMCs CTMC: Interpretation of CTMCs, Examples of CTMCs Introduction to Queuing Theory, Kendall’s Notation, Little’s Law, M/M/1 Course Review Optional material (where do we go from here? Regression, Machine Learning)

Go to class Go to class Go to class Go to class Go to class Go to class Go to class Go to class Go to class Go to class Go to class Go to class Go to class Go to class Go to class

Go to class Go to class Go to class Go to class Go to class...