Union-Find

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

References:

• https://www.coursera.org/learn/algorithms-part1/home/welcome
• https://vancexu.github.io/2015/07/21/intro-to-union-find-data-structure-exercise.html
• https://jznotebook.com/2014/02/15/algorithms-part-i-social-network-connectivity-with-union-find/

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.

• sorted
  • http://www.dr-chuck.com/csev-blog/2010/01/fun-python-syntax-operator-itemgetter-sorted-and-lambda-functions-oh-my/
• items, iteritems
  • https://stackoverflow.com/questions/10458437/what-is-the-difference-between-dict-items-and-dict-iteritems
• itemgetter
  • https://stackoverflow.com/questions/15371691/how-to-sort-a-dictionary-by-value-desc-then-by-key-asc
    • cool trick to sort by combination of ascending and descending
• sys.stdin
  • EOF literal for Windows is Control+Z  (not Control+D)

 

Code:

• fractional_knapsack.py

 

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:

• https://stackoverflow.com/questions/7993413/git-submodules-with-modified-and-untracked-content-why-and-how-to-remove-it
• https://gist.github.com/gitaarik/8735255
• https://www.techjini.com/blog/working-with-git-submodules/
• https://medium.com/fiverr-engineering/working-with-git-submodules-ec6210801e07
• https://longair.net/blog/2010/06/02/git-submodules-explained/

Indian National Math Olympiad

Seems like a lifetime ago, but I suddenly wanted to pull up some reference books I had used when preparing for INMO-2000 (class 10),  INMO-2002 (class 11) and INMO-2003 (class 12)

Resources:

• https://files.vipulnaik.com/olympiads/preparingforolympiads.pdf

Video Lectures on Discrete Mathematics and Algorithms

Stony Brook  [my Alma Mater 🙂 ]

• http://www3.cs.stonybrook.edu/~algorith/math-video/
• http://www3.cs.stonybrook.edu/~algorith/video-lectures/

IMSc (Indian Institute of Mathematical Sciences):

• https://www.youtube.com/watch?v=Lv3o4OOHG_w
• https://www.youtube.com/watch?v=fH0V-sQrBqE
  • Check out the channel! Some very cool videos

MIT

• https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/index.htm
• https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/index.htm
• https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/index.htm
• https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/index.htm

Python Break : Improve Your Python

I came across this very interesting series of blog posts. The authos (Jeff Knupp) discusses some nuances in Python

• Is Python call-by-value or call-by-reference? Neither.

• Improve Your Python: Python Classes and Object Oriented Programming

• Improve Your Python: Decorators Explained

 

There are a bunch of “Improve Your Python” articles in that blog. Check them out.

Code:

• python_scope.py

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:

• https://cs.stackexchange.com/questions/83022/find-largest-and-second-largest-elements-of-the-array/83056#83056
• https://math.stackexchange.com/questions/1601/lower-bound-for-finding-second-largest-element/1672#1672

Code:

• max_pairwise_product.py