Union-Find

The Union Find problem leads to an understanding of some very interesting data structures.

Capture

References:

Advertisements

Python sorted, itemgetter, stdin

I find it interesting how implementing a simple algorithm can teach you so many new things.

I was recently implementing the fractional knapsack problem

The interesting was – during implementation I got to learn some interesting things about Python.

 

Code:

 

git submodule

There are some interesting articles out there about git submodules

Tips:

  • cd into the submodule directory and do git status.
    • Many things just become clear that way!

References:

Video Lectures on Discrete Mathematics and Algorithms

Stony Brook  [my Alma Mater 🙂 ]

IMSc (Indian Institute of Mathematical Sciences):

MIT

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: