Warm Up for Dynamic Programming Practice #DPfCI #dynamic_programming #recursion

bubbleSort.cpp

#include <cassert>
#include <iostream>

#undef RECURSION
#undef DYNAMIC_PROGRAMMING
#undef RUN

#define RECURSION 1
#define DYNAMIC_PROGRAMMING 2
#define RUN RECURSION
// #define RUN DYNAMIC_PROGRAMMING

void Swap(int& a, int& b)
{
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
}

#if RUN == RECURSION

// void BubbleSort(int array[], unsigned int n)
// {
//   if (n == 1) {
//     return;
//   }

//   // Bubble up the max item to the end of the n-size array.
//   for (unsigned int i = 0 ; i < n - 1 ; ++i) {
//     if (array[i] > array[i+1]) {
//       Swap(array[i], array[i+1]);
//     }
//   }

//   // The max item is at array[n] after bubbling.
//   // Now, keep sorting the array from 0 to n-1.
//   BubbleSort(array, n-1);
// }

void BubbleSort(int array[], unsigned int n)
{
  if (n == 1) {
    return;
  }

  // Bubble up the max item to the end of the n-size array.
  unsigned int maxIndex = 0;
  for (unsigned int i = 1 ; i < n ; ++i) {
    if (array[i] > array[maxIndex]) {
      maxIndex = i;
    }
  }
  if (maxIndex != n-1) {
    Swap(array[maxIndex], array[n-1]);
  }

  // The max item is at array[n] after bubbling.
  // Now, keep sorting the array from 0 to n-1.
  BubbleSort(array, n-1);
}

#else

// void BubbleSort(int array[], unsigned int n)
// {
//   // Bubble up the max item to the end of the array iteratively.
//   // We need to bubble up item n-1 times at most, since the smallest item
//   // will be naturally bubbled down to the beginning of the array.
//   for (unsigned int i = 1 ; i <= n - 1 ; ++i) {
//     // Sort only array[0:n-i];
//     for (unsigned int j = 0 ; j < n - i ; ++j) {
//       if (array[j] > array[j+1]) {
//         Swap(array[j], array[j+1]);
//       }
//     }
//   }
// }

void BubbleSort(int array[], unsigned int n)
{
  // Bubble up the max item to the end of the array iteratively.
  // We need to bubble up item n-1 times at most, since the smallest item
  // will be naturally bubbled down to the beginning of the array.
  for (unsigned int i = 1 ; i <= n-1 ; ++i) {
    // Sort only array[0:n-i];
    unsigned int maxIndex = 0;
    for (unsigned int j = 1 ; j <= n-i ; ++j) {
      if (array[j] > array[maxIndex]) {
        maxIndex = j;
      }
    }
    if (maxIndex != n-i) {
      Swap(array[maxIndex], array[n-i]);
    }
  }
}

#endif

int main()
{
  // int arr[10] = { 3, 6, -5, 12, 59, -40, 23, 21, 60, -12 };
  // BubbleSort(arr, 10);
  unsigned int n = 0;
  std::cout << "Enter size of array (greater than 0): ";
  while(!(std::cin >> n) || n <= 0) {
    std::cout << "The size should be greater than 0! Enter again: ";
    std::cin.clear();
  }
  int* arr = new int[n];
  for (unsigned int i = 0 ; i < n ; ++i) {
    std::cout << "array[" << i << "]: ";
    std::cin >> arr[i];
  }

  BubbleSort(arr, n);

  std::cout << "Sorted: ";
  for (unsigned int i = 0 ; i < n ; ++i) {
    std::cout << arr[i] << " ";
    if (i > 0) {
      assert(arr[i] >= arr[i-1]);
    }
  }
  std::cout << std::endl;

  delete[] arr;

  return 0;
}

factorial.cpp

#include <iostream>

#undef RECURSION
#undef DYNAMIC_PROGRAMMING
#undef RUN

#define RECURSION 1
#define DYNAMIC_PROGRAMMING 2
// #define RUN RECURSION
// #define RUN DYNAMIC_PROGRAMMING

#if RUN == RECURSION

// Recursion
unsigned int Fractorial(unsigned int n)
{
  return n < 2 ? 1 : n * Fractorial(n - 1);
}

#else

// Dynamic Programming
unsigned int Fractorial(unsigned int n)
{
  unsigned int f = 1;
  for (unsigned int i = 1 ; i <= n ; ++i) {
    f *= i;
  }
  return f;
}

#endif

int main()
{
  int n = 0;
  std::cout << "Enter n: ";
  std::cin >> n;
  std::cout << n << "! = "<< Fractorial(n) << std::endl;
  return 0;
}

power.cpp

// See https://gist.github.com/ChunMinChang/9753c72e2441343e14757f5a9ac95a98
// and https://chunminchang.github.io/blog/post/exponentiation-by-squaring
// for better solutions of k^n.

#include <iostream>

#undef RECURSION
#undef DYNAMIC_PROGRAMMING
#undef RUN

#define RECURSION 1
#define DYNAMIC_PROGRAMMING 2
// #define RUN RECURSION
// #define RUN DYNAMIC_PROGRAMMING

#if RUN == RECURSION

// Recursion
int Power(int k, unsigned int n)
{
  return n ? k * Power(k, n - 1) : 1;
}

#else

// Dynamic Programming
int Power(int k, unsigned int n)
{
  int p = 1;
  for (unsigned int i = 1 ; i <= n ; ++i) {
    p *= k;
  }
  return p;
}

#endif

int main()
{
  int k = 0;
  unsigned int n = 0;
  std::cout << "Enter k, n: ";
  std::cin >> k >> n;
  std::cout << k << "^" << n << " = "<< Power(k, n) << std::endl;
  return 0;
}

sum.cpp

#include <iostream>

#undef RECURSION
#undef DYNAMIC_PROGRAMMING
#undef RUN

#define RECURSION 1
#define DYNAMIC_PROGRAMMING 2
// #define RUN RECURSION
// #define RUN DYNAMIC_PROGRAMMING

#if RUN == RECURSION

// Recursion
int Sum(int n)
{
  if (n == 0) {
    return 0;
  }
  return n + Sum(n > 0 ? n-1 : n+1);
}

#elif RUN == DYNAMIC_PROGRAMMING

// Dynamic Programming
int Sum(int n)
{
  int s = 0;
  while (n != 0) {
    s += n;
    (n > 0)? --n : ++n;
  }
  return s;
}

#else

// Math
// Sum(a, a+d, a+2d, ..., a+(m-1)d) = [m(2a+(m-1)d)]/2
// In this case, d = 1, so sum = [m(2a+m-1)]/2.
int Sum(int n)
{
  int a = 0, m = 0;
  if (n > 0) {
    a = 1;
    m = n;
  } else {
    a = n;
    m = -n;
  }
  return (m*(2*a + m-1))/2;

  // int a = (n > 0) ? n : -n;
  // int s = a*(a+1)/2;
  // return (n > 0)? s : -s;
}

#endif

int main()
{
  // Sum(n) is summation from 0 to n if n >=0,
  //                  or from n to 0 if n <0
  int n = 0;
  std::cout << "Enter n: ";
  std::cin >> n;
  std::cout << "Sum is " << Sum(n) << std::endl;
  return 0;
}

sumOfArray.cpp

#include <iostream>

#define ARRAY_LENGTH(A) (sizeof(A) / sizeof(A[0]))

#undef RECURSION
#undef DYNAMIC_PROGRAMMING
#undef RUN

#define RECURSION 1
#define DYNAMIC_PROGRAMMING 2
// #define RUN RECURSION
#define RUN DYNAMIC_PROGRAMMING

#if RUN == RECURSION

// The lastest element, array[size-1], will be the sum of all the
// previous elements after executing the function call. That is,
// array[size-1] = array[size-2] + array[size-3] + ... + array[1] + array[0]
// after calling Sum(array, size).
void Sum(int* array, unsigned int size)
{
  if (size <= 1) {
    return;
  }
  Sum(array, size - 1);
  array[size - 1] += array[size - 2];
}

#else //RUN == DYNAMIC_PROGRAMMING

void Sum(int* array, unsigned int size)
{
  for (unsigned int i = 1 ; i < size ; ++i) {
    array[i] += array[i - 1];
  }
}

#endif

int main()
{
  int a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  const unsigned int sz = ARRAY_LENGTH(a);
  Sum(a, sz);
  for (unsigned int i = 0 ; i < sz ; ++i) {
    std::cout << a[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}