Maximum Subsequence Sum Problem (MCSS) Before we get started let me remind you that this is a series of short articles on Dynamic Programming. You can refer to the first article (introduction) here. In this article we are going to discuss a new problem (MCSS) that can be solved efficiently using Dynamic Programming. The MCSS
Longest Common Subsequence Welcome to the 4th article on Dynamic Programming. You can refer to the first article (introduction) here. I will be using the shortcut LCS to refer to longest common sub-sequence. Let us get started. Introduction One of the applications of “Longest Common Subsequence” problem is comparing DNA strings to see how similar
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
Problem Given the following database table: DATA (id, data_date, data_value). The id field is not unique. Write an SQL statement to select the latest value for each id Solution Group rows by id then select rows with maximum date Code Here is the code
Problem Write an SQL statement to find rows with duplicate column values in a database table Solution You need to group by the column containing the duplicate values then select only the groups with count greater than 1 Code Here is the code in SQL
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 Write a regular expression in Perl to validate dates in the following format “mm/dd/yyyy”. The month and day fields can be one or two digits. Code Here is a sample Perl code to do that
