Longest Common Sub-Sequence

The longest common subsequence (LCS) problem is very popular in computer science. This problem can be solved by dynamic algorithm. We can define this problem to find the longest subsequence common to all sequences in a set of sequences (often just two sequences).

Let A  = {1,3,4,6,8}
B = {7, 3,2,4,6,10,8}

LCS (A,B) = {3,4,6,8} , Length = 4;

Longest Decreasing Subsequence

Read : Longest Increasing Subsequence
Dynamic Programming:

Longest Increasing Subsequence

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. he longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.
Example:
In the first 16 terms of the binary Van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

a longest increasing subsequence is

0, 2, 6, 9, 11, 15.

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15

are other increasing sub sequences of equal length in the same input sequence [Wiki].
Dynamic Problem:

Maximum Subarray Problem

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984). [Wiki]

Example:
[1] A = {-2,1,-1,1,1,-1,2,1,-5}; [assum, 1st element is indicated by 0]
Maximum Value = 4, start index = 1, End index = 7

[2] A = {-2,1,-2,1,1,-1,2,1,-5}; [assum, 1st element is indicated by 0]
Maximum Value = 4, start index = 3, End index = 7

[3] A = {-2,1,-3,4,-1,2,1,-5,-4}; [assum, 1st element is indicated by 0]
Maximum Value = 6, start index = 3, End index =6

[4] A = {2,3,5,4,6,3,5,4,6};
Maximum Value = 38, start index = 0, End index =8

[5] A = {-1,-2,-3,-4,-5,-6,-7,-8,-9}
Maximum Value = -1, start index = 0, End index =0

Outlaine of Algorithm Design & Analysis Course

Prerequisite courses: 

• CSE 201 (Data Structure) 
• CSE 107 (Computer Programming)/ CSE 207 (Object Oriented Programming

Course Objectives: Computer algorithms are the building blocks in computer programming. This course will give students a comprehensive introduction of common data structures, algorithm design and analysis. Unlike programs, algorithms are not dependent on a particular programming language, machine, system, or compiler. They are mathematical entities, which can be thought of as running on some sort of idealized computer with an infinite random access memory and an unlimited word size. Algorithm design is all about the mathematical theory behind the design of good programs. It makes familiar with fundamental algorithms, algorithmic techniques and analyze the running time of a given algorithm.

Convex Hull (Brute Force Algorithm)

Previous Topics:

• Convex Hull (Introduction)
• Convex Hull( Geometric Primitives)
• Convex Hull ( Geomatric Primitives-I)
• Convex Hull ( Geomatric Primitives-II)
• Convex Hull ( Geomatric Primitives-III)

Find Convex Hull from a Set of Points (Brute Force Algorithm):

---

There are two variants of the convex hull problem:

[1]. Obtain the vertices of the convex hull ( these vertices are also called extreme points);
[2]. Obtain the vertices of the convex hull in some order (clockwise, for example).

Convex Hull ( Geomatric Primitives-III)

Previous Topics:

• Convex Hull (Introduction)
• Convex Hull( Geometric Primitives)
• Convex Hull ( Geomatric Primitives-I)
• Convex Hull ( Geomatric Primitives-II)

Determining Whether a Point Is Inside a Complex Convex Polygon:

---

Figure 1 demonstrates a typical case of a severely concave polygon with 14 sides. The red dot is a point which needs to be tested, to determine if it lies inside the polygon.
The solution is to compare each side of the polygon to the Y (vertical) coordinate of the test point, and compile a list of nodes, where each node is a point where one side crosses the Y threshold of the test point. In this example, eight sides of the polygon cross the Y threshold, while the other six sides do not. Then, if there are an odd number of nodes on each side of the test point, then it is inside the polygon; if there are even numbers of nodes on each side of the test point, then it is outside the polygon. In our example, there are five nodes to the left of the test point, and three nodes to the right. Since five and three are odd numbers, our test point is inside the polygon.

Convex Hull ( Geomatric Primitives-II)

Previous Topics:

• Convex Hull (Introduction)
• Convex Hull( Geometric Primitives)
• Convex Hull ( Geomatric Primitives-I)

Some Geometric Primitives:

---

Now let A(x1,y1) and B(x2,y2) are two point. We draw a line passing through A and B. we have a point q(x3, y3). We have to determine the perpendicular distance from the point q to AB line.

Convex Hull ( Geomatric Primitives-I)

Previous Topics:

• Convex Hull (Introduction)
• Convex Hull( Geometric Primitives)

Some Geometric Primitives:

---

Q1. Let there are two point p1 and p2. Now draw a line through p1 and p2. If we have a point q, we will determine that q is to the left or right of p1p2 line. A solution has been given in previous post ( see the above link). Now I will discuss another simple solution.

Convex Hull( Geometric Primitives)

Previous Topic:

Convex Hull (Introduction)

Some Geometric Primitives:

---

Computing the area of a triangle:
Using Vector:

Let vectors AB and AC point respectively from A to B and from A to C. The area of parallelogram ABDC is then,
                      |AB x AC|
which is the magnitude of the cross product of vectors AB and AC. The area of triangle ABC is half of this,
                      0.5* |AB x AC|

Here AB x AC = |AB||AC| sinθ, so θ determine that angle between AB and AC.

Now you see, point A to B, then point C is to the left of AB (see Fig. (a) . Point C is to the right of AB (see Fig. (b). so, we can say,

For fig. a, AB x AC = |AB||AC| sinθ (positive value) 
For fig. a, AB x AC = |AB||AC| sinθ (negative value) 

Convex Hull (Introduction)

Convex Hull:

---

The convex hull of a set S of points in the plane is defined to be the smallest convex polygon containing all the points of S. we can define a polygon to be convex if for only two points p1 and p2 inside the polygon, the directed line segment from p1 to p2 is fully contained in the polygon