NP-Incompleteness
Most recent post:
Dynamic Time Warping
25 Jan 2022
Suppose we are given two discrete signals corresponding to the speech resulting from pronouncing a given sentence. They might have been pronounced by different people and in different intonations and speed, and we would like determine the similarity between these signals.
In this post we’ll discuss dynamic time warping, a technique that can be used to compare the similarity between time series allowing for small variances in the time scales. We’ll provide Python implementations of an exact algorithm $O(N^2)$ based on dynamic programming and an approximated one that runs in $O(N)$.
Sub-pages
- About
- Selected Posts
- Tags - Posts grouped by tags
Older Posts
- 25 Jan 2022 - Dynamic Time Warping
- 01 Jan 2022 - 2021 in Review
- 24 Dec 2021 - Revisiting Python: Modules
- 11 Dec 2021 - Pitch Detection via Cepstrum in Python
- 29 Nov 2021 - T-Digest in Python
- 16 Nov 2021 - A Simple Key Logger for MacOS
- 23 Oct 2021 - Cepstrum
- 09 Oct 2021 - Hermitian Functions
- 10 Sep 2021 - Z-Transform
- 01 Sep 2021 - Writing Posts
- 31 Aug 2021 - Discrete Time Filters
- 17 Aug 2021 - Maximum Non-Empty Intersection of Constraints
- 04 Aug 2021 - Paper Reading - Ray
- 31 Jul 2021 - Discrete Fourier Transforms
- 02 Jul 2021 - Namespace Jailing
- 26 Jun 2021 - Hilbert Spaces
- 13 May 2021 - Linear Predictive Coding in Python
- 19 Apr 2021 - Chroot Jailing
- 03 Apr 2021 - Source-Filter Model
- 06 Mar 2021 - Boyer–Moore Majority Vote Algorithm
- 20 Feb 2021 - Levinson Recursion
- 08 Feb 2021 - Linux Filesystems Overview
- 25 Jan 2021 - Viterbi Algorithm
- 09 Jan 2021 - Max Area Under a Histogram
- 01 Jan 2021 - 2020 in Review
- 26 Dec 2020 - Shor's Prime Factoring Algorithm
- 23 Dec 2020 - Quantum Phase Estimation
- 11 Dec 2020 - Number Factorization from Order-Finding
- 21 Nov 2020 - Quantum Fourier Transform
- 06 Nov 2020 - A Puzzling Election
- 11 Oct 2020 - The Deutsch-Jozsa Algorithm
- 09 Oct 2020 - Paper Reading - Latent Aspect Rating Analysis on Review Text Data
- 04 Sep 2020 - L-BFGS
- 31 Jul 2020 - Buddy Memory Allocation
- 11 Jul 2020 - From WordPress to Markdown
- 11 Jun 2020 - Huffman Coding
- 25 May 2020 - Shortest String From Removing Doubles
- 22 May 2020 - Review: Working Effectively With Legacy Code
- 24 Apr 2020 - CPU Cache
- 28 Mar 2020 - Browser Performance
- 07 Mar 2020 - Sockets
- 02 Feb 2020 - Python Coroutines
- 04 Jan 2020 - Observable
- 04 Jan 2020 - 2019 in Review
- 26 Dec 2019 - Python Type Hints
- 09 Nov 2019 - Aho-Corasick
- 30 Sep 2019 - Protein Design
- 06 Sep 2019 - Protein Folding Prediction
- 21 Jul 2019 - Content Delivery Network
- 01 Jul 2019 - Async Functions in JavaScript
- 10 Jun 2019 - Von Neumann Architecture
- 10 May 2019 - Constructing Trees from a Distance Matrix
- 12 Apr 2019 - Consistent Hashing
- 13 Mar 2019 - Rust Memory Management
- 22 Jan 2019 - DNA Assembly
- 01 Jan 2019 - 2018 in Review
- 26 Dec 2018 - De Bruijn Graphs and Sequences
- 26 Nov 2018 - Eulerian Circuits
- 05 Nov 2018 - Blockchain
- 01 Oct 2018 - Two-factor authentication
- 04 Sep 2018 - DNA Sequencing
- 20 Jul 2018 - Log Structured Merge Trees
- 24 Jun 2018 - Writing JavaScript using OCaml
- 04 Jun 2018 - Bulls and Cows
- 30 Apr 2018 - Cell biology and Programming
- 01 Apr 2018 - HyperLogLog in Rust
- 10 Feb 2018 - Paper Reading - F1: A Distributed SQL Database That Scales
- 20 Jan 2018 - CSS Layout
- 05 Jan 2018 - 2017 in Review
- 16 Dec 2017 - Generalized Tries in OCaml
- 16 Nov 2017 - Mutually Recursive Modules in OCaml
- 02 Oct 2017 - Polymorphic Recursion in OCaml
- 01 Sep 2017 - Numerical Representations as inspiration for Data Structures
- 06 Aug 2017 - Lazy Rebuilding
- 29 Jul 2017 - Monitoring System using Raspberry Pi
- 09 Jul 2017 - Eliminating Amortization
- 01 Jun 2017 - Notes on JavaScript Interpreters
- 22 May 2017 - Largest sets of subsequences in OCaml
- 01 May 2017 - OpenVis Conf 2017
- 27 Apr 2017 - Paper Reading - Spanner: Google's Globally-Distributed Database
- 19 Mar 2017 - Amortization and Persistence via Lazy Evaluation
- 01 Mar 2017 - Notes on Coursera's Functional Programming Principles in Scala
- 16 Jan 2017 - Domestic server using Raspberry Pi
- 01 Jan 2017 - 2016 in Review
- 21 Dec 2016 - Amortization Analysis
- 18 Nov 2016 - Streams and Lazy Evaluation in OCaml
- 05 Nov 2016 - US as an hexagonal map
- 23 Oct 2016 - Persistent Data Structures
- 06 Sep 2016 - Review: The Design of Everyday Things
- 04 Aug 2016 - Web Workers
- 18 Jul 2016 - OCaml Modules
- 27 Jun 2016 - Exploring OCaml
- 01 Jun 2016 - Review: Code Complete 2
- 13 Mar 2016 - Tree Ring Matching using the KMP Algorithm
- 15 Feb 2016 - Developing a project in Javascript
- 18 Jan 2016 - HTTP Basics
- 01 Jan 2016 - 2015 in Review
- 27 Nov 2015 - Software transactional memory in Haskell
- 26 Oct 2015 - Haskell Basic Networking
- 09 Oct 2015 - Notes on how browsers work
- 22 Aug 2015 - An interesting PHP Inheritance behavior
- 07 Aug 2015 - Notes on Zookeeper
- 19 Jul 2015 - JavaScript Promises
- 07 Jun 2015 - Notes on Javascript Memory Profiling in Google Chrome
- 14 May 2015 - Haskell Concurrent Programming
- 28 Apr 2015 - React.js introduction
- 08 Mar 2015 - Revisiting Python: Object Oriented Programming
- 23 Feb 2015 - Revisiting Python: Functions
- 20 Feb 2015 - Revisiting Python: Basic Types
- 29 Jan 2015 - Bloom Filters
- 01 Jan 2015 - 2014 in Review
- 30 Dec 2014 - Introduction to the R language for programmers
- 24 Nov 2014 - The PageRank algorithm
- 08 Oct 2014 - Haskell Profiling and Optimization
- 25 Aug 2014 - Introduction to d3.js
- 19 Jul 2014 - Monad Transformers
- 04 Jun 2014 - Supervised Machine Learning
- 18 May 2014 - Javascript Prototyping
- 14 Apr 2014 - The Paxos Protocol
- 01 Mar 2014 - Emacs Lisp Introduction
- 21 Jan 2014 - An Introduction to the Parsec Library
- 01 Jan 2014 - 2013 in Review
- 28 Dec 2013 - Turing Machines and Undecidability
- 11 Nov 2013 - Lawler and an Introduction to Matroids
- 30 Oct 2013 - An Introduction to Agda
- 01 Oct 2013 - Zippers and Comonads in Haskell
- 13 Aug 2013 - Totally Unimodular Matrix Recognition
- 28 Jul 2013 - Monads in Haskell - Part II
- 30 Jun 2013 - Network Matrices
- 26 May 2013 - Monads in Haskell - Part I
- 28 Apr 2013 - The Algorithm X and the Dancing Links
- 01 Jan 2013 - 2012 in Review
- 25 Sep 2012 - Skip Lists in Python
- 16 Sep 2012 - Flood it! An exact approach
- 09 Sep 2012 - Functors
- 02 Sep 2012 - Totally Unimodular Matrices
- 28 Aug 2012 - The Visitor pattern and Vtables in C++
- 18 Mar 2012 - Probabilistic Graphical Model Lecture Notes - Week 1
- 11 Mar 2012 - Lagrangean Relaxation - Practice
- 12 Feb 2012 - Pell Equation
- 05 Feb 2012 - Lagrangean Relaxation - Theory
- 01 Jan 2012 - 2011 in Review
- 01 Jan 2011 - 2010 in Review
- 23 Feb 2010 - Hypar
- 14 Feb 2010 - ACM ICPC World Finals 2010
- 01 Jan 2010 - 2009 in Review