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.
 

Boost Library Compilation Error (using CMake): undefined reference to `boost::iostreams::detail::

While using CMake to compile a simple c++ code containing boost library utilization, I encountered the following linkage problem:

main.cpp:(.text._ZN5boost9iostreams6detail9close_allINS0_21basic_gzip_compressorISaIcEEENS1_16linked_streambufIcSt11char_traitsIcEEEEEvRT_RT0_[void boost::iostreams::detail::close_all >, boost::iostreams::detail::linked_streambuf > >(boost::iostreams::basic_gzip_compressor >&, boost::iostreams::detail::linked_streambuf >&)]+0x18e): undefined reference to `boost::iostreams::detail::zlib_base::reset(bool, bool)'

collect2: ld returned 1 exit status

make[2]: *** [test.exe] Error 1

make[1]: *** [CMakeFiles/test.exe.dir/all] Error 2

make: *** [all] Error 2

For reference, the code I was trying to compile was the following ( a simple zipping and reading from a zipped file).:

#include <fstream>

#include <iostream>
#include <boost/iostreams/device/file.hpp>
#include <boost/iostreams/filtering_streambuf.hpp>
#include <boost/iostreams/filtering_stream.hpp>
#include <boost/iostreams/copy.hpp>
#include <boost/iostreams/filter/gzip.hpp>
using namespace std;
using namespace boost::iostreams;

int main()
{
   //The following code decompresses data from a file and writes it to standard output.
   ifstream file("hello.txt.gz", ios_base::in | ios_base::binary);
   filtering_streambuf<input> in;
   in.push(gzip_decompressor());
   in.push(file);
   boost::iostreams::copy(in, cout);

   boost::iostreams::filtering_ostream geometry;
   geometry.push(boost::iostreams::gzip_compressor(boost::iostreams::gzip::best_compression));

   // Generating a Zip file
   string filename = "example1.txt.gz";
   filtering_ostream out;
   unsigned int compressionLevel = boost::iostreams::gzip::best_compression;
   out.push(gzip_compressor(compressionLevel));

   out.push(file_sink(filename.c_str(), std::ios::binary));
   out << "This is a gz file\n";
   out << "This is the second line\n";
}

How I solved this problem is as follows: 

1)  I already had the following setting in the CMakeList.txt file:

SET(BOOST_DIR /usr/intel/pkgs/boost/1.54.0-gcc-4.7.2 CACHE PATH "Boost directory")


2)  Then, I added the bold and red lines below to have it compile without linkage error (the black lines already existed)

SET(BOOST_LIBDIR ${BOOST_DIR}/lib64)

SET(BOOST_LIB -L${BOOST_LIBDIR} boost_thread.a pthread.a  )

SET(BOOST_INCLUDE_DIR ${BOOST_DIR}/include )
LINK_DIRECTORIES(${BOOST_LIBDIR})
INCLUDE_DIRECTORIES(${BOOST_INCLUDE_DIR}  )
find_package(Boost COMPONENTS system filesystem iostreams regex  REQUIRED)
set (EXE test.exe)
add_executable(${EXE} main.cpp )
TARGET_LINK_LIBRARIES(${EXE} ${Boost_LIBRARIES} )

This made the trick and it worked without problems

Mansa Musa's Hajj Route (circa 1324)

--- will be updated later ---

References: 
1) P.J. Oliver, Mansa Musa and the Empire of Mali, CreateSpace Independent Publishing Platform (March 26, 2013) amazon

Map of Ibn Battuta's Africa trip including Mali circa 1337

FDTD simulations - Why Smooth Turn-on of Source is Needed?

In Finite-Difference Time-Domain (FDTD) simulations, source injection needs to be smoothly done in order to suppress the undesired high frequency components excited during turn on. To visualize this problem, we provide two cases with and without turn-on source injection. On the right simulation, total field/scattered field injection is done using the cosine excitation without any smooth turn-on which effectively mimics the step function operation. This results in the injection of high frequency components creating the ripples and fluctuations in the signal propagating in the domain. On the contrary, the left simulation has a smooth turn of by using a half Hanning window ramp-up which effectively acts as low pass filter for the injected source. As a result, the signal propagating in the domain is free of high frequency components, hence no ripples and fluctuations.

Nehalem Bay from the Neahkahnie Mountain [1,680' (512 m)]

Finally, we had an opportunity to have a family hike this summer. My son, Omer and my daughter, Meryem were with us as well. Omer was walking by himself and Meryem was comfortably carried in my back. After a pleasant  hour of walking starting from the south trailhead, we reached to the top of Neahkahnie Mountain. The view of the Nehalem Bay and the Pacific Ocean was stunning. Omer was happy to be at the top and couldn't help but took his selfie.

Mt. Hood Walk Up to 2915 m (9563 ft)

Seems so simple in the GPS track log. But in reality, it poses both physical and mental challenges to walk up to Mt. Hood. And definitely, it requires well studied planning from what to have in your backpack to what to eat before the start etc. After the attempt, I now realize that I wasn't well prepared for the challenge. My crampons were not fitting very well and at every step my mind was preoccupied whether they would get out of my shoes or not. The glasses I brought and started using after 2500 m where not fog proof. So, with the influence of sweat and breath warmth, the glasses became foggy making me half blind. After 2500 m, the wind was strong and the weather got really cold. I didn't have anything to cover my face and it got really cold. Eventually, I started to have headache which grew only bigger. I started to feel so sleepy and they told me that I was going through altitude sickness. Hence I needed to get down as quick as possible. I had to abort the climb. I was ~100 m away from the Hog's Back. Hopefully, next time with better preparation I can do better than this one.

Here are some photos from that day:
Mt. Hood right before the sunset as seen from Timberline Lodge. Getting ready for the midnight walk-up.

The walk-up starts around 1 am and the trail is already full of fellow hikers lighting up the trail.

Sun is rising behind the Mt. Hood. Since we are in the south-west side, we are left in the shade. Mt. Jefferson is seen at the background.

At 2915 m (9563 ft), altitude sickness kicks in. I have a very bad headache and drowsiness. Cannot continue further, need to turn back. This is the last point I was able to reach close to the Hog's Back.

Canyon right on the south of Hog's back.

Mt. Hood

Munra Point Hike (573 m -1879 ft)

Some photos

McNeil Point Hike at the Mt. Hood National Forest (2118 m ~ 6900 ft)

Here is the video of the last 100 meters of hike past the McNeil point towards Mt Hood from the Cathedral Ridge.



Photos:
Mt Hood from the North side. Glisan Glacier is on the left and Cathedral Ridge to Mt Hood is just in front of us. 

 Looking northwards. On the horizon, Mt. Adams can be seen.

 The valley on the south side of McNeil Point.

GPS log of our hike:

South Sister Mountain Ascent (3,157 m - 10,358 ft)

Our camping location for the night.

South Sister

Middle and North Sister from the South Sister Peak

Middle and North Sisters zoomed

Moraine Lake as seen from the South Sister peak

Beamforming by Phased Array Antennas

In this second video of the series on beamforming, we show the time domain wave propagation for two phased array antennas at different phase differences. Thanks to the constructive and destructive interferences, the main beam of the wave is steered towards angle of interest.

See also:
Phased Array Antenna Beam Steering Animation (Beamforming)
Beamforming by Phased Array Antennas 



Antenas en fase, Antenne réseau à commande de phase, フェーズドアレイレーダー, Фазированная антенная решётка, Фазована антенна решітка, 相位陣列, Szyki fazowane, Fázisvezérelt antennarács, מערך מופע, آرایه فازی

Selectively Removing the Polar Axis Labels in Matlab

In Matlab polar plots, the default is to show the whole 360 degrees of the whole graph and also include the polar labels up to 360. If some of the labels are desired not the displayed selectively, one remedy is to replace the corresponding strings with empty string. The procedure is pretty simple and I am showing it below.

First assume that we have such a code that plots the polar plot of a radiation pattern of an antenna array.

set(0,'defaultFigureColor',[1 1 1]) 

clear all; clc;

freq=1e9;
c=3e8;
lambda=c/freq;
T= 1/freq;
omega=2*pi*freq;
k=2*pi/lambda;

Ns=20;
ds=lambda/Ns;

Nt=25;
dt=T/Nt;
t=0:dt:(1*T);

R=(0*lambda):ds:(8*lambda);
Ntheta=240;
dtheta=2*pi/Ntheta;

theta=0:dtheta:(2*pi);


x=R.'*cos(theta);
y=R.'*sin(theta);

delta=(pi/3);

figure (10); clf; 
d = lambda/2;
A = [1 1 1 1 1 1 1]; % Amplitude of each array antenna
Fa=zeros(1,length(theta));
for i=0:(7-1)
    temp =  (A(i+1) * exp(-1i*i*delta + 1i*k*(i*d-3*d)*cos(theta)));
    Fa = Fa + temp;
end
Fa=abs(Fa);
kk=polar(theta,-Fa/max(Fa));   hold on; axis off;

 
The resulting plot is shown below where polar labels up to 330 degrees are shown.

Assume that we do not want to display the labels larger than 180 degrees, the remedy is simply to find the corresponding handle to that string and then replace it with empty string as shown below.

set(findall(gca,'String','210'),'String',' ')
set(findall(gca,'String','240'),'String',' ')
set(findall(gca,'String','270'),'String',' ')
set(findall(gca,'String','300'),'String',' ')
set(findall(gca,'String','330'),'String',' ')