Dynamic Programming Problem #3 : Equal Sum Partition

Image for post
Image for post
Photo by Emile Perron on Unsplash

Before starting up with the Equal Sum Partition Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Equal Sum Partition Problem. I’d also highly recommend you to go through the Subset Sum Problem since it’s the parent problem for Equal Sum Partition Problem.

With that being said, let’s get started.

1. What is Equal Partition Sum Problem ?

Given a set of N non-negative integers, determine if the set can be partitioned into two subsets such that the sum of the elements in each of the two subsets is equal. …


Dynamic Programming Problem #2 : Subset Sum

Image for post
Image for post
Photo by Safar Safarov on Unsplash

Before starting up with the Subset Sum Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Subset Sum problem. I’d also recommend to go through the Knapsack Problem since it’s the parent problem for Subset Sum Problem.

With that being said, let’s begin!

1. What is Subset Sum Problem ?

Given a set of N non-negative integers and a target sum S, determine if there exists a subset of the given set such that the sum of the elements of the subset equals to S. …


Dynamic Programming Problem #1 : 0–1 Knapsack

Image for post
Image for post
Photo by Emile Perron on Unsplash

Before starting up with the Knapsack Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Knapsack problem.

With that being said let’s begin !

What is 0–1 Knapsack ?

The problem of 0–1 Knapsack goes something like this.

We are given an empty bag that can hold maximum of W weight. We have a set of N items. Each item has an associated value v and an associated weight w. …


Getting started with Dynamic Programming

Image for post
Image for post
Photo by Emile Perron on Unsplash

1. What is Dynamic Programming ?

In simple words one can say that it is an optimisation over plain recursion technique. This is achieved by reducing the number of recursive calls, either by storing the intermediate computed values or by deriving the final computation based on some kind of logical relation. This ultimately leads to reduced time complexities, thereby improving the overall performance of the solution.

Since it’s a programming paradigm thus it has nothing to do with being specific to a particular language or set of programming languages.

With that being said let’s dive into Dynamic Programming.

2. Recursion, Tabulation & Memoization

The key to understanding any problem’s solution that employs the use of Dynamic Programming (commonly referred to as DP), is Recursion. One must first master the skill to code up a recursive solution for the same problem. Building a DP based solution using either Tabulation or Memoization can then be very easily done with the help of the recursive code. …


Getting started with STL in C++

Image for post
Image for post
Photo by Fotis Fotopoulos on Unsplash

What are Maps in STL ?

Maps are nothing but a type of associative container which stores elements in the form of key-value pairs. For those of you who are familiar with python, you can think of maps like a dictionary in python.

A key in map is used to uniquely identify the element and the value contains the corresponding stored data. Thus a key has to be unique and cannot repeat but the values can be same for two different keys.

Eg :

Enrolment Number : Name

Here Enrolment Number is the key and Name is the corresponding value. The data type of the key and value may or may not be the same. …


Getting started with STL in C++

Image for post
Image for post
Photo by Clément H on Unsplash

The Standard Template Library (STL) is a very useful set of template classes containing various containers. One among these containers is Lists. Today we’ll be having a look at Lists in STL. But before we proceed further I’d like to say that if this is your first time learning STL then I’d recommend you have a look at this article before beginning with this one.

With that being said let’s dive further into the topic by knowing what are lists in STL ?

A. Lists in STL

Lists are a type of sequence containers which provides us with constant insertion and deletion time anywhere within the sequence given that we have obtained the corresponding iterator to the same. …


Getting started with STL in C++

Image for post
Image for post
Photo by Safar Safarov on Unsplash

Iterators

Iterators are something which is used to point at the memory addresses of STL containers’ elements. Thus providing a means to access the data stored within the container and ability to modify them. They can be simply thought of as pointers.

Why Iterators ?

We need iterators in order to manipulate the containers. Containers on their own cannot be modified unless we make use of an iterator or a member function. The purpose is to isolate the user from the internal structure of the container thus helping with abstraction.

They provide a bridging or a connection between the algorithms and containers by allowing the algorithms to operate on the containers via them. …


Getting started with STL in C++

Image for post
Image for post
Photo by Maxwell Nelson on Unsplash

The Standard Template Library (STL) in C++ is nothing but a set of template classes which provides us with the widely used data structures such as lists, stacks, maps, etc. along with iterators, functions and algorithms in order to play around with the data elements.

A. Main Components of STL

  1. Containers

Containers are nothing but holder objects which stores other objects i.e. it’s elements. A container does the memory management for its elements and provides us with member functions or iterators in order to interact with it’s data elements.

2. Algorithms

Algorithms, defined under the header <algorithm>, are nothing but a collection of several functions which are designed in order to used on any sequence of elements that can be accessed using iterators or pointers. One thing to note about algorithms is that they do not change the way a data structure is organised in any way. …

About

Tanishq Vyas

Student at PES University.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store