Corner

Prim's Algorithm Animation

2017-03-10T18:47:00.000-08:00

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

2017-02-19T14:46:00.002-08:00

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

2017-02-19T14:43:00.003-08:00

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 *

2017-01-25T09:45:00.000-08:00

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

2016-12-28T18:01:00.000-08:00

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

2016-08-11T22:47:00.000-07:00

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

2016-06-30T16:30:00.002-07:00

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?

2015-09-02T08:55:00.001-07:00

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

2015-07-05T13:53:00.001-07:00

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

2015-02-23T14:24:00.001-08:00

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::

2015-02-17T16:44:00.001-08:00

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)

2015-01-28T21:00:00.000-08:00

--- 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?

2014-09-30T16:22:00.000-07:00

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)]

2014-09-28T20:23:00.001-07:00

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)

2014-09-19T08:56:00.001-07:00

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)

2014-09-15T09:33:00.002-07:00

Some photos

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

2014-09-08T12:41:00.001-07:00

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)

2014-07-31T12:49:00.000-07:00

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

2014-05-26T13:32:00.000-07:00

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

2014-05-17T10:39:00.003-07:00

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',' ')

On Suunto Ambit2 - Comparison with an Altitude Post

2014-04-30T16:59:00.002-07:00

After using my good old Sony GPS-CS3KA for more than 5 years mainly for the GPS track logs and photo-tagging, I finally upgraded to a more functional gadget, namely the Suunto Ambit2. While I wanted to keep the GPS logging alive, I also wanted to learn and record about my heart rate during long hikes (or any other sports) as well as immediate altitude and temperature info. After a little bit of research online, all fingers pointed to Suunto Ambit2 for increased functionality and exceptional battery life for extended adventures. Hence I decided to buy one and did so recently.

So far, I was able to use Ambit2 in several hikes (including our hike to the top of Mt. St. Helens) and bike rides and I can definitely say that GPS logs rendered by Ambit2 are much smoother than those of the Sony GPS-CS3KA. I plan to prepare a comparative post on the GPS log performances but for now I just have the following photo where I hold the Ambit2 next to the altitude post at the peak of King's Mountain in the Tillamook region of Oregon. Note that the post reads 3226 feet which is equal to 983.2 meters making it 5 meters off from the Ambit2's reading of 988 m (in other words Ambit2 reads 3241 ft whereas the post states 3226 feet). I cannot verify the accuracy of the post but 5 meter difference should be okay.

Edit: Approximately one month later, we were in the summit again and I had the chance to record the summit moments with a GoPro.

Mount St. Helens Hike (~8287 ft)

2014-03-29T20:58:00.000-07:00

Mount St. Helens Hike

This was my second attempt to hike up to the Mount St. Helen's peak which is at 2526 m (8287 ft). Almost exactly 1 year after the first ascent, this time our group was only 3 people which was a big reduction compared to last year's 8 people. Similar to our group, the parking lot at Marble Snow Park also had much less cars/campers compared to last year. For the record, the starting altitude was 886 m, so roughly 1500 m was ahead of us.

Being a smaller group, we were faster to pack and start the hike in the morning. It was 6.40 am when we were in the trail. After two hours clouds started to come over the St. Helens but later on they were completely gone. It took almost 6 hours to reach the top, the view was gorgeous. The smoke from the volcano was on. The view of Mount Rainier and Mount Adams was great. Here are some snapshots from the top:

What happens if the Source is Inside the PML region in FDTD simulations?

2014-02-18T23:43:00.000-08:00

In most of the FDTD simulations, perfectly matched layers play an indispensable role by their ability to absorb the incoming waves to mimic free space propagation. Triggering effect for this animation is the simple curiosity of what would happen if a point source was embedded in the PML rather than the inner domain.

To illustrate this, we utilized the uniaxial PML (UPML) formulation in a 2D FDTD scenario in homogeneous medium. We present three parallel simulations in which the point sources are located (left) deep inside the PML, (middle) slightly inside the PML and (right) outside but close to the PML. As can be observed, the PML performs great in eliminating portions of the wave impinging normal (or close to the normal) to the PML surface. But for high oblique incidences, the decaying of the wave is not completely satisfied.

For the leftmost case where the source is deeply embedded in the PML, the wave cannot propagate in the -x and +x directions and quickly decay in both directions. However, along the -/+ y directions, the PML acts as a waveguide. Thanks to the upper and lower PML regions, the wave inside the PML continues to decay along the -/+ y directions.

Total Field / Scattered Field (TF/SF) Implementation in FDTD

2014-02-18T23:41:00.000-08:00

Here, the plane wave excitation using the total field / scattered field (TF/SF) formulation in finite-difference time-domain (FDTD) algorithm is demonstrated. The interface between the "total" and "scattered" field regions is shown using the square box. The plane wave polarized in the -z direction (with respect to screen surface) is injected into the medium along the -y direction and then the scattering phenomena from two different scatterers (one metallic triangular wedge and another circular dielectric scatterer) are animated. The reflected wavefronts from the scatterers can explicitly be observed in the scattered field regions, whereas total field is observed within the box.

Keywords: Scattering from prism, 三角柱, Prisme triangulaire, 삼각기둥,முப்பட்டகம், Триъгълна призма

Group Velocity / Phase Velocity Animation - Case 2: Zero Group Velocity

2014-02-15T23:39:00.001-08:00

In this second video of the series, we demonstrate the case where the group velocity is zero while the phase velocity is positive number. The individual wave components comprising the total wave are first shown at the top along with a corresponding "dot" representing the phase velocity of each component.

In the bottom figure, we have the resulting wave that travels along the +x direction with a positive phase velocity but the group velocity remains to be zero. The wave packet envelope is shown in magenta color in dashed lines.

For the other videos in the series, check the below links:
1) Group Velocity larger than Phase Velocity: https://www.youtube.com/watch?v=tlM9vq-bepA

Групповая скорость, Gruppengeschwindigkeit, Voortplantingssnelheid, Velocidad de grupo, Grupa rapido, Vitesse de groupe, Velocità di gruppo, 군속도, מהירות חבורה, ჯგუფური სიჩქარე, 群速度, Gruppefart, Prędkość grupowa, Групова швидкість, 群速度, Vận tốc nhóm, Grupphastighet, Grupinis greitis, Phasengeschwindigkeit, Velocidad de fase, 相速度, Vitesse d'une onde, Velocità di fase, Фазовая скорость, 位相速度