Hi All,
Please try to provide solutions to the below problems.
1) For any given polynomial algorithm A for a decision problem, we can
associate a language L = { x | A(x) = 1 } i.e., all such inputs. If P
is the set of all such languages (remember polynomial time of A), is P
closed under Kleene Star? Note that P is closed under union,
intersection, complement and concatenation.
2) Task scheduling. We are given N tasks. Task Ai takes Ti amount of
time and has a deadline Di finishing the task within deadline leads to
a profit of Pi. We want to schedule the tasks so that there is maximum
profit. Will greedy approach in this case? If all the numbers involved
are integers then can we dynamic programming to solve this polynomial
time? If the numbers are real, prove that the problem is NP-C.
Thanks.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
