# Algorithm Design and Analysis

Provided by University of Pennsylvania (PennX)
Intermediate
See prerequisites
6–8 hours
per week, for 4 weeks
Free

\$149 USD for graded exams and assignments, plus a certificate

Learn about the core principles of computer science: algorithmic thinking and computational problem solving.

## Before you start

• Discrete Mathematics - sets, functions, relations; proofs, and proofs by induction; Boolean logic
• Basic probability
• Basic knowledge of Java
Course opens: Jul 31, 2017
Course ends: Sep 16, 2019

## What you will 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
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

## Overview

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.

Sampath Kannan
Henry Salvatori Professor and Department Chair, Computer and Information Science
University of Pennsylvania
View Courses
This course is part of:

Earn a Professional Certificate in 2-4 months if courses are taken one at a time.

View the program
1. 24–32 hours of effort

Learn the fundamentals of object-oriented programming in Java, as well as best practices of modern software development.

2. 32–40 hours of effort

Learn how to select, apply, and analyze the most appropriate data representations in your code and design high quality software that is easy to understand and modify.

3. 24–32 hours of effort

Learn how to develop dynamic, interactive, and data-driven web apps using JavaScript.

Get started in computer science

Browse over 600 computer science courses
Of all edX learners:
73% are employed
Of all edX learners:
45% have children
Based on internal survey results
388,208 people are learning on edX today