香港中文大学：《Design and Analysis of Algorithms》课程教学资源（PPT课件讲稿）Week 1 Introduction to the course

60:sysis of Algorithms Week 1:Introduction Instructor:Shengyu Zhang

Instructor: Shengyu Zhang

First week Part l:About the course Part ll:About algorithms ▣Vhat are algorithms? Why are they important to study? Part Ill:About complexity What is the complexity of an algorithm a problem Growth of functions

First week ◼ Part I: About the course ◼ Part II: About algorithms ❑ What are algorithms? ❑ Why are they important to study? ◼ Part III: About complexity ❑ What is the complexity of an algorithm / a problem ❑ Growth of functions

Part I:About the course

Part I: About the course

Tutorials Tutorials:Let's set the time now. Tuesday:5:30pm-6:15pm Webpage: http://www.cse.cuhk.edu.hk/~syzhang/course/Alg15 Information (time and venue,TA,textbook,etc.) Lecture slides oTutorials Homework Announcements

Tutorials ◼ Tutorials: Let’s set the time now. ❑ Tuesday: 5:30pm-6:15pm ◼ Webpage: http://www.cse.cuhk.edu.hk/~syzhang/course/Alg15 ❑ Information (time and venue, TA, textbook, etc.) ❑ Lecture slides ❑ Tutorials ❑ Homework ❑ Announcements

About the flavor of the course It's more of a math flavor than a programming one. You will need to write pseudo-code,but never C/Java/... You will design and analyze,think and prove (rather than code)

About the flavor of the course ◼ It’s more of a math flavor than a programming one. ◼ You will need to write pseudo-code, but never C/Java/… ◼ You will design and analyze, think and prove (rather than code)

Prerequisites Officially: CSC2110 DISCRETE MATHEMATICS 口CSC2100/ESTR2102 DATA STRUCTURES Effectively:Basic mathematical maturity functions,polynomial,exponential; a proof by induction; basic data structure operations (stack,queue,...) basic math manipulations... Note:As long as you'd like to learn it

Prerequisites ◼ Officially: ❑ CSC2110 DISCRETE MATHEMATICS ❑ CSC2100/ESTR2102 DATA STRUCTURES ◼ Effectively: Basic mathematical maturity ❑ functions, polynomial, exponential; ❑ proof by induction; ❑ basic data structure operations (stack, queue, …); ❑ basic math manipulations… ◼ Note: As long as you’d like to learn it

Homework,Exam Homework assignments (20%). ▣About4 assignments. ·Mid-term exam(30%). Final (50%)

Homework, Exam ◼ Homework assignments (20%). ❑ About 4 assignments. ◼ Mid-term exam (30%). ◼ Final (50%)

Homework Policy Discussions and googling on web are allowed in general But you have to write down the solution yourself And you fully understand what you write

Homework Policy ◼ Discussions and googling on web are allowed in general ◼ But you have to write down the solution yourself ◼ And you fully understand what you write

Zero tolerance for cheating/plagiarism Worse than a 0 score for this course;you may be out of dept/school/university. "The Chinese University of Hong Kong places very high importance on honesty in academic work submitted by students,and adopts a policy of zero tolerance on cheating and plagiarism.Any related offence will lead to disciplinary action including termination of studies at the University. ----Honesty in Academic Work (http://www.cuhk.edu.hk/policy/academichonesty)

Zero tolerance for cheating/plagiarism ◼ Worse than a 0 score for this course; you may be out of dept/school/university. ◼ “The Chinese University of Hong Kong places very high importance on honesty in academic work submitted by students, and adopts a policy of zero tolerance on cheating and plagiarism. Any related offence will lead to disciplinary action including termination of studies at the University.” ---- Honesty in Academic Work (http://www.cuhk.edu.hk/policy/academichonesty)

textbook ■Algorithms S.Dasgupta, C.H.Papadimitriou, Cbkjorithma U.V.Vazirani. McGraw-Hill Higher Education,2007. -Draft available at http://www.cs.berkel Sanjoy Dasgupta Christos Papadimitriou ey.edu/~vazirani/alg Umesh Vazirani orithms.html

textbook ◼ Algorithms S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, McGraw-Hill Higher Education, 2007. ◼ Draft available at http://www.cs.berkel ey.edu/~vazirani/alg orithms.html