someone wants to throw a party and is deciding whom to invite. He has n mathematicians to choose from, and for each mathematician i, he has Friends[i], which is a linked list of i's friends among the n mathematicians. He wants to pick as many people as possible subject to the constraint that each invited mathematician has at least 10 of their friends at the party. Give an efficient greedy algorithm that takes as input the list of n mathematicians and the lists of their friends, and outputs the largest possible set of party invitees. Assume that friendship is symmetric.

(a) State this problem as a graph problem: what is the input graph G =(V,E) That is, what are the vertices? What are the edges? What is the set of

invitees in graph-theoretic terms (is it a subset of edges or vertices and with what properties)?

(b) Describe your greedy algorithm in plain English. In what sense is your algorithm greedy?

(c) Give a formal proof of correctness for your algorithm.

(d) Describe your algorithm in pseudocode.

(e) State and justify the running time of your algorithm.