香港中文大学：《Topics in Theoretical Computer Science》课程教学资源（PPT课件讲稿）Lecture 1 Review of basic concepts of algorithms and complexity, probability and tail bounds

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