algorithms20181106.md

https://gist.github.com/johntran - > algorithms20181106.md

Algorithms 2018 11 06

Problem Set

N-Queens

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3.

For example, following is a solution for 4 Queen problem.

The expected output is an array of QueenSolution. QueenSolution is an array of QueenPositions that makes up a possible solution. QueenPositions is a class that holds the row and index that queen is placed in. This class can hold other methods.

/**
 * Class that represents queen position on the chessboard.
 */
export class QueenPosition {
  /**
   * @param {number} rowIndex
   * @param {number} columnIndex
   */
  constructor(rowIndex, columnIndex) {
    this.rowIndex = rowIndex;
    this.columnIndex = columnIndex;
  }
}

export default function nQueens(queensCount) {
  // fill me
}

nQueens(4)
// returns [
[new QueenPosition(0,2), new QueenPosition(1,0), new QueenPosition(2,3), new QueenPosition(3,1)]
// other solutions here
]

Hint 1:
export default function nQueens(queensCount) {
  // This array will hold positions or coordinates of each of
  // N queens in form of QueenPosition(row, column)[].
  // For 4 queens it results in [null, null, null, null]
  const queensPositions = Array(queensCount).fill(null);

  /** @var {QueenPosition[][]} solutions */
  const solutions = [];

  // Solve problem recursively.
  nQueensRecursive(solutions, queensPositions, queensCount, 0);

  return solutions;
}

Matrix Chain Multiplication

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:

    (ABC)D = (AB)(CD) = A(BCD) = ....

However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,

    (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
    A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Clearly the first parenthesization requires less number of operations.

Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function MatrixChainOrder() that should return the minimum number of multiplications needed to multiply the chain.

  Input: p[] = {40, 20, 30, 10, 30}   
  Output: 26000  
  There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30.
  Let the input 4 matrices be A, B, C and D.  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  (A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30

  Input: p[] = {10, 20, 30, 40, 30} 
  Output: 30000 
  There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30. 
  Let the input 4 matrices be A, B, C and D.  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  ((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30

  Input: p[] = {10, 20, 30}  
  Output: 6000  
  There are only two matrices of dimensions 10x20 and 20x30. So there 
  is only one way to multiply the matrices, cost of which is 10*20*30
  
// Algorithm is from Intro to Algorithms by Cormen pg. 370
// Time Complexity: O(n^3)
// Space: O(n^2)
function createMultiDimensionalArr(length) {
  // Create a multidimensional array
  let table = new Array(length);
  for (let i = 0; i < table.length; i++) {
    table[i] = new Array(length);
  }
  return table;
}

function matrixChainDp(arr) {
 // fill me
}

Count all possible paths from top left to bottom right of a mXn matrix

The problem is to count all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down

Examples :
Input :  m = 2, n = 2;
Output : 2
There are two paths
(0, 0) -> (0, 1) -> (1, 1)
(0, 0) -> (1, 0) -> (1, 1)

Input :  m = 2, n = 3;
Output : 3
There are three paths
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2)
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2)