About this Course

12,879 recent views

Shareable Certificate

Earn a Certificate upon completion

100% online

Start instantly and learn at your own schedule.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Intermediate Level

Basic knowledge of at least one programming language (loops, recursion, input/output). Basic math: proof by induction, proof by contradiction.

Approx. 19 hours to complete

English

Subtitles: English

Shareable Certificate

Earn a Certificate upon completion

100% online

Start instantly and learn at your own schedule.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Intermediate Level

Basic knowledge of at least one programming language (loops, recursion, input/output). Basic math: proof by induction, proof by contradiction.

Approx. 19 hours to complete

English

Subtitles: English

Offered by

Saint Petersburg State University logo

Saint Petersburg State University

Syllabus - What you will learn from this course

Week
1

Week 1

4 hours to complete

Point inclusion in a polygon

4 hours to complete
9 videos (Total 41 min)
9 videos
1.2 Problem statement4m
1.3 Testing point inclusion in a polygon3m
1.4 Algorithmic details3m
1.5 Degenerate cases2m
1.6 Putting everything together3m
1.7 Convex polygons4m
1.8 Testing point inclusion in a convex polygon6m
1.9 Star-shaped polyogns4m
3 practice exercises
Preliminaries20m
Geometric computing
Polygon hierarchy
Week
2

Week 2

4 hours to complete

Convex hulls

4 hours to complete
9 videos (Total 54 min)
9 videos
2.2 A naïve algorithm5m
2.3 Modified Graham's algorithm10m
2.4 Graham's scan6m
2.5 Jarvis march3m
2.6 Divide and conquer10m
2.7 Incremental algorithms3m
2.8 Quick hull3m
2.9 Chan's algorithm7m
3 practice exercises
Basic observations
Alternative algorithmic approaches
Refinements
Week
3

Week 3

4 hours to complete

Intersections

4 hours to complete
6 videos (Total 52 min)
6 videos
3.2 Plane sweep10m
3.3 Data structures6m
3.4 An algorithm for intersecting line segments11m
3.5 The algorithm complexity9m
3.6 Polygon intersection8m
3 practice exercises
Intersections and plane sweep
Implementation details
Intersecting polygons
Week
4

Week 4

4 hours to complete

Polygon triangulation

4 hours to complete
7 videos (Total 40 min)
7 videos
4.2 Traingulation: definition and properties5m
4.3 A naïve algorithm2m
4.4 Graph dual to a triangulation6m
4.5 An ear-cutting algorithm4m
4.6 Monotone polygons4m
4.7 Triangulating a monotone polygon11m
3 practice exercises
Polygon triangulations: basic properties
Dual graphs
Monotone polygons

Frequently Asked Questions

  • Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

  • When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

  • You will be eligible for a full refund until two weeks after your payment date, or (for courses that have just launched) until two weeks after the first session of the course begins, whichever is later. You cannot receive a refund once you’ve earned a Course Certificate, even if you complete the course within the two-week refund period. See our full refund policy.

  • Yes, Coursera provides financial aid to learners who cannot afford the fee. Apply for it by clicking on the Financial Aid link beneath the "Enroll" button on the left. You’ll be prompted to complete an application and will be notified if you are approved. Learn more.

  • This Course doesn't carry university credit, but some universities may choose to accept Course Certificates for credit. Check with your institution to learn more. Online Degrees and Mastertrack™ Certificates on Coursera provide the opportunity to earn university credit.

More questions? Visit the Learner Help Center.