10 steps to master dynamic programming (step I)

June 9, 2017

Introduction

It takes a lot of practice to learn dynamic programming. As a Leetcode player, Julia learns very patiently to work on Leetcode 123 - buy and sell stock, even at most 2 transactions. Julia has to learn quickly to use dynamic programming to solve problem, and then build a recurrence formula like a mathematician. She will figure out how to do it.

First step to learn again is to play this rename game on stackexchange.com discussion post.

Dynamic Programming should be renamed

Discussion is here.

Dynamic programming

Julia's favorite verse:

Smart recursion plus memoization leading to a faster algorithm.
How to recognize that a problem may admit a smart recursion and come up with it? A common case is divide and conquer.

A

Any recurrence whatsoever

D

defining the subproblems
recursively solving the subproblems

F
frugal bottom-up recursion

I
Inductive Programming
Reverse Inductive Programming

L

Linear programming, integer programming, semidefine programming
Extract a recursive structure from the problem, and write down as a recurrence ( modeling)
"Solve the obtained recurrence in a bottom-up way"  (algorithms)

M

Multistage planning

Multiway-Divide and Memoized-Conquer, and Merge all subproblems

Memoiztion

O
Overlapping-divide-and-conquer

R
Reverse Inductive Programming
Recursive view
Recursive horizon

S
Splice-and-combine

To go with divide-and-conquer

Or overlapping-divide-and-conquer


Smart recursion, but not tables "table and fill"

T

Tabular/ tabulated recursion
Tabular call caching

Tables are sometime used.
Dynamic programming over trees (Maximum independent set), it uses a tree, or in some cases a tree of arrays,
or an array of trees, or in some cases a Cartesian product of trees.

Actionable Items

Google some keywords in the following list:

frugal bottom-up recursion

Tabular/ tabulated recursion

Maximum independent set

Overlapping-divide-and-conquer

Study the ICPC coach website: a Utah professor with great performance on Hackerrank.

quicksort: a practice makes difference

February 2, 2016

Introduction

Julia likes to work on basic things on algorithm problem solving, like brute force solution, recursive function design, divide and conquer solution, partitioning; So, she can write code everyday on algorithm.

Review the quicksort algorithm, and then, practice using C# programming language. So many times Julia went through the review of quick sort algorithm, but to write it in less than 10 minutes, without a bug, without stress, takes more dedicated effort - maybe write a blog to share will help.   

Julia likes to rewrite the above paragraph in April 9, 2018.

Quicksort warmup

First review the blog - the quick algorithm written in Java programming language. Julia must like the idea of choosing pivot value - "// simple version - pick the right most value as the pivot ". As a sports programmer, Julia knows that the power of using a simple test case, she likes to do it here. 

Let us describe how quick sort works: - explain it using 5 minutes - 10 minutes to write the code 

1. First, using partition, and then, divide and conquer, use recursive function calls to solve the problem.

Most important technique, is to design a partition - 2-way partition, how to design the partition, choose pivot point, and how to do partition step by step.

Let us work on a simple example and have discussion, show the procedure of partition.

Let us say that array 1, 2, 3, 4, 5, 6, sorted, and then we like to derive the above sorted array using this one, 1, 3, 2, 5, 4, 6.

One of ideas to choose pivot position, is to choose last number in the array.  For the example, choose last one in the array, 6, the position of pivot point, left side <= 6, right side > 6. So, do you see the problem, 6 is not ideal case. No swap, second partition with 0 values; in other words, all values go to first partition. 

Two way partition

Let us work on another order: 1, 6, 2, 5, 4, 3, 

1. Choose pivot value - last element in the array, value 3
2. Work on partition the array, left partition <= 3, right partition > 3
3. Two partitions are 1, 2, 6, 5, 4, 3

4. Put the pivot point in-between, 1, 2, 3,  6, 5, 4
5. Divide and conquer, solve two small subproblems, use recursive call. 

Use a diagram to show progress:      

Scan the array once from left to right, and then keep track of the start position of right partition. Anything less than 3 will be in left partition.  

The easy way to remember is to find right partition's start position. 

Two way partition - test case

1, 2, 6, 5, 4, 3  -> move pivot value 3 between two partitions

1, 2, 3,  6, 5, 4

Step by step, 

first, after partitioning, the array is the following:

1, 2, 6, 5, 4, 3 

so right side partition starting from array's index value 2 to 4, values are highlighted in background color of green. 

Left side partition:

1  2

left partition, array's index is from 0 to 1. 

Right side partition -  start and end position. 

6 5 4 

right partition, array's index is from 2 to 4. 

And then the pivot value 3 is inserted in-between left partition and right partition. 

1, 2, 3,  6, 5, 4

Let us recap what we practice here, go over a simple test case, and then choose a pivot value, and then partition, divide and conquer, go to solve two small problems using recursive calls. 

Julia's practice:

Quick sort algorithm writing in C# - less than 20 minutes (18 minutes to write the code with comments)

2nd practice using C# 

Quicksort Lecture Study

Julia, spend one hours to read the webpage, and enjoy the great lecture. Reading is much important than coding. And then, work on some questions in the lecture.

princeton lecture notes

Questions and Answers

February 3, 2016

After reading her favourite lecture notes, Julia likes to respond something to entertain quicksort algorithm practice, put something together with her own thinking based on discussion from reading material:

Fact 1:
Q1. Quick sort algorithm will work even in worst case, no dead loop. Why? 
Arguments:
1. Each recursive function, at least one value is resolved, no more work for the value. That is pivot point. So, at most, each recursive call solves one value, n recursive call will solve all n values in the array. Is it fun to design the algorithm? Yes.

Q2. Quicksort function design - only solve one value to position correctly, in the whole array. This is not efficient? 
Arguments:
1. This is the fact. And it works fine. And if you remember that, you can write a quick sort algorithm in less than 5 minutes. 
2. So, position one value, partition array into two sections. 

Q3. Partition can use different strategies, only important and should work on more is to find one, work out as fast as you can. And make it easy to remember. What is your advice? 
Advice:
  Choose last one in the array as a pivot point, and then, find the partition - swap and maintain a partition (each value in the partition  >  pivot value) just on right side of array. Use two pointers to find the partition two values - start, end position. 

Q4. Is this algorithm using in-place without extra space? 
Answer: 
Yes, the answer is staying in the original array, no extra space (O(1), not O(n)). So, array is used to store result, only swap two nodes' value if need. 

Facts: at most how many swap?     it depends. O(n^2)
           How many recursive calls?  n 

Because it is using in-place, the quicksort function design takes 3 input arguments, original array, start, end. 

If you cannot come out best design using in-place, you may need extra time. 

Feb. 4, 2016 Q5. Work on Leetcode - partition list
86. Partition list
http://www.cnblogs.com/springfor/p/3862392.html

328. Odd Even Linked List

Follow up after 9 months

Nov. 24, 2016
Review the code review about quick sort. 
Answer the question, link is here.  

Follow up after 13 months

March 14, 2017
1. Read all algorithms in the blog, the blogger got Google and Linkedin offer. The algorithms may be a good study material for Julia.

2. Practice one more time, C# code. Add test case for partition method and quicksort method. 

Leetcode 23: Merge K Sorted Lists

July 19, 2016

 Problem statement:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 Julia's first two practices in 2015:
1. Naive solution:
https://github.com/jianminchen/Leetcode_C-/blob/master/MergeKSortedLists_A_No23.cs


2. Implementation using merge sort: August 12, 2015
https://github.com/jianminchen/Leetcode_C-/blob/master/MargeKSortedLists_B_No23.cs

Come back to work on this problem in 2016, July 19:

Study those blogs:
1. Most favorite one:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-merge-k-sorted-lists.html

Specially, the third discussion using divide and conquer, the conclusion that the merge solution is same time efficiency using heap solution Nklog(k), k is the number of arrays, and N is the length of the array, assuming that each array has same length.

1. http://www.cnblogs.com/TenosDoIt/p/3673188.html

2. http://bangbingsyb.blogspot.ca/2014/11/leetcode-merge-k-sorted-lists.html

3. http://codeganker.blogspot.ca/2014/08/leetcode_26.html

4. http://www.cnblogs.com/springfor/p/3869217.html

5. https://github.com/shawnfan/LintCode/blob/master/Java/Merge%20k%20Sorted%20Arrays.java

7. Excellent article - Julia, share your personal story as well.
http://codeganker.blogspot.ca/2014/08/leetcode_26.html

Read the article: 

http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf

Julia's question and answer: 
1. Ideas to improve practice?
Answer:
  Ideas to construct the practice:
   1. Need to work on blog 7 - 3 solutions using C#, apply to "merge k sorted array".

Learn bottom-up merge sort, and know the time complexity as well.

C# solution - merge k sorted array - using bottom-up implementation merge sort
https://gist.github.com/jianminchen/d5fab2036647d380f20c908e91a81132

   2. Write down the proof of "divide and conquer" time complexity comparison using heap, O(nk logk)
       Show some simple example to help understand the time complexity.
   3. Warm up the code practice a few times, aiming to write 20 minutes for a solution
   4. Need to figure out master theorem quickly.

2. Can you work on a small example to illustrate some analysis?
Copy the image from Princeton's lecture note:

3. Can you write some C# code this time to make your own mark?

Actionable items:

Read the article, and write down questions - prepare a further reading list. (30 minutes reading )
https://en.wikipedia.org/wiki/Merge_sort
Notes:

keywords:  (remember 14 keywords)
average and worst-case performance
Bitonic Mergesort
Bottom-up implementation
comparison-based sorting algorithm
external merge sort - disk/ tape drives

external merge sort
master theorem
merge sort - not inplace - must be allocated for the sorted output to be stored in
parallel mergesort
polyphase merge sort
natural merge sort - similar to a bottom up merge sort

stable sort, 
TimSort, 
tiled merge sort algorithm
Top-down implementation

Variants:
  1. reducing the space complexity
  2. cost of copying

locality of reference

memory hierarchies
cache-aware version of merge sort algorithm
tiled merge sort algorithm

Parallel merge sort

Merge sort parallelizes well due to use of the divide-and-conquer method.

-
Comparison with other sort algorithms

heapsort   vs merge sort

O(1) auxiliary space instead of merge sort's O(n).

efficient quicksot implementations generally outperform mergesort for sorting RAM-based arrays - ?

merge sort is a stable sort and is more efficient at handling slow-to-access sequential media.

Merge sort is often the best choice for sorting a linked list.

the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others(such as heapsort) completely impossible.

Java, Array.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficicency switch to insertion sort when fewer than seven array elements are being sorted.

Python uses Timsort, another tuned hybrid of merge sort and insertion sort.

--
More reading:
30 minutes to review:
http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf


5 minutes reading:
http://infolab.stanford.edu/~ullman/fcscnotes/notes9.pdf

20 minutes reading - plan to read - parallel merge sort
http://stanford.edu/~rezab/dao/notes/Lecture04/cme323_lec4.pdf

Read 10 minutes a time - get lost and enjoy reading ...


http://web.archive.org/web/20150120063131/https://android.googlesource.com/platform/libcore/+/jb-mr2-release/luni/src/main/java/java/util/TimSort.java

Will come back very soon.

Divide and Conquer: Preorder traversal of ternary tree

January 6, 2016 重温一道关于树遍历的题目, 在新年开始的第一个星期, 鼓励自己, 加油! 多写代码, 多练习. Be humble, learn from her mistakes in 2015. Julia is learning how to solve "divide and conquer" - write a perfect recursive function - without bug in base case - recursive calls.  Her lessons for recursive function design, divide and conquer solution in 2014, 2015: 1. Do the work for root node, but do not do the work for its children; In other words, a subproblem can be handled by a recursive call.  2. Do not repeat base case 'if' clause - a checking afterwards in the recursive function call. Not necessary, except trying to use less stack.  Julia, recursive function design is like dealing with a family - single parent with children; show the work how to handle root node, that is almost done. Let recursive function to take care of children, do not do the work for children nodes. For example, binary tree, 2 children, call recursive function twice; Ternary tree, 3 children, and then, use 3 recursive calls.  Once again, "Do not do the work for children directly".  Action items: 1. Work on Leetcode questions again and start with simple questions. Binary Tree Preorder traversal of ternary tree

https://github.com/jianminchen/TreeAlgorithms/blob/master/ternaryTreeTraversal.cs   Binary Tree Inorder traversal: https://github.com/jianminchen/TreeAlgorithms/blob/master/TreeInorderTraversal.cs   Binary Tree Post order traversal https://github.com/jianminchen/TreeAlgorithms/blob/master/TreePostOrderTraversal.cs   Preorder traversal  https://github.com/jianminchen/TreeAlgorithms/blob/master/TreePreOrderTraversalB.cs

More reading about ternary tree:
  https://en.wikipedia.org/wiki/Ternary_search_tree

  https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms

  http://www.drdobbs.com/database/ternary-search-trees/184410528

Leetcode discuss: 84. Largest Rectangle in Histogram

July 19, 2022

Here is the link. 

C# | Quick learner | Optimal time complexity solution provided

Dec. 3, 2020
I work on five solutions and I like to share the solution using stack with optimal time complexity O(N^2). Also, I add brute force solution as solution 2, which may not be helpful for any interview preparation, O(N^3).

All solutions in series:

1. Brute force
2. Better brute force
3. Divide and conquer
4. Better divide and conquer
5. Using stack

Solution 1: Using stack | Time complexity: O(N)

Example | Case study | Ask good questions
It is a hard level algorithm. Every one should think about using stack to reach optimal time complexity O(N). But how to maintain the stack and keep ascending stack to meet calculation need. I like to contribute some good thoughts so that you and I both learn something.

How to calculate the largest histogram area - 10, what is in stack when iteration to index = 4, value 2, I believe that maximum area will calculate including 6 - as one standalone, and then two - 5 and 6, and then 6 should be popped from stack, 6 should be popped from 5, since 5 and 6 will no longer be needed in any calculation for possible bigger area any more.

One thing to argue is that the stack should always keep the minimum value in the stack before it reaches the last one in the stack. That one is possible candidate for largest histogram area, using minimum value multiplys the length of the array.

Calculation when index = 4, value 2

1. Pop 6 since 6 > 2 - calculate area 6 -> 6, compare to maximum area so far
2. Pop 5 since 5 > 2 - calculate area from 5, 6 -> 10, compare to maximum area so far
3. Compare 1 vs 2, leave 1 in stack, no calculation, push 2 into the stack, {1, 2}. 

Think about the above steps, see if anything is wrong or missing anything for possible largest histogram area.

Go back and forth to warm up the algorithm design using the above histogram, ask more questions. Using debugger, and then make sure that the argument is true or false.

Requirement analysis:
I reviewed a few videos on youtube.com related to this algorithm. I do think that the missing part in those video is about how to analyze starting from brute force, and come out requirement for optimal solution:

1. Need to find minimum value in the array, for width of span of whole array.
2. Need to find maximum value in the array, for only one number area;
3. Need to argue that ascending order numbers, we can skip multiple areas for one number, two numbers, three numbers etc. to one of them, as long as we count the numbers from highest to smaller ones in consecutive orders. (This is interesting math problem, we can prove that it is true.)
4. Next extract the design of data structure of ascending stack.
5. We need to make sure that for all width from 1 to n, n is the length of the array, we need to select at least one of them, maximum one should be included.
6. More on step 5, relax on this requirement, we can find multiple time as long as we maintain the ascending stack, and pop up those numbers bigger than current number.

public class Solution {
    public int LargestRectangleArea(int[] height) {
            var stack = new Stack<int>();

            var index = 0;
            var largestArea = 0;

            int length = height.Length; // 6

            while (index < length) // true; index = 1; index = 2;
            { 
                //     stack empty            going upward
                if (stack.Count == 0 || height[stack.Peek()] < height[index]) // index = 1, false;
                {
                    stack.Push(index++); // 0, index = 1;
                }
                else
                {
                    // going downward and then pop stack, calculate rectangle.
                    popStackAndCalculate(ref largestArea, stack, height, index);
                }
            }

            while (stack.Count > 0)
            {
                popStackAndCalculate(ref largestArea, stack, height, length);
            }

            return largestArea;
        }

        /// <summary>
        /// downward and then pop stack to calculate the rectangle
        /// </summary>
        /// <param name="largestArea"></param>
        /// <param name="stack"></param>
        /// <param name="height"></param>
        private static void popStackAndCalculate(ref int largestArea, Stack<int> stack, int[] height, int rightIndex)
        {
            int length = height.Length; // 6

            int lastHeight = height[stack.Pop()]; // 2
            int width = stack.Count == 0 ? rightIndex : rightIndex - stack.Peek() - 1; // 1

            largestArea = Math.Max(largestArea, lastHeight * width); // 2 * 1
        }
}

Solution 2: Brute force solution | Naive approach
I like to quickly share the brute force solution. This is a good exercise to review basics of for loop and make sure that calculation is correct first.

Five series - C# - Brute force - TLE - Time O(N^3)

Consider every possible pair of bars, and find the area of the rectangle formed between them using the height of the shortest bar lying between them as the height and the spacing between them as the width of the rectangle. We can thus, find the required rectangle with the maximum area.

public class Solution {
    /// <summary>
        /// brute force solution
        /// Time complexity: O(N^3)
        /// start and end position - all possible pairs - O(N^2)
        /// Find minimum height in given range - O(N)
        /// Total time complexity is O(N^3). 
        /// </summary>
        /// <param name="heights"></param>
        /// <returns></returns>
        public int LargestRectangleArea(int[] heights)
        {
            var length = heights.Length; 
            int maxarea = 0;

            for (int start = 0; start < length; start++)
            {
                for (int end = start; end < length; end++)
                {
                    var minHeight = Int32.MaxValue;

                    for (int k = start; k <= end; k++)
                    {
                        minHeight = Math.Min(minHeight, heights[k]);
                    }

                    maxarea = Math.Max(maxarea, minHeight * (end - start + 1));
                }
            }

            return maxarea;
        }
}