This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.
All the features of this course are available for free. It does not offer a certificate upon completion.
제공자:
프린스턴 대학교
강의 계획 - 이 강좌에서 배울 내용
주
1완료하는 데 2시간 필요
Analysis of Algorithms
We begin by considering historical context and motivation for the scientific study of algorithm performance. Then we consider a classic example that illustrates the key ingredients of the process: the analysis of Quicksort. The lecture concludes with a discussion of some resources that you might find useful during this course.
4 videos (Total 76 min), 2 readings, 1 quiz
2개의 읽기 자료
Getting Started10m
Exercises from Lecture 110m
1개 연습문제
Analysis of Algorithms4m
주
2완료하는 데 2시간 필요
Recurrences
We begin this lecture with an overview of recurrence relations, which provides us with a direct mathematical model for the analysis of algorithms. We finish by examining the fascinating oscillatory behavior of the divide-and-conquer recurrence corresponding to the mergesort algorithm and the general "master theorem" for related recurrences.
5 videos (Total 71 min), 1 reading, 3 quizzes
1개의 읽기 자료
Exercises from Lecture 210m
3개 연습문제
Pop Quiz on Telescoping2m
Pop Quiz on the Master Theorem2m
Recurrences4m
주
3완료하는 데 2시간 필요
Generating Functions
Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.
5 videos (Total 84 min), 1 reading, 1 quiz
5개의 동영상
Counting with Generating Functions27m
Catalan Numbers14m
Solving Recurrences18m
Exponential Generating Functions7m
1개의 읽기 자료
Exercises from Lecture 310m
1개 연습문제
Generating Functions6m
주
4완료하는 데 2시간 필요
Asymptotics
Exact answers are often cumbersome, so we next consider a scientific approach to developing approximate answers that, again, mathematicians and scientists have used for centuries.
4 videos (Total 83 min), 1 reading, 1 quiz
4개의 동영상
Manipulating Expansions 19m
Asymptotics of Finite Sums 16m
Bivariate Asymptotics 28m
1개의 읽기 자료
Exercises from Lecture 410m
1개 연습문제
Asymptotics4m
4.7
6개의 리뷰최상위 리뷰
This course is more about mathematic than algorithms, it teaches how to solve tricky combinatorial problems
This is great course if you already done some algorithms courses and want to go deeper.
강사
Robert Sedgewick
William O. Baker *39 Professor of Computer ScienceComputer Science
프린스턴 대학교 정보
Princeton University is a private research university located in Princeton, New Jersey, United States. It is one of the eight universities of the Ivy League, and one of the nine Colonial Colleges founded before the American Revolution.
자주 묻는 질문
강의 및 과제를 언제 이용할 수 있게 되나요?
강좌에 등록하면 바로 모든 비디오, 테스트 및 프로그래밍 과제(해당하는 경우)에 접근할 수 있습니다. 상호 첨삭 과제는 이 세션이 시작된 경우에만 제출하고 검토할 수 있습니다. 강좌를 구매하지 않고 살펴보기만 하면 특정 과제에 접근하지 못할 수 있습니다.
Can I earn a certificate in this course?
No. As per Princeton University policy, no certificates, credentials, or reports are awarded in connection with this course.
궁금한 점이 더 있으신가요? 학습자 도움말 센터를 방문해 보세요.
Coursera는 세계 최고의 교육에 대한 보편적인 접근 기회를 제공하며,
최고의 대학 및 기관들과 제휴하여 온라인 강좌를 제공합니다.
© 2019 Coursera Inc. All rights reserved.
