Tanya Anand - OpenGenus IQ: Learn Computer Science

Longest Palindromic Subsequence: Reducing complexity from O(2^N) to O(N^2)

The longest palindrome subsequence problem (LPS) is the problem to find longest subsequences of a string that is also a palindrome. We will see two solutions one which is a naive solution and the other is a dynamic programming approach where we will reduce the time complexity from O(2^N) to O(N^2)

dynamic programming

Longest Bitonic Sequence

The problem we will solve is given a sequence an array of positive integers and have to find the length of longest bitonic subsequence. Using dynamic programming ideas, we will solve this on O(N^2) time complexity

algorithm

Number of arithmetic progression subsequences in a given set of numbers

The problem is that given an array of n positive integers. The task is to count the number of Arithmetic Progression subsequence in the array. This can be solved using dynamic programming in linear time complexity.

algorithm

Find the Longest Arithmetic Progression using Dynamic Programming

The problem we will solve is that given a set of integers in sorted order, find length of longest arithmetic progression in that set. This can be solved by brute force in O(N^3) while a dynamic programming approach with take O(N^2) time complexity.

control statement

switch case control statement

A switch statement allows a variable to be tested for equality against a list of values. Each value is called a case, and the variable being switched on is checked for each case.if variable and case value are matched, then matched case will be executed.

control statement

for loop control statement

A for loop allows us to write a loop that is executed a specific number of times. The loop enables us to perform n number of steps together in one line. We have provided the flow diagram, syntax and example to demonstrate for loop.

control statement

do while loop control statement

A do-while loop is similar to a while loop, except the fact that it is guaranteed to execute at least one time. The do-while loop checks its condition at the bottom of the loop after one time execution of do.

control statement

While loop control statement

A while loop is a control flow statement that allows code to be executed repeatedly based on a given condition. We have provided a flow chart, syntax and programming example to demonstrate while loop

control statement

if-else control statement

if else is a programming construct/ concept for controlling the flow of program execution. The basic idea is to execute different code depending upon the outcome of an expression.