IGNOU MCA 3rd Semester Solved Assignment For 2016-2017 Session

MCS 031

Discuss some real world problems, to which the techniques given below are applicable. 

Discuss some real world problems, to which the techniques given below are applicable
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach

Divide and Conquer in real world

I am going to explain using real world systems around us

Government and Company: 

In real world, Government follows the divide and conquer approach to get all problem listed and resolve. Using State Leaders, District Leaders, Block Leader, Village Leader etc. 

Similar for the company, suppose someone purchased a Product from Cipla, and He received an outdated product from store. For this problem He can't complain directly to CEO of Cipla. 

CEO > Managers of different fields > Territorial Manager > Area Manager > Local Distributor > Then Local Shop/Store

By this chain they can easily find the problem and solved in mannered way. 

Simple word, We can solve a big problem in small pieces and solve it, after solving each merge them together. 

So basically, divide any big problem into smaller problems (to make our life easy), solve individual problems and combine the solution of small problems to get the solution to big problem. Note that sometimes, there is no need for combining solutions of small problems.

Dynamic programming in real life

Dynamic programming used to avoid repetitive work. That can be achieve by remembering partial results.

Real World Problem : Min-Num-Coins

(Gives the minimum number of coins for Given Amount)

In Automated shop, someone purchased goods of Rs. 389, After billing Machine start showing few combination of change to achieve the Amount 389. Customer will select a combination and give the money. Similar If customer paid 500 to pay 389 then Shopkeeper will also calculate the change with minimum coins.

Aircraft stand assignment to minimize walking

Gate scheduling is concerned with assigning flights to terminal or ramp positions, called gates. It is a key activity in airport operations. With the increase of civil air-traffic and the corresponding growth of airports in the past decades, the complexity of the task has increased significantly. At large international airports, several hundreds of flights must be handled per day.

Greedy Approach in real world

Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.

The interval scheduling maximization problem (ISMP) is to find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible.