Dynamic Programming (DP) Tutorial with Problems

Dynamic Programming

Table of Contents

• 1. Introduction to Dynamic Programming
• 2. Applications
• 3. Steps to solve a DP Problem
• 4. Approaches to Dynamic Programming
• 5. Example: Fibonacci Sequence
• 6. Example: Knapsack Problem
• 7. Leetcode Problems
• 8. References

1 Introduction to Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure, which are described below:

• Overlapping subproblems

  A problem has overlapping subproblems if it can be broken down into subproblems which are reused several times. For example, in the Fibonacci sequence, to calculate Fib(5), one needs Fib(4) and Fib(3), but Fib(4) itself requires Fib(3) and Fib(2). Here, Fib(3) is calculated multiple times, which is an overlapping subproblem.

• Optimal substructure

  A problem has an optimal substructure if an optimal solution to the problem contains within it optimal solutions to the subproblems. For instance, in the shortest path problem, if the shortest path from point A to point C goes through point B, then the shortest path from A to B is also part of the shortest path from A to C.

Generate cross compile toolchain in Gentoo

Gentoo crossdev

Table of Contents

• 1. Introcution
• 2. References

1. Introcution

Crosstool-ng is commonly used to build a cross-compiler toolchain in various Linux distributions. In Gentoo, the cross-compiler environment generator, crossdev, has been made for our convinience. It is a set of bash scripts that utilize emerge to provide a system integrated cross-compilation capability.

In this article, we are going to walk through building cross-compiler toolchain for an operating system and the embedded target (bare matel).

Emerge to install crossdev.

$ sudo emerge --ask sys-devel/crossdev

Install and run docker on gentoo linux

Table of Contents

• 1. Introduction
• 2. Installtion
• 3. Configuration
• 4. Usage
• 5. References

1 Introduction

Docker is a container virtualization environment that can establish development or runtime environments without modifying the host operating system. It is faster and lighter than full hardware virtualization.

This article will guide you through the steps required to install and run Docker on Gentoo Linux.

2 Installtion

The official sys-kernel/gentoo-kernel-bin package supports running Docker.

For the customized kernel, refer to Docker: Kernel to configure the proper kernel options.

Default USE flags can be utilized. It is recommended to read the messages for the package app-containers/docker when emerging Docker and recompile the kernel based on what is not set but should be.

To check the kernel configuration compatibility, run:

$ /usr/share/docker/contrib/check-config.sh

Install the app-containers/docker and app-containers/docker-cli packages.

$ sudo emerge --ask --verbose app-containers/docker app-containers/docker-cli

Connect USB device to WSL

Table of Contents

• 1. Introduction
• 2. Prerequisites
• 3. Attach a USB device
• 4. References

1 Introduction

This article will guide you through the steps required to connect a USB device to Linux running on Windows Subsystem for Linux (WSL).

2 Prerequisites

• Install WSL and ensure it is updated to the latest version.

For installation guidance, refer to How to install Linux on Windows with WSL

• Install a Linux distribution configured to WSL 2.

Heap and Priority Queue

Table of Contents

• 1. Introduction to Heap and Priority Queue
• 2. What are the applications of Heap and Priority Queue?
• 3. Heap in C++ standard library
• 4. Priority Queue in C++ standard library
  • 4.1. Minimum Priority Queue
• 5. The Applications of Priority Queues
• 6. References

1 Introduction to Heap and Priority Queue

A heap is a tree-based data structure that adheres to the heap property: in a max heap, any parent node's key (value) is greater than or equal to the keys of its children. Conversely, in a min heap, the key of a parent node is less than or equal to the keys of its children.

For more details, refer to Wikipedia: Heap (data structure).

A priority queue is an abstract data type similar to a regular queue or stack, where each element has an associated priority. Elements with higher priority are served before those with lower priority.

For more details, refer to Wikipedia: Priority queue.

Although they are conceptually different, priority queues are often referred to as heaps because they are commonly implemented using heaps.

The binary heap is a data structure that efficiently supports the basic priority queue operations. It allows O(1) performance for accessing the root, O(log n) for insertions and deletions, and O(n) for initially building the heap from a set of n elements.

Note that the time complexity to build a heap is O(n log n) using a top-down approach, whereas a bottom-up approach achieves O(n).

Monotonic Stack

Table of Contents

• 1. Introduction to monotonic stack
• 2. What can monotonically increasing stacks do?
  • 2.1. To find the previous less element of each element in a vector with O(n) time.
  • 2.2. To find the next less element of each element in a vector with O(n) time.
• 3. What can monotonically decreasing stacks do?
• 4. When are monotonic stacks used?
• 5. The applications of monotonic stacks
• 6. References

1 Introduction to monotonic stack

A monotonic stack is a stack whose elements are monotonically increasing or decreasing.

If we pop greater elements from the stack before pushing a new element, the stack will increase from bottom to top. If we pop lesser elements, the stack will decrease.

The typical paradigm for an increasing monotonic stack is like:

for (int i = 0; i < A.size(); i++) {
    while (!stk.empty() && stk.top() > A[i]) {
        stk.pop();
    }
    stk.push(A[i]);
}

2 What can monotonically increasing stacks do?

Monotonically increasing stacks can be used to solve a variety of algorithmic problems. One common use case is for finding the nearest greater element in an array. By maintaining a stack of elements in increasing order, we can quickly determine the next greater element for each element in the array. Monotonically increasing stacks can also be used for finding the maximum area of a histogram, as well as for solving problems related to dynamic programming and graph algorithms.

2.1 To find the previous less element of each element in a vector with O(n) time.

What is the previous less element of an element in a vector? Suppose there is a vector [3, 8, 9, 6], for each element 3, 8, 9, and 6:

• There is no previous less element for 3.
• The previous less element of 8 is 3.
• The previous less element of 9 is 8.
• The previous less element of 6 is 3.

USB Power Delivery EPR Test

Java Collection Framework basics

Introduction to Wi-Fi