CMSC57opomtr cince Week 1:Review of Algorithms and Probability Instructor:Shengyu Zhang
Instructor: Shengyu Zhang
First week Part l:About the course Part ll:About algorithms and complexity ▣Vhat are algorithms? Growth of functions What is the complexity of an algorithm a problem Part Ill:Review of probability Tail bounds
First week ◼ Part I: About the course ◼ Part II: About algorithms and complexity ❑ What are algorithms? ❑ Growth of functions ❑ What is the complexity of an algorithm / a problem ◼ Part III: Review of probability ❑ Tail bounds
Part I:About the course
Part I: About the course
Info Webpage: http://www.cse.cuhk.edu.hk/~syzhang/course/MScAlg15 Information (time and venue,TA,textbook,etc.) o Lecture slides aHomework Announcements Flavor: More math than programming
Info ◼ Webpage: http://www.cse.cuhk.edu.hk/~syzhang/course/MScAlg15 ❑ Information (time and venue, TA, textbook, etc.) ❑ Lecture slides ❑ Homework ❑ Announcements ◼ Flavor: ❑ More math than programming
Homework Homework assignments (100%). o No exam. 12 homework. You only need to complete 10. If you do more than 10,the 10 with the highest scores count
Homework ◼ Homework assignments (100%). ❑ No exam. ◼ 12 homework. ◼ You only need to complete 10. ❑ If you do more than 10, the 10 with the highest scores count
textbook No textbook. Lecture notes available before classes. ■ Some general references are listed in the course website as well
textbook ◼ No textbook. ◼ Lecture notes available before classes. ◼ Some general references are listed in the course website as well
Part II:About algorithms and complexity
Part II: About algorithms and complexity
A good example:driving directions n Suppose we want to drive from CUHK to Central.How to route? Let's ask Google
A good example: driving directions ◼ Suppose we want to drive from CUHK to Central. How to route? ◼ Let’s ask Google
What's good here: Step by step. 0 Each step is either turn left/right,or go straight for ..meters. An estimated time is also given. An algorithm is a computational procedure that has step-by-step instructions. It'll be good if an estimated time is given
◼ What’s good here: ❑ Step by step. ❑ Each step is either turn left/right, or go straight for … meters. ❑ An estimated time is also given. ◼ An algorithm is a computational procedure that has step-by-step instructions. ◼ It’ll be good if an estimated time is given
More on complexity Why time matters? Time is money！ Being late means 0 value ■Veather forecast. ■Homework. Running time:the number of elementary steps Assuming that each step only costs a small (or fixed)amount of time
More on complexity ◼ Why time matters? ❑ Time is money! ❑ Being late means 0 value ◼ Weather forecast. ◼ Homework. ◼ Running time: the number of elementary steps ❑ Assuming that each step only costs a small (or fixed) amount of time