Learning Algorithms from scratch

You may be thinking why one need to learn algorithms after having 10 years of experience, but it is the question of survival for many as today’s time once again moving back to old programming era where computer scientist deriving programs based on mathematics, designing algorithms before they write any program e.g. AI/ML.

After realising some sense of lacking in our mundane work culture where we don’t do programming but under the hood of it we do all things other than programming. Funny things is that we still get the title as Software Programmer, Programmer Analyst J and when you get older in the organisation you promotes to the Sr. roles.

It’s my genuine effort to improve myself as well my other friends who are victim of such jobs where although we graduated as Computer Science Engineers but doing some excel or cosmetic works. I am attempting to fill the gap we had by starting my learning with building blocks of computer i.e. Algorithms. I would definitely need your help in this voyage to find the gems of actual programming and develop ourselves for right job.

If we start from elementary level there are various methods used to design algorithms –

  1. Greedy Approach
  2. Divide and Conquer
  3. Dynamic Programming
  4. Backtracking
  5. Branch and Band
  6. Linear Programming
  7. Integer Programming
  8. Neural Networks
  9. Genetic Algorithms
  10. Simulated Annealing

We will aim here to gain mastery on various algorithm techniques which will give us power to deep dive into specific areas as required.

Greedy Algorithm Method

  • This approach tries to construct solution in stages.
  • To find solution to the given problem we need to make best decision based on given constraint in the problem.
  • Once taken decision cannot be changed in subsequent stages, therefore, the decision should be feasible and with optimal cost.
  • This method just focuses on current stage rather than problem as a whole, so it may not produce optimal solution that we desire but it can be used in certain scenarios where the nature of problem seeks quicker solution with somewhat optimizations.

We will see the few standard examples of Greedy approach and then we will conclude when to use and when not to use this.

Container Loading Problem

We have one Cargo ship which can be loaded with max 400 Kg, ABC Corporation want to deliver below container to the New York from Mumbai. Can you find how would you send maximum number of containers to New York?

Let’s understand the problem first, we have 8 containers with particular amount of weight laden inside it. We have constraint here that we can load Cargo with max 400 KG of weight, and along with that we have to achieve the optimal solution by loading maximum container into Cargo ship.

One very simple solution we see at first glance is we can load containers which are having minimum weight, right? Yes, you are right, but to achieve this we need to sort the container in increasing order of weight – as shown below.

Program Implementation

Let’s see how we can write a simple program to by writing greedy logic to solve this problem. As explained above the first part is to sort the containers and the second part is to select the one with least weight than ship capacity.

class Program
{
        static void Main(string[] args)
        {
            Console.WriteLine("********Container Loading Greedy Approach************");

            List containers = new List();

            var c1 = new Container { ID = 1, Weight = 150 };
            var c2 = new Container { ID = 2, Weight = 120 };
            var c3 = new Container { ID = 3, Weight = 100 };
            var c4 = new Container { ID = 4, Weight = 90 };
            var c5 = new Container { ID = 5, Weight = 150 };
            var c6 = new Container { ID = 6, Weight = 50 };
            var c7 = new Container { ID = 7, Weight = 20 };
            var c8 = new Container { ID = 8, Weight = 70 };

            
            containers.Add(c1);
            containers.Add(c2);
            containers.Add(c3);
            containers.Add(c4);
            containers.Add(c5);
            containers.Add(c6);
            containers.Add(c7);
            containers.Add(c8);
            
            ContainerLoading cargo = new ContainerLoading();
            var loaded = cargo.ContainerLoadingSolution(containers, 500);

            Console.WriteLine("\n    ID : Weight");

            foreach (var item in loaded)
            {
                Console.WriteLine("\n    C" + item.ID + " : " + item.Weight);                
            }                       

            Console.WriteLine("\n\n    Number of Containers: "+ loaded.Count() + " | Total Weight: "+ loaded.Sum(x=>x.Weight) +"kg") ;
        }
}

public class Container
{
        public int ID { get; set; }
        public int Weight { get; set; }
        public bool IsSelected { get; set; }
}

public class ContainerLoading
{
        public List ContainerLoadingSolution(List containers, int capacity)
        {
            int remaningCapacity = capacity;

            //Sort the container in increasing order of their weight
            var sortedContainer = containers.OrderBy(x => x.Weight);

            foreach (var item in sortedContainer)
            {
                if (item.Weight <=remaningCapacity)
                {
                    item.IsSelected = true;
                    remaningCapacity -= item.Weight;
                }
                else
                {
                    item.IsSelected = false;
                }
            }

            return sortedContainer.Where(x=>x.IsSelected).ToList();            
        }
}

When to consider Greedy Algorithm Method

  • As we saw Greedy approach to solve the problem, which is purely based on the decision we made initially to reach the optimal solution. However, it can be worse in case decision goes wrong in case input data changes dynamically. Consider below example of path finder – it returns best path as 55 instead of 5, because it’s decision was greedy and it worked well for first but failed in next stage.

  • It does not mean that we cannot use this method anywhere, think of the scenario where problem is bound to certain time limit and input data range is huge then Greedy works magically and though it not offers best solution but tries to give you average optimum solution than manually solving the problem. It gives us global optimum solution in faster manner.
  • In real time Greedy algorithm technique is being used in gaming, operating system job scheduling, meeting room scheduling. Please comment below if you know any more real time usage of Greedy technique.

Wait for second article in the line on next algorithm technique…

Be the first to comment

Leave a Reply

Your email address will not be published.


*