Video Lectures on Discrete Mathematics and Algorithms

Stony Brook  [my Alma Mater 🙂 ]

IMSc (Indian Institute of Mathematical Sciences):

MIT

Advertisements

Finding two largest elements in an array

This is a very interesting problem indeed.

The problem comes in multiple flavors:

  • Find two largest elements in an array in 1.5n comparisons.
  • Find two largest elements in an array in n+log(n)−2 comparisons.
  • Prove that no algorithm for finding two largest elements in an array can do this in less than n+ log (n)−2 comparisons.
  • What is the fastest algorithm for finding three largest elements?

 

References:

Code:

Bentley’s Treatment of the Maximum Sum Subsequence Problem

I thoroughly enjoyed the treatment given to this problem by Jon Bentley.

In particular, the section on “Principles” was such an exciting read – it shows some of the tricks used in algorithm design :

  • Save state to avoid recomputation
  • Preprocess state into data structures 
  • Divide and conquer algorithms
  • Scanning algorithms
  • Cumulatives 
  • Lower bounds
  • Sorting (my humble addition to the list)

References:

K-means Clustering

One of my friends recently asked me about the K-means algorithm.

  • how does it work ?
  • what are the typical applications i.e. where/how is it used in the industry ?

In the discussion that followed, we ended up playing around with several visualizations available that do an awesome job of explaining this technique.

we also hacked around with some code from joel grus’  book (data science from scratch) to develop more intuition on the K-means algorithm.

Visualizations:

Code:

 

There are some very interesting insights which we got playing around with trying to use K-means to cluster an image containing different colors:

sample5

 

Balanced Ternary

I was solving this math problem which had to do with representing every Natural number as a summation/subtraction of distinct power of 3

Interestingly this led me to this branch of mathematics called ‘Balanced Ternary’. Check it out!

Exploration of this problem gave me interesting insights about base representation of a number, something that I have been keeping in the backburner for a long while now. Finally got a chance to follow up on this.

References:

Problem:

Code: