关键信息
关于内容
This course is running for one last time and will retire soon. Last day to enroll is November 23rd.
How do you optimally encode a text file? How do you find shortest paths in a map? How do you design a communication network? How do you route data in a network? What are the limits of efficient computation?
This course, part of the Computer Science Essentials for Software Development Professional Certificate program, is an introduction to design and analysis of algorithms, and answers along the way these and many other interesting computational questions.
You will learn about algorithms that operate on common data structures, for instance sorting and searching; advanced design and analysis techniques such as dynamic programming and greedy algorithms; advanced graph algorithms such as minimum spanning trees and shortest paths; NP-completeness theory; and approximation algorithms.
After completing this course you will be able to design efficient and correct algorithms using sophisticated data structures for complex computational tasks.
- How to represent data in ways that allow you to access it efficiently in the ways you need to
- How to analyze the efficiency of algorithms
- How to bootstrap solutions on small inputs into algorithmic solutions on bigger inputs
- Solutions to several classic optimization problems
- How to critically analyze whether a locally optimal approach (greedy) can provide a globally optimal solution to a problem
前提
- Discrete Mathematics - sets, functions, relations; proofs, and proofs by induction; Boolean logic
- Basic probability
- Basic knowledge of Java
课程大纲
Week 1: Mathematical Preliminaries; Asymptotic analysis and recurrence relations; Sorting and Searching; Heaps and Binary Search Trees
Week 2: Algorithm Design Paradigms - Divide-and-Conquer algorithms, Dynamic Programming, Greedy Algorithms
Week 3: Graphs and graph traversals; minimum spanning trees; shortest paths
Week 4: Flows; NP-completeness; Approximation Algorithms
教师
Sampath Kannan
Henry Salvatori Professor and Department Chair, Computer and Information Science
University of Pennsylvania
内容设计师
平台
EdX est une plateforme d'apprentissage en ligne (dite FLOT ou MOOC). Elle héberge et met gratuitement à disposition des cours en ligne de niveau universitaire à travers le monde entier. Elle mène également des recherches sur l'apprentissage en ligne et la façon dont les utilisateurs utilisent celle-ci. Elle est à but non lucratif et la plateforme utilise un logiciel open source.
EdX a été fondée par le Massachusetts Institute of Technology et par l'université Harvard en mai 2012. En 2014, environ 50 écoles, associations et organisations internationales offrent ou projettent d'offrir des cours sur EdX. En juillet 2014, elle avait plus de 2,5 millions d'utilisateurs suivant plus de 200 cours en ligne.
Les deux universités américaines qui financent la plateforme ont investi 60 millions USD dans son développement. La plateforme France Université Numérique utilise la technologie openedX, supportée par Google.
