ChunMinChang

#include <iostream> // std::cout, std::endl;
#include <memory>   // std::shared_ptr
#include <string>   // std::string
#include <vector>   // std::vector

class A
{
public:
  A()
  {

ChunMinChang

Fibonacci Tricks

Comparison of different calculations for Fibonacci numbers.

TODO

• Saving all the pair of function name and function pointer and using it to check and print its results
  • e.g. Save a pair like ["Recursive", fibonacci_recursive]

Reference

• Calculating Fibonacci Numbers by Fast Doubling

ChunMinChang

// $ g++ dfs.cpp --std=c++11
#include <iostream>
#include <vector>

template<class T>
void ShowResult(std::vector<T>& result)
{
  for (unsigned int i = 0 ; i < result.size() ; ++i) {
    std::cout << result[i] << " ";
  }

ChunMinChang

#ifndef BINARY_TREE_UTILS
#define BINARY_TREE_UTILS

#include <algorithm>  // std::remove_if
#include <cstdlib>    // std::calloc
#include <string>     // std::string, std::stoi
#include <sstream>    // std::istringstream

std::string nullStr = "#";

ChunMinChang

Performance: Mutable array v.s. Hashtable

Subjects:

• mutable array: std::vector
• hash table: std::unordered_map

Results

Insertion time(ms)

| Data Size | 10 | 50 | 100 | 1000 | 5000 | 10000 |

ChunMinChang

// $ g++ class-array.cpp --std=c++11
#include <iostream>

class A
{
public:
  A() {}
  ~A() {}
  void setValue(int v) { value = v; }
  int getValue() { return value; }

ChunMinChang

Common search techniques

• Binary search
• Interpolation search
• Fibonacci search

TO-DO

• Fix Floating point exception in interpolation search
• Implement a recursive version of Fibonacci search
• Implement a Fibonacci search by checking array length with Fn instead of Fn - 1

ChunMinChang

#include "BFM.h"

#include <assert.h>

BFM::BFM(Graph aGraph, unsigned int aStart)
  : ShortestPath(aGraph, aStart)
  , mNegativeCycleDetected(false)
{
}

ChunMinChang

#if !defined(DISJOINTSET_H)
#define DISJOINTSET_H

// The disjoint-set/union–find/merge–find data structure:
//   https://en.wikipedia.org/wiki/Disjoint-set_data_structure
class DisjointSet
{
public:
  // All numbers belong in different sets at the begining.
  DisjointSet(unsigned int aNumbers)

ChunMinChang

#include "ShortestPath.h"
#include <assert.h>

std::vector<int>
BellmanFordMoore(std::vector< std::vector<int> >& aGraph, unsigned int aStart)
{
  assert(!aGraph.empty());

  // To record the shortest distance from start node to other nodes.
  std::vector<int> distances(aGraph.size(), INF);