DP 2

First a simple problem -

Given a number N, and a set of numbers, say S = {x1, x2, x3 }. Find the number of ways to represent N as sum of the numbers from set S. Since it is sum operator, we can ignore all  x in S, s.t. x > N. So assume all x <= N in this case.

Let say N = 5; S = { 1, 3, 4 }. How the different sum repesentation would look ? 

1+1+1+1+1

1+1+3

1+3+1

3+1+1

1+4

4+1. 

So we have 6 different ways to sum Note that 4+1 and 1+4 are different representations, so are others with 3.

We define F(N) = # of ways to write N as sum of elements from set S = { x1, x2, ... xm}. Here N = 5, and S= {1,3,4}.

Looking for substructure, so we need to fix, say the last position of the sum representations. Say, the last position is 1. then the rest of the sum has to be N-1. It is nothing but F(N-1), similarly if the last position is 3 or 4, then the rest of those representation has to be F(N-3) and F(N-4) respectively. Now since we have only three such numbers in the set, F(N) = F(N-1) + F(N-3) + F(N-4). What are the base cases ??

F(1) = # ways to represent 1 as sum of elements from the set S = {1,3,4}. Only one way, just select 1. F(2) = 1, since 1+1 is the only way. F(3) = 1+1+1 or 3 representations so F(3) = 2, and F(4) = 3

Solution -

F[1] = F[2] = 1; F[3] = 2; F[4] = 3;

for ( int i = 5, i <= N; i++ )

     F[i] = F[i-1] + F[i-3] + F[i-4];

That's it !!

Whart is the takeaway from this example ?

If the set S = {3, 5, 6, 9 } what would be functional equations and dependencies ? Solve it.

Posted on Saturday, May 5, 2018 at 07:56PM by Registered CommenterProkash Sinha | CommentsPost a Comment

Dynamic Programming 1

Dynamic Programming(DP) is originally an analytic process for different types of optimization problems in : Engineering, Economics, and stratic processes. Usually it came from Calculus of varations and other Analytic methods of Mathematics.

Then came the Operation Researchs as a branch of studies where dynamic programming plays a central role. We would try to avoid those topics that are not related to programming.

But we may cover an interesting part -- Probabilistic Dynamic Programming just for fun.

I've seen many websites for solving Dynamic Programming problems. Perhaps way too many, including PDF down loads etc. My main concern is how to get a systematic treatment of even approaching these problems ?

I don't know yet, and I'm still looking for it. So I will have my unbiased and humiliated discussions on this ...

 Principles of attacking DP problems --

-- try to find a recursive solution first. In order to do that it is important to define a Functional equation. The functional equation, if correct will lead to a recursive implementation. And the main theme will be like : F(n) = min { F(n-k), where 0 <=k < n } or some other form. So some operatior, almost always, would be used to carry forward the solution from sub-problems' solution.  This is to get the right sub-structures of the problem.

-- Now try to reduce the problem to basic cases, and hand calculate thru the equation to see if it is satisfying your equation. Like in Binary Tree search, we can argue with small sample binary tree to see if the recussive function, hence the implementation is correct or not. 

-- Finally see if the recusive solution on small base cases gives any redundant computations. If so, then we can use dynamic programming formulation for the problem. So try to come up with a DP formulation.

Note that DP solution requires saving of previous sub-problem computations. Hence memoization is needed using some sort of tables.

Other thing to note that DP problems has it own dimenstions like 1-d, 2-d, 3-d. 2-d, 3-d problems are harder to formulate though. 

Since Optimization problems are mostly the domain for DP solution, constraint functions gives the dimensions.

EX:    Maximize  or Minimize some Objective Function, subject to some constraint.

 

Posted on Saturday, May 5, 2018 at 05:55PM by Registered CommenterProkash Sinha | CommentsPost a Comment

Dynamic programming 0

What is dynamic Programming ?

Dyanmic programming is a design paradime, that helps eliminate redundant computations. In a sense, the mathematical problem has to have nice sub-structures to allow use of sub problems solution(s) to achieve the solution of the problem at hand.

A great example is Fibonacci sequence - 1, 1, 2, 3, 5, 8, 13 ... where the solution of Fib(N) = Fib(N-1) + Fib(N-2), and Fib(N) means Fibonnaci number of N > 1.

Where it came from ?

In early 50s and 60s of last century, there were optimization problems related industralization that brought new insights to understand the substructures of problems and use them. This soon became new field of Mathematics called Operations Reseachs. Bellman is one of the founder of this branch of Mathematical Analysis to optimization problems.

What is an Optimization problem ?

When we have a finite resource, how could we use it the most efficient way is in essence and optimization problem. Ex: If you have 100 bucks to spend for a day, and you are given the alternatives with cost of those alternatives. How would you like to optimize the use of 100 bucks.

So there is an Objective function ( optimization function) that we want to maximize or minimize. And there is/are constraints or bounds that keep the scope of the optimization we can use. So it would be fair not to tackle these problems by extreemly rich persons ( fill the names here) to optimize grocery budget of a month, for example.

Why it is important for Programmers ?

There are lot of problems being solved using computers. And lot of problems require lot of computing resources when programmatically solved. Some large problems are impossible to solve using other means.

Where is the place to get an understanding of Dynamic Programming ?

You can find lots of Algorithm books, online documents etc. But the gound work has to be from Bellman, et. all books. Reason being that is that way, is because identifying sub stuctures is the key.

Common problems that are being used for interviews are --- 

Longest Common Subsequence

Longest Increasing Subsequence

Edit Distance

Minimum Partition

Ways to Cover a Distance

Longest Path In Matrix

Subset Sum Problem

Optimal Strategy for a Game

0-1 Knapsack Problem

Boolean Parenthesization Problem

Shortest Common Supersequence

Matrix Chain Multiplication

Partition problem

Rod Cutting

Coin change problem

Word Break Problem

Maximal Product when Cutting Rope

Dice Throw Problem

Box Stacking

Egg Dropping Puzzle

 ...


 


Posted on Sunday, April 8, 2018 at 02:42PM by Registered CommenterProkash Sinha | CommentsPost a Comment

When AI > NI

These days, Artificial Intellegence > Natural Intellegence. The days of Frankenstien finally arrived. Every high-tech company is investing or at least broadcasting that they are using or very soon would be using AI. Sooooo, I started looking back of what we were doing 30 yrs back in Graduate school ! Back then AI was mostly natural language based expert systems or some Heuristics based expert systems. For example, computer based chase player. Robotics, Newral network etc., were in their dawn days. We did not have many branches like: ML, supervised learning, deep learning etc.  Took a class in AI, later in mid semister dropped out, did not make much sense.

Then came the Statistical / Baysian decision process, and now Ai is as pervasive as Cell Phone. I did a sampling of some of the books in AI, and got stuck with the book - Deep Learning! Looking at the book gave me an immense joy, and disappoint too. The book is wonderfully written, by my first glance of few chapters. Joy was that most of the topics are covered back then in different form and purpose. Like statistical methods, Probablity and Measure toward Discrete Martingale, Operations Research, Stochastic processes etc. Disapointment is there is really a Deep Learning again for me, if I need to look at them again...

Big question is -- How do we make a massivelly parallel machine to learn ? How could we make the machine available for almost all areas of scientific researches ?

 

There are many areas that needs to be covered before even I could start saying something ...

One such area is Dynamic Programming, that is essential for any optimization problem that has overlapping substructures. Finding such structures and using them needs key insights of the problem at hand.

So I will start with some dynamic programming next.

 

 

 

 

 

 

Posted on Sunday, April 1, 2018 at 05:47PM by Registered CommenterProkash Sinha | CommentsPost a Comment

Design,Resign ...

Do I really like to do the same thing time and again ? That's the question I ask to myself. The answers are different for different situations. Some tasks I can't left to others - like taking a shower etc. And it is repetitive that I can not avoid :-). Others I really don't want to repeat.

One such example is tracing your program thru debug messages, so you know when was the last time, the program behaved as expected, or at least hope for.

So how could I write a debugging module that would take care most of my tracing work, when in need to trace them. Yeah, you will say - as if none of us seen this before. And you are right. We have seen a lot of them. Sometime they are old cruft, and codes are defacto standard copy/paste from even older code. No one really likes to trace/debug, or at least not much of it. Hence the result.

Recently, due to way many things coming into software complexity, people are trying to have different debug tracing, and even systems support logging and tracing. Some of them are system supplied, and you can not change the behaviour and sometime very hard to share with experts on the other side of the globe or galaxy.

Questions aboud -

1) How can I use some design, that does not restrict me in most ways, like use of common languages like: Java, C++, object-C, Swif etc.

2) How can I use in a location independent way ?

3) How can I turn on/off tracing at will and control different types of tracing messages I'm interested in ?

4) How can I make the fairly secure and private ?

5) How can I have them thead safe, so that it does not get in the way of debugging / tracing itself?

etc., etc...

All of these boil down to one thing, in some sense, decouple every little feature(s) as it is always the fact that we don't have complete requirements aprioi. All most always, we will see some thing is either not present or never thought about while at the design table.

All of these, leads to open ended design, so we can plug and play as we go along without compromising structure integrity by large magnitude. And translate to Design Patterns. Mapping requirements to existing design patterns ( or to even come up with new ones ) is the process that I'm talking about by taking an example implementation of a sofware component.

In summary, it will have the formatting meta data to know where is log is coming from, it will have the privacy/encription etc., it will allow dynamic control of what we trace and where the traces go, it should be able to allow multiple related software programming languages... 

Basic design pattern for this I chose is called Observer pattern. This is part of a class of patterns named Behavioural pattern. The choice of implementation language is C++, since the C interface is common among the languages I mentioned above along with many more.

Note that not all patterns are simple, and some of them are even fairly complex to get it right. Here we choose Observer to decouple producer from consumer of the trace to dynamically control both trace message types and destinations of the messages. A message can land in any other remote machine, along with quick console debugging, and system file logging. Messages could also be for different reasons ( event types ) too.

Adapter pattern is used to capture multiplatform supports.

 

 

 

 

Posted on Saturday, March 10, 2018 at 12:57PM by Registered CommenterProkash Sinha | Comments Off