DEV Community: Naime Molla

Introduction to Dynamic programming

Naime Molla — Thu, 26 Jan 2023 17:15:55 +0000

You will learn about dynamic programming in this tutorial using a beginner's approach. Why DP is so important for writing effective code? And two essential techniques for solving dynamic problems. Let's start with a great and powerful technique for writing beautiful and efficient code.

What is dynamic programming?

Dynamic programming is a method of solving problems by breaking them down into smaller, overlapping subproblems. The solutions to these subproblems are then stored in a table so that they can be reused instead of recalculating them each time they are needed. This can greatly reduce the time and space complexity of a problem, making it much more efficient to solve.

Why we need to know about dynamic programming technic?

Many problems that seem intractable at first glance can be solved relatively easily with dynamic programming. This is because dynamic programming breaks down a problem into smaller, overlapping subproblems, and stores the solutions to these subproblems in a table, making it possible to reuse them instead of recomputing them each time they are needed.

Dynamic programming can often be used to find optimal solutions to problems, rather than just any solution. For example, dynamic programming can be used to find the shortest path between two nodes in a graph, or the longest common subsequence between two strings.

Many problems that are NP-hard can be solved in polynomial time using dynamic programming. This is because dynamic programming reduces the time complexity of a problem by breaking it down into smaller subproblems, and reusing the solutions to these subproblems instead of recomputing them each time they are needed.

What is the difference between a Dynamic programming technic and recursion?

Dynamic programming and recursion are two different techniques used to solve problems. The main difference between them is the way they approach a problem and store the solutions to subproblems. Dynamic programming stores the solutions to subproblems in a table, so they can be reused instead of recomputing them each time they are needed. This greatly reduces the time complexity of a problem, making it more efficient to solve. Recursion, on the other hand, breaks down a problem into smaller subproblems and solves them recursively, without storing the solutions. This can lead to a lot of duplicate work, and can make a problem very slow to solve, but it's often simpler to implement. Both methods have their own advantages and disadvantages and a problem can be solved using both methods, the choice of which method to use depends on the specific problem and the desired trade-off between time complexity and ease of implementation.

How to Identify if it is a Dynamic programming problem?

There are several ways to identify if a problem is a dynamic programming problem. One way is to look for overlapping subproblems, which occur when the same subproblem is solved multiple times with different inputs. Another way is to look for a problem that can be broken down into smaller subproblems, where the solution to the original problem can be constructed from the solutions to the subproblems.

Techniques to solve Dynamic Programming Problems.

There are several techniques that can be used to solve dynamic programming problems, including memoization, tabulation, and the use of recurrence relations. These techniques involve storing the solutions to subproblems in a table and reusing them instead of computing them each time they are needed. I will write more details about these technic next time. stay connected.

Let's take the example of Fibonacci series. The Fibonacci series is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.

// Fibonacci series using Dynamic programming (python code)
def fib(n, lookup):
  if n <= 0:
    lookup[n] = 0
    return 0
  if n == 1:
    lookup[n] = 1
    return 1
  if lookup[n] == None:
    lookup[n] = fib(n-1, lookup) + fib(n-2, lookup)
    return lookup[n]
n = 70
lookup = [None]*(101)
print("Fibonacci Number is : " , fib(n, lookup))

In this example, we are using the technique of memoization to store the solutions to subproblems in a table, and reusing them instead of recomputing them each time they are needed. This greatly reduces the time complexity of the problem, making it much more efficient to solve. Your computer will can't calculate the Fibonacci number of 70 with commonly used techniques. This is the power of dynamic programming.

In conclusion, dynamic programming is a powerful method of solving problems that can greatly reduce the time and space complexity of a problem. By breaking a problem down into smaller, overlapping subproblems, and storing the solutions to these subproblems in a table, we can greatly improve the efficiency of our algorithms. Feel free to reachout me to discus about problem solving.

Simple overview of MySQL (Relational Database)

Naime Molla — Fri, 24 Dec 2021 13:26:09 +0000

What is MySQL:

MySQL is a Widely used relational database management system. It's free and open-source and ideal for both small and large applications. It's very fast, reliable, scalable and easy to use.

Who uses MySQL?

Most popular websites like Facebook, Twitter, Airbnb, Uber, YouTube, GitHub, etc. Content Management Systems like Wordpress, Joomla, Drupal, Contao, etc. A huge number of web developers around the world use MySQL as a database management system.

Show Data on your website:

If you want to show data in your website from a database, you will need:

An RDBMS database program like MySQL.
A server-side scripting language, like PHP.
To use SQL to get the data you want.
To use HTML/ CSS to style the page.

RDBMS:

RDBMS stands for Relational Database Management system. It's a program used to maintain a relational database. RDBMS is the basis for all modern database systems such as MySQL, Oracle, Microsoft SQL server and Microsoft Access.

Database Table:

A table is a collection of related data entries, and it consists of columns and rows. A column holds specific information about every record in the table. A Record or row is each individual entry that exists in a table.
Look at this table:

The columns in the table above are: CustomerID, CustomerName, ContactName, Address, City, PostalCode and Country. The table has 5 records.

Explain Relational Database:

A Relational database defines database relationships in the form of tables. The tables are related to each other - based on data common to each.

Look at the following three tables "Customers", "Orders" and "Shippers" database

Customers Table

The relationship between the "Customers" table and the "Orders" table is the CustomerID column.

Orders Table

The relationship between the "Orders" table and the "Shippers" table is the SipperID column.

Some Most important SQL Commands:

INSERT - Insert new data into a database
SELECT - extract data from a database
UPDATE - updates data in a database
DELETE - deletes data from database
CREATE DATABASE - creates a new database
AlTER DATABASE - modifies a database
CREATE TABLE - creates a new table
ALTER TABLE - modifies a table
DROP TABLE - deletes a table
DROP INDEX - deletes an index
CREATE INDEX - creates an index

What's new changes and features in React Router v6.

Naime Molla — Wed, 22 Dec 2021 12:42:19 +0000

In the React ecosystem, React Router is the most used and popular library. It's downloaded about 3.6 million times a week, according to npm. This amount is almost half of React's 7.6 mmillion weekly downloads. That means React Router used almost half of the React project. The latest version of React Router 6 has created a lots of buzz in the React community. So, Without further ado, Let's explore some new changes and features of React Router.

Routes Replaces Switch:

In latest version is replaced with . Routes component has a new prop called element, where you can pass the component it needs to render.

Example:  
<Routes>
  <Route path="user/:id" element={<User />} />
  <Route path="users/new" element={<NewUsers />} />
</Routes>

In this change, we don't need to concern about the order anymore because Routes picks the most specific routes fisrt based on the current URL.

Use "useNavigate" instead of "useHistory":

The old useHistory hook has been removed and replaced with a suspense-ready navigate API. Now you should use "useNavigate" to programmatically navigate around your application. To redirect your user, they expose a navigate comonent.

Exaple: 

import { Navigate, useNavigate } from 'react-router-dom';

function Redirect() {
  return <Navigate to="/home" replace />;
}

function GoHomeButton() {
  let navigate = useNavigate();
  function handleClick() {
    navigate('/home')
  }
  return (
    <div>
      <button onClick={handleClick}>Go to home page</button>
    </div>
  );
}

Replace "useRouteMatch" with "useMatch":

useMatch is to mush similar to v5's useRouteMatch, with a few key differences:

It uses new path pattern matching algorithm
The pattern argument is now required
No longer accepts an array of patterns
When passing a pattern as an object, some of the options have been renamed to better align with other APIs in v6

useRouteNatch({strict}) is now useMatch({end})
useRouteMatch({sensitive}) is now useMatch({caseSensitive})
It returns a match object with a different shape

Nested Route:

Nested Route is the most important and useful feature in react router. We use it so many time specially in larg and complex application. In latetst version of react router dom, we notice some changes on it. Look at this code

import {
  BrowserRouter,
  Routes,
  Route,
  Link,
  Outlet
} from 'react-router-dom';

function App() {
  return (
    <BrowserRouter>
      <Routes>
        <Route path="/" element={<Home />} />
        <Route path="users" element={<Users />}>
          <Route path="/" element={<UsersIndex />} />
          <Route path=":id" element={<UserProfile />} />
          <Route path="me" element={<OwnUserProfile />} />
        </Route>
      </Routes>
    </BrowserRouter>
  );
}

function Users() {
  return (
    <div>
      <nav>
        <Link to="me">My Profile</Link>
      </nav>

      <Outlet />
    </div>
  );
}

If you compare this code with previous nested route system code, you will notice few things:

In latest version we are using to coecify nested routes! The URL paths nest along with the route elements, so /users/me renders .
We used an element as a placeholder. Here define how the User component renders its child routes. Depending on the current location, will render either a or element.

Smaller Bundle Size:

The React Router authority claims that the new version is a lot smaller than the previous versions. Authority estimate that it's about 70% smaller. Your application loads faster, especially over slow/poor network connections and content to your user faster for smaller bundles.

Hopefully this post has given you some clear-sightedness into the latest version of React Router v6. I hope it has also given you some ideas about how you can get started with it and use it in your application. If there is any mistake. Please let me know.