[MINI] Exponential Time Algorithms
Data Skeptic24 Nov 2017

[MINI] Exponential Time Algorithms

In this episode we discuss the complexity class of EXP-Time which contains algorithms which require $O(2^{p(n)})$ time to run. In other words, the worst case runtime is exponential in some polynomial of the input size. Problems in this class are even more difficult than problems in NP since you can't even verify a solution in polynomial time.

We mostly discuss Generalized Chess as an intuitive example of a problem in EXP-Time. Another well-known problem is determining if a given algorithm will halt in k steps. That extra condition of restricting it to k steps makes this problem distinct from Turing's original definition of the halting problem which is known to be intractable.

Denne episoden er hentet fra en åpen RSS-feed og er ikke publisert av Podme. Den kan derfor inneholde annonser.

Episoder(601)

Streetlight Outage and Crime Rate Analysis with Zach Seeskin

Streetlight Outage and Crime Rate Analysis with Zach Seeskin

This episode features a discussion with statistics PhD student Zach Seeskin about a project he was involved in as part of the Eric and Wendy Schmidt Data Science for Social Good Summer Fellowship.  Th...

18 Jul 201433min

[MINI] Experimental Design

[MINI] Experimental Design

This episode loosely explores the topic of Experimental Design including hypothesis testing, the importance of statistical tests, and an everyday and business example.

11 Jul 201415min

The Right (big data) Tool for the Job with Jay Shankar

The Right (big data) Tool for the Job with Jay Shankar

In this week's episode, we discuss applied solutions to big data problem with big data engineer Jay Shankar.  The episode explores approaches and design philosophy to solving real world big data busin...

7 Jul 201449min

[MINI] Bayesian Updating

[MINI] Bayesian Updating

In this minisode, we discuss Bayesian Updating - the process by which one can calculate the most likely hypothesis might be true given one's older / prior belief and all new evidence.

27 Jun 201411min

Personalized Medicine with Niki Athanasiadou

Personalized Medicine with Niki Athanasiadou

In the second full length episode of the podcast, we discuss the current state of personalized medicine and the advancements in genetics that have made it possible.

20 Jun 201457min

[MINI] p-values

[MINI] p-values

In this mini, we discuss p-values and their use in hypothesis testing, in the context of an hypothetical experiment on plant flowering, and end with a reference to the Particle Fever documentary and h...

13 Jun 201416min

Advertising Attribution with Nathan Janos

Advertising Attribution with Nathan Janos

A conversation with Convertro's Nathan Janos about methodologies used to help advertisers understand the affect each of their marketing efforts (print, SEM, display, skywriting, etc.) contributes to t...

6 Jun 20141h 16min

[MINI] type i / type ii errors

[MINI] type i / type ii errors

In this first mini-episode of the Data Skeptic Podcast, we define and discuss type i and type ii errors (a.k.a. false positives and false negatives).

30 Mai 201411min

Populært innen Vitenskap

fastlegen
tingenes-tilstand
jss
forskningno
rss-zahid-ali-hjelper-deg
rekommandert
rss-paradigmepodden
sinnsyn
liberal-halvtime
vett-og-vitenskap-med-gaute-einevoll
rss-overskuddsliv
kvinnehelsepodden
nordnorsk-historie
tidlose-historier
villmarksliv
grunnstoffene
rss-inn-til-kjernen-med-sunniva-rose
nevropodden
noen-har-snakket-sammen
fjellsportpodden