• Length:
    4 Weeks
  • Effort:
    6–8 hours per week
  • Price:

    FREE
    Add a Verified Certificate for $149 USD

  • Institution
    PennX
  • Subject:
    Computer Science
  • Level:
    Intermediate
  • Language:
    English
  • Video Transcript:
    English
  • Course Type:
    Self-paced on your time

Associated Programs:

Prerequisites

  • Discrete Mathematics - sets, functions, relations; proofs, and proofs by induction; Boolean logic
  • Basic probability
  • Basic knowledge of Java

Interested in this course for your Business or Team?

Train your employees in the most in-demand topics, with edX for Business.

Purchase now|Request Information

About this course

Skip About this course

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.

What you'll learn

Skip What you'll learn
  • 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

Syllabus

Skip Syllabus

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

Meet your instructors

University of Pennsylvania
Sampath Kannan
Henry Salvatori Professor and Department Chair, Computer and Information Science
University of Pennsylvania

Pursue a Verified Certificate to highlight the knowledge and skills you gain
$149 USD

View a PDF of a sample edX certificate

  • Official and Verified

    Receive an instructor-signed certificate with the institution's logo to verify your achievement and increase your job prospects

  • Easily Shareable

    Add the certificate to your CV or resume, or post it directly on LinkedIn

  • Proven Motivator

    Give yourself an additional incentive to complete the course

  • Support our Mission

    edX, a non-profit, relies on verified certificates to help fund free education for everyone globally

Interested in this course for your Business or Team?

Train your employees in the most in-demand topics, with edX for Business.

Purchase now|Request Information