Solve the problems below. Your answers do not have to be long, but they should be complete, precise, concise and clear. Write the solutions on your own and acknowledge your sources in case you used “library” material. It is preferred that you type your work using your favorite software package but you submit only in pdf.
Explain your reasoning in detail in the questions below.
- Three topics have been covered in a course. The professor told the students that two among these will be assigned for study and among these two just one will be selected for the exam which all students must answer. How many questions should a (lazy) student study for in order to ensure s(he) can answer the question?
- The distributed computing course has covered T topics. The professor tells the students that A among these will be assigned for study and among these A just S will be selected for the exam which all students must answer. What’s the minimum number N of questions that a lazy student must study so as to ensure all S questions are in the final exam list?
1. [2 pts] Apply the greedy sequential coloring algorithm discussed in class to such an interval unit interval graph. In the pseudo-code place the vertices in order of their left endpoint,