Dynamic programming - Introduction

Dynamic programming is a method for solving problems that involve overlapping subproblems and repeated computation for the same sub-structure. This approach optimizes by breaking down complex problems and avoiding redundant work.

To make this clearer, let’s consider a real-world example: imagine there are 200 houses in an apartment complex, and four people are tasked with checking which houses are locked. Each person checks and records the state of the houses every hour. However, if they don’t coordinate, some houses might be checked multiple times, wasting time and resources. Instead, if the four people share real-time information about which houses they’ve already checked, they can avoid redundant checks, speeding up the process and saving energy.

In computer science, this is similar to “Dynamic Programming.” When a problem has overlapping sub-structures, its time complexity can become exponential. By using techniques like memoization or bottom-up dynamic programming, we can often reduce this complexity to linear or polynomial time.

Combination Algorithms

1. Longest Common Subsequence

2. Tower Of Hanoi

3. Tower of Hanoi program in java

SUBSET/COMBINATION Generating and coding.

In this video we will discuss about the idea behind generating combination/subset from the give set. Here the set can be a string, Each character is considered as single element.

Longest Common Subsequence

Longest Common Sub-Sequence


Idea behind the logic is

1. If the two string's first character is same then truncate both and use the truncated string and proceed.
2. if the first two character is not same then, first truncate one character from string s1 and call the function, then truncate the character from string s2 and call the function again. and take the max from that.
 

#include <stdio.h>
#include <strings.h>
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))

int lcs(char *s1, char *s2) {

 if (strlen(s1) == 0 || strlen(s2) == 0) 
  return 0;

 if (*s1 == *s2) {

  return 1+lcs(s1+1, s2+1);
 }
 else {

  return MAX(lcs(s1+1, s2), lcs(s1, s2+1));
 }
}

int main() {

 char s2[] = "abcd";
 char s1[] = "efgh";

 printf("%d\n", strlen(s2));

 int c = lcs(s1, s2);

 printf("%d   count = %d\n", c, count);
}

Recursion - Writing recurrence relation, finding run time complexity and proof.

Javascript Programming Language

 Swift Programming Langauge