Save for later

Approximation Algorithms

Many real-world algorithmic problems cannot be solved efficiently using traditional algorithmic tools, for example because the problems are NP-hard. The goal of this course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems. These techniques apply when we don't require the optimal solution to certain problems, but an approximation that is close to the optimal solution. We will see how to efficiently find such approximations. Prerequisites: In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know: - O-notation, Ω-notation, Θ-notation; how to analyze algorithms - Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc. - Basic probability theory: events, probability distributions, random variables, expected values etc. - Basic data structures: linked lists, stacks, queues, heaps - (Balanced) binary search trees - Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort - Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort, shortest paths) The material for this course is based on the course notes that can be found under the resources tab. We will not cover everything from the course notes. The course notes are there both for students who did not fully understand the lectures as well as for students who would like to dive deeper into the topics. The video lectures contain a few very minor mistakes. A list of these mistakes can be found under resources (in the document called "Errata"). If you think you found an error, report a problem by clicking the square flag at the bottom of the lecture or quiz where you found the error.

Get Details and Enroll Now

OpenCourser is an affiliate partner of Coursera.

Get a Reminder

Send to:
Rating Not enough ratings
Length 6 weeks
Starts Aug 28 (4 weeks ago)
Cost $49
From EIT Digital via Coursera
Instructor Mark de Berg
Download Videos On all desktop and mobile devices
Language English
Subjects Programming
Tags Computer Science Algorithms

Get a Reminder

Send to:

Similar Courses

Careers

An overview of related careers and their average salaries in the US. Bars indicate income percentile.

Presales Solution Executive - Atlanta GA or Dallas TX $64k

Solution Scientist $81k

Core Infrastructure Solution Specialist $89k

B2B Outside Sales Rep.-Business Solution Sales Specialist $103k

Solution Quality Analyst Lead $107k

Solution Architect GRC Manager $123k

Solution (BI) Architect Consultant $127k

Solution Specialist Consultant 2 $129k

ETL Solution Architect Lead $132k

Finance and Controlling Solution Architect $137k

Solution Architect with Mobility $152k

Senior Disaster Recovery Solution Architect $179k

Write a review

Your opinion matters. Tell us what you think.

Rating Not enough ratings
Length 6 weeks
Starts Aug 28 (4 weeks ago)
Cost $49
From EIT Digital via Coursera
Instructor Mark de Berg
Download Videos On all desktop and mobile devices
Language English
Subjects Programming
Tags Computer Science Algorithms

Similar Courses

Sorted by relevance

Like this course?

Here's what to do next:

  • Save this course for later
  • Get more details from the course provider
  • Enroll in this course
Enroll Now