Re: [algogeeks] coloring problem Dynamic programming
Saurabh your solutions seems right , but can u explain me how did u arrive at the time and space complexity with some proof /pseudocode/ explanation? On 15 December 2013 09:47, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
No need for the explanation ,got it man thanks. On 15 December 2013 16:20, kumar raja rajkumar.cs...@gmail.com wrote: Saurabh your solutions seems right , but can u explain me how did u arrive at the time and space complexity with some proof /pseudocode/ explanation? On 15 December 2013 09:47, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
What can be the recurrence relation if the condition is changed to No 3 adjacent houses should get same color? On 15 December 2013 16:26, kumar raja rajkumar.cs...@gmail.com wrote: No need for the explanation ,got it man thanks. On 15 December 2013 16:20, kumar raja rajkumar.cs...@gmail.com wrote: Saurabh your solutions seems right , but can u explain me how did u arrive at the time and space complexity with some proof /pseudocode/ explanation? On 15 December 2013 09:47, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
