Assembly Line Scheduling This is the second article on Dynamic Programming. You can refer to the first article (introduction) here. Let us get started by defining our problem. Problem definition The following bullet points define our problem: We have two (parallel) car assembly lines (1) and (2). Each assembly line has (n) stations. The time
Introduction This short article is mainly for students, software engineers and those who are struggling to get a grip on the subject. In other words I will not be focusing on the theoretical side of the topic. I will first explain what Dynamic Programming means then provide several examples to demonstrate this algorithmic technique. I
Question Suggest few areas to inspect to improve the performance of a slow query Answer Here are few areas to check: Tables have no indexes. Database indexes improve query performance dramatically on the expense of slow writes and extra space Tables are scanned in full. Scanning huge tables degrades performance Table statistics are not updated.
Greedy algorithm interval scheduling problem An event starts at 9AM and finishes at 6PM. Several volunteers have signed to the event each providing a time period during which they can help. We need to cover the entire time of the event (9AM-6PM) with the least number of volunteers. Assume the next volunteer in line can
Optimized version of bubble sort Bubble sort is a slow comparison based sorting algorithm. Can you suggest one way to optimize it. Optimized bubble sort complexity and solution Bubble sort works by repeatedly visiting all elements of the list to be sorted comparing each pair of adjacent elements and swapping them if they are not
Activity selection problem greedy algorithm Assume that you are an administrator who is in charge of a conference room equipped with some expensive telepresence system. Different employees or groups of employees need to have access to the conference room but they can not use the telepresence system at the same time. Every day employees who
Maximal independent set problem You have a set of radio stations all having the same transmission frequency. Signals from adjacent stations interfere with each other which causes data loss. We need to choose the largest set of stations that can operate at the same time without data loss. Assume the list of stations is represented
Problem Given an amount of money in US currency. Give an algorithm to make change of the given amount using the smallest possible number of coins. Recall that US coins are Dollars (100 cents), Quarters (25 cents), Dimes (10 cents), Nickels (5 cents) and Pennies (1 cent) Solution A greedy approach to solve this problem
Problem Given an array of N integers. The array is expected to contain positive as well as negative numbers. Find the maximum contiguous subsequence sum (MCSS) of the array. For example the MCSS of {2, -4, 1, 2} is 3 which is the sum of the subsequence {1, 2}. A brute force approach requires 3
Maximum contiguous subsequence sum problem Given an array of N integers. The array is expected to contain positive as well as negative numbers. Find the maximum contiguous subsequence sum (MCSS) of the array. For example the MCSS of {2, -4, 1, 2} is 3 which is the sum of the subsequence {1, 2}. A brute
