Algorithm Design and Analysis

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

At a glance(Overview)

  • Institution: PennX
  • Subject: Computer Science
  • Level: Intermediate
  • Prerequisites:
    • Discrete Mathematics – sets, functions, relations; proofs, and proofs by induction; Boolean logic
    • Basic probability
    • Basic knowledge of Java

What you’ll learn(Outline)

  • 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

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

Testimonials

It was an eye-opening course. – James

It was an eye-opening course.

It was an eye-opening course.