This course is intended for professionals that lack formal education in computer science, and that are in search of a simple and practical guide to algorithmic complexity. The course explains the concepts in layman's terms, and teaches how to reason about the complexity of algorithms without requiring one to have an extensive mathematical skillset. This course can also be handy for revising complexity concepts or Big-O analysis before interviews. Finally, the content also scratches the surface of some advanced analysis topics to provide a more encompassing image of the complexity theory.

Big-O Notation For Coding Interviews and Beyond

Are all decision problems in the complexity class NP?

Are all decision problems in the complexity class NP?

Can optimization problems be in NP?

Travelling salesman problem is defined as a salesman planning to visit a bunch of cities to sell his merchandise. The salesman wants to cut costs and needs to follow a route which allows him to visit every city but at the same time is the shortest route among all possible routes. Is this problem in NP-complete?

Travelling salesman problem is defined as a salesman planning to visit a bunch of cities to sell his merchandise. The salesman wants to cut costs and needs to follow a route which allows him to visit every city but at the same time is the shortest route among all possible routes. Is this problem in NP-complete?

If P=NP is proven, will integer factorization be still in complexity class NP-intermediate? 

If P=NP is proven, will integer factorization be still in complexity class NP-intermediate?

NP-complete problems can't be solved at all?

NP-complete problems can’t be solved at all?

Questions to test understanding of P/NP problems.

Basics

Formal Analysis Tools

Recursive

Data-Structures

Amortized Analysis

Probabilistic Analysis

Complexity Theory

The End

Problem Set 6