Prim's Algorithm Animation

For a given set of randomly distributed points in 2-dimensional space, we utilize the Prim's algorithm to find the minimum total distance from a randomly selected origin point (P_origin). The algorithm is written in C++, visualization is done via Python, video editing by Blender. Also, for those who want to run their algorithm for the same set of points in this video, you can download the input files here. Dropbox path:

 

Final minimum spanning tree snapshots for several random point distributions:

Bent Waveguide

Here, we demonstrate the propagation through bent waveguides with different bending radii. The thickness of all waveguides are same and let's denote as "d" here. Then we have 3 cases where the radius of bending is d, 2d or 3d. With the smaller radius, the leakage from the bending is stronger compared to the other ones.

Estimating Pi

Here, we look at the Archimedes' method to calculate/estimate the Pi number where simpler polygons are used to find the area of a unit circle. The video is inspired from a talk given by MIT Professor John Guttag within MITx - 6.00.2x.

Simple remedy on CLANG error: no member named * in namespace *

Given the following code snippet in C++, when it is compiled with gcc, there is no issue. However, when compiled using the clang, then we see the following error:

Compilation:

clang++ -std=c++14 -pedantic -Wall  main.cpp

Output:

main.cpp:12:18: error: no member named 'runtime_error' in namespace 'std'
      throw std::runtime_error("Cannot find the input file...");
            ~~~~~^
1 error generated.

Code snippet given the above error with Clang.

#include <fstream>
#include <iostream>

using namespace std;

int main() {

   ifstream input;
   input.open("test.txt");

   if (!input.is_open()){
      throw std::runtime_error("Cannot find the input file...");
   }

   input.close();

   return 0;
}

This is because clang cannot find the header file. Either it should be included or simply telling clang which header file to look at solves the problem. In this particular example, including the header file where runtime_error() is defined which is the #include is good enough. 

Sedona, Arizona trip - Caught by snow

While expecting to see the wonderful rock formations, we were caught in the snow. This was a bit surprising but the city still looked beautiful.

Fast C++ Solution to Huge Fibonacci number modulo m

This is a fast solution in C++ to Huge Fibonacci number modulo m question asked in the Algorithms course in UC San Diego Coursera course on Algorithms. It first calculates the Pisano period, then utilizes it to reduce the problem to a smaller size. The code also contains iterative solver to calculate Fibonacci number modulo m.

#include <iostream>
#include <vector>
using namespace std;

// This iteratively calculates the mod m of Fn, i.e. Fn % m [cost: O(n)]
template <typename T>
T calc_fibModm(T n, T m) {

  T fn=0, fn_minus1=1,fn_minus2=1;

  if (n==0)
      return 0;
  else if (n==1 || n==2)
      return 1;
  else {
     for (T i=2; i<n; i++){
      fn =( fn_minus1 % m + fn_minus2 % m) %m ;
      fn_minus2 = fn_minus1;
      fn_minus1 = fn;
     }
   }

  return fn;
}

template <typename T>
T findPeriod(T  n,T  m){ // Find the periodicity of Fibanacci series (i.e. Pisano period)

  vector<T > vMod;
  for (T i=0; i<n; i++){
    T modi = calc_fibModm(i,m);
    vMod.push_back(modi);

    if (i>2 && vMod[i] ==1 && vMod[i-1] == 0) {// this might be the start of a new periods as all new period start with 01 sequence

      // now calculate forward (i-2) new elements and check with the first set 
      // whether all elements are same (to establish periodicity)
      bool bAllOk= true;
      for (T j=i-1; j<2*i-3+1; j++){
          T modi_forward =  calc_fibModm(j,m);
          if (vMod[j-(i-1)] != modi_forward) {
            bAllOk=false;
            break;
          }
      }
      
      if (bAllOk) {
        T period = i-1;
        cout<<"n="<<n<<", m="<<m<<" --> period ="<<period<<endl;
        return period;
      }
    }
  } 
  // if reached here, that means the periodicty hasn't started yet, increase n
  string errStr="Not big enough n=("+to_string(n)+") to catch periodicity. Increase n to get periodicity";
  throw runtime_error(errStr);
  return -1;
}

template <typename T>
T get_fibonacci_huge(T n,T m) { // note that Fn % m = F_(n % period) % m

  if (m==1){
    return 0;
  } else { // general case
    T period = findPeriod(n,m);
    return calc_fibModm((n%period), m); 
  }
}

int main() {
    long long n, m;
    // try n=281621358815590 m=30524  output should be 11963
    std::cin >> n >> m;
    std::cout <<"Fn % m ="<< get_fibonacci_huge(n, m) << '\n';
}

Answer to MaxCounters question at Codility

Below is the Python solution to MaxCounters programming lesson in Codility. This gives the O(M+N) time complexity. The link to the question is here.

MaxCounters:
Calculate the values of counters after applying all alternating operations: increase counter by 1 and set value of all counters to current maximum

# Detected time complexity: O(N + M) %100 from codility

def solution(N,A):
 
 B=[0]*N

 baseValue =0;
 maxCount = 0; 
 for x in A:
   if 1 <= x <= N:
      B[x-1] = max(B[x-1],baseValue) + 1 
      maxCount=max(B[x-1],maxCount)
   else: 
      baseValue = maxCount

 for i in xrange(N):
    B[i]=max(B[i],baseValue)


 return B ;

Unix ls command - How to Exclude Certain Patterns using Wildcard?

Let's say you have a directory where there are too many files/folders having similar names and you want to exclude them during an ls operation. The command to use is as follows:

ls --ignore="PATTERN*"

Below is an example where there are folders named run_* and other files. The results obtained after typing plain ls and with the exclude options are shown below:

With the option: (Note the usage of the wildcard)

Travels of Ibn Jubayr from Granada, Spain to Mecca between 1183-1185 AD

Ibn Jubayr traveled almost 150 years before Ibn Battuta started his epic journey around the world. In his book, Ibn Battuta has used Ibn Jubayr's book as a reference for the cities he has already wrote about.


.... to be completed

References:

• Roland Broadhurst, "The Travels of Ibn Jubayr", Goodword Books, 2013 (first published in 1952)

Time Lapse from King's Mountain and Table Mountain tops

I had the chance to capture time lapse photos during two recent hikes. Here are the outcomes: King's Mountain: Here the camera is positioned westward towards the Pacific Ocean

Table Mountain: Overlooking the Columbia Gorge in a very cloudy morning. Once we got back to the trailhead, the clouds were completely gone.