Matrix Chain Multiplication Welcome to the third article on Dynamic Programming. You can refer to the first article (introduction) here. Let us get started. Introduction Before we formally define our problem let us first refresh our memory about matrix multiplication. In order to multiply two matrices (A) and (B) the number of columns of matrix
Assembly Line Scheduling This is the second article on Dynamic Programming. You can refer to the first article (introduction) here. Let us get started by defining our problem. Problem definition The following bullet points define our problem: We have two (parallel) car assembly lines (1) and (2). Each assembly line has (n) stations. The time
Introduction This short article is mainly for students, software engineers and those who are struggling to get a grip on the subject. In other words I will not be focusing on the theoretical side of the topic. I will first explain what Dynamic Programming means then provide several examples to demonstrate this algorithmic technique. I
Merging Two Arrays Problem Given two sorted arrays A and B of different sizes m and n. Describe an algorithm to combine the two arrays into one array. The output array must not have duplicates. The output array must maintain the original order of values in A and B Solution If you recall the well
Lexicographic Order Problem Write java method to compare two strings lexicographically. The method should return 0 if the two strings are Lexicographically equal. It should return 1 if the first string comes before the second string in the dictionary. It should return -1 if the first string comes after the second string in the dictionary.
Problem Provide example code in Perl to implement an array of C like structs Solution Use a hash table. The hash key is recommended to be a unique identifier and the hash value is a reference to an array. The idea is simple and the rest is just using the correct Perl syntax Code Here
Problem Write a Java method to replace a sub string in a given text with another string of the same size Solution Loop through the text character by character. Starting at the current character loop a number of times equal to the size of the sub string while comparing characters in the original text and the sub
Problem Write a C++ function to copy an existing string. Do not use built in functions. Solution This is a straight forward question and to my surprise I was asked this question in a site interview. If you are not prepared you might stumble on the easy ones. The idea is to allocate memory for
Problem You have a log file on UNIX operating system. Each line in the log file contains an IP address in the 10th column where columns (or fields) are separated by a space. Write a Perl program to parse the log file and print the unique IP addresses in the log file Solution Read the
Problem Given a one dimensional integer array of 9 elements. Write a function to map the array into a row major 3×3 two dimensional array Solution If you are familiar with 3D graphics API like DirectX or OpenGL they store 4×4 transformation matrices as a linear array of 16 elements. In DirectX the format is