DATA STRUCTURES AND ALGORITHM

Data structures of a computer is a specialized format of arranging and storing data for easier access and faster manipulation and storage. It can also be seen as the collection of all data values and data manipulation structures and the relationships amongst them including the possible operations that can be performed on/by them.

 

Data types

They are organized formats of storing data for error free manipulation. Some standard data types are: String, Integers, Boolean, and Character. In most cases, special definitions are made for easier handling of bulk data. Other data types (Derived ) are: Array, Stack, Queue, File, Linked List, Record, Table, Tree, etc.

Generally, data types are of two categories (System defined – the structure, storage space, and manipulation mechanism of these data types are predefined. You have no control over them but can only use them. This includes integer, floating point, bool, character and double.  The second is User Defined – one that you define the structure, storage mechanism and space. E.g classes. )

Abstract Data Types(ADT) They are user defined datatypes with proper definition of its data structure and possible operations that it can be used to perform.

 

Variable: It is a unique definition and reservation of memory whose value can change in the course of a program block. Depending on the definitions, variables can hold only one type of data or is open to any type of data.

 

Pointers: They are mainly registers. They basically hold the address locations of other variables.

 

Iteration: In programming repeating a block of instruction is very common. This is called a loop. A single instance of execution of instructions in a loop is called an Iteration. E.g

public class addnumbers {

public static void main (String args[]){

int j=1;

for (int i=1;i<=4;i++){

j=i*j;

}

System.out.println(j);

} }

 

Below is the value of j after each iteration

 

Value of J Iteration
1 First
2 Second
6 Third
24 Forth

 

Subprogram: A sequence of instructions packaged as a unit to perform a specific sub task within a main program. This can be called upon at any point of the main program to perform the defined task. Depending on definition, subprograms can accept inputs, return outputs, do both, or return nothing (null). Every subprogram must be defined with certain properties such as the scope, input  type, output type, and unique name.

 

Recursion: It works like a loop (in fact it is a loop) but the only difference is that it has the ability to call itself within the loop(Though sometimes on a smaller scale). The tree below was done by recursion using MSW LOGO

 

Modular design:

This is a design approach that subdivides a whole system into various parts (or  subsystems or modules) which can be completed individually and later assembled to make the whole. It is very common amongst programmers working on a whole software solution. They usually have to build individual modules and collaborate using GitHub. This is also applicable in the design of a car where each component part is designed in separate units of the factory and later brought together. The major factor for modularization is FUNCTION, the parts are broken apart based on function.

The advantages are: Faster production, Reduced risks (safety), Higher yields and quality, Reduced cost of production, etc

 

Algorithm: An algorithm is a carefully constructed step-by-step procedure to solve a GIVEN problem.

 

Characteristics of algorithms:

 

Precise Must have a well defined  procedure
Uniqueness Each steps must make a unique attempt that moves the solution closer to accomplishment
Finiteness There must be a start and an end
Generality ?
Input Should be able to receive input
Output Should be able to produce and output

 

Different types of algorithms:-

(source: http://gonitsora.com/algorithm-types-and-classification/)

Every algorithm falls under a certain class.

Basically they are-

1)   Brute force

2)   Divide and conquer

3)   Decrease and conquer

4)   Dynamic programming

5)   Greedy algorithm

6)   Transform and conquer

7)   Backtracking algorithm

Brute force algorithm:-

Brute force implies using the definition to solve the problem in a straightforward manner.

Brute force algorithms are usually the easiest to implement, but the disadvantage of solving a problem by brute force is that it is usually very slow and can be applied only to problems where input size is small.

Divide and conquer algorithm:-

In divide and conquer method, we divide the size of a problem by a constant factor in each iteration. This means we have to process lesser and lesser part of the original problem in each iteration. Some of the fastest algorithms belong to this class. Divide and conquer algorithms have logarithmic runtime.

Decrease and conquer algorithm:-

This kind of problem is same as divide and conquer, except, here we are decreasing the problem in each iteration by a constant size instead of constant factor.

Dynamic programming:-

The word ‘dynamic’   refers to the method in which the algorithm computes the result. Sometimes, a solution to the given instance of problem depends on the solution to smaller instance of sub-problems. It exhibits the property of overlapping sub-problems. Hence, to solve a problem we may have to recompute same values again and again for smaller sub-problems. Hence, computing cycles are wasted.

To remedy this, we can use dynamic programming technique. Basically, in dynamic programming, we “remember” the result of each sub-problem. Whenever we need it, we will use that value instead of recomputing it again and again.

Greedy algorithm:-

For many problems, making greedy choices leads to an optimal solution. These algorithms are applicable to optimization problems.

In a greedy algorithm, in each step, we will make a locally optimum solution such that it will lead to a globally optimal solution. Once a choice is made, we cannot retract it in later stages.

Proving the correctness of a greedy algorithm is very important, since not all greedy algorithms lead to globally optimum solution.

For ex- consider the problem where you are given coins of certain denomination and asked to construct certain amount of money in inimum number of coins.

Let the coins be of 1, 5, 10, 20 cents

If we want change for 36 cents, we select the largest possible coin first (greedy choice).

According to this process, we select the coins as follows-

20

20 + 10

20 + 10 + 5

20 + 10 + 5 + 1 = 36.

For coins of given denomination, the greedy algorithm always works.

But in general this is not true.

Consider the denomination as 1, 3, 4 cents

To make 6 cents, according to greedy algorithm the selected coins are 4 + 1 + 1

But, the minimum coins needed are only 2 (3 + 3)

Hence, greedy algorithm is not the correct approach to solve the ‘change making’ problem.

Infact, we can use dynamic programming to arrive at optimal solution to this problem.

Transform and conquer:-

Sometimes it is very hard or not so apparent as to how to arrive at a solution for a particular problem.

In this case, it is easier to transform the problem into something that we recognize, and then try to solve that problem to arrive at the solution.

Consider the problem of finding LCM of a number. Brute force approach of trying every number and seeing if it is the LCM is not the best approach. Instead, we can find the GCD of the problem using a very fast algorithm known as Euclid’s algorithm and then use that result to

 

Backtracking algorithm:-

Backtracking approach is very similar to brute force approach. But the difference between backtracking and brute force is that, in brute force approach, we are generating every possible combination of solution and testing if it is a valid solution. Whereas, in backtracking, each time you generate a solution, you are testing if it satisfies all condition, and only then we continue generating subsequent solutions, else we will backtrack and go on a different path of finding solution.

A famous example to this problem is the N Queens problem. According to the problem, we are given a N X N sized chessboard. We have to place N queens on the chessboard such that no queens are under attack from any other queen.

We proceed by placing a queen in every column and appropriate row. Every time we place a queen, we check whether it is under attack. If so, then we will choose a different cell under that column. You can visualize the process like a tree. Each node in the tree is a chessboard of different configuration. At any stage if we are unable to proceed, then we backtrack from that node and proceed by expanding other nodes.

An advantage of this method over brute force is that the numbers of candidates generated are very less compared to brute force approach. Hence we can isolate valid solutions quickly.

Ex- for an 8 X 8 chess board, if we follow brute force approach, we have to generate 4,426,165,368 solutions and test each of them. Whereas, in backtracking approach, it gets reduced to 40,320 solutions.

 

Analysis of algorithm (find it in the textbook sent to us on page 54-81

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: