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:

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';
}