Answered You can hire a professional tutor to get the answer.
(15 points). UCLA has hired you to write an algorithm to schedule their final exams. Each quarter, UCLA offers n different classes.
2. (15 points).
UCLA has hired you to write an algorithm to schedule their final exams. Each quarter, UCLA offers n different classes. There are r different rooms on campus and t different time slots in which exams can be offered. You are given two arrays E[1..n] and S[1..r] where E[i] is the number of students enrolled in the ith class, and S[j] Is the number of seats in the jth room. At most one final exam can be held in each room during each time slot. Class i can hold its final exam in room j only if E[i] < S[j].
a. (12 pts) Write an algorithm (in bullet form) to assign a room and a time slot to each class (or report correctly that no such assignment is possible).
b. (3 pts) Provide time complexity analysis.
3. (15 points).
Let T be an n-node tree rooted at some node r. We want to place as few guards as possible on nodes of T, such that every edge of T is guarded: an edge between a parent node v and its child w is guarded if one places a guard on at least one of these two nodes v, w.
a. (11 pts) Give an O(n) time algorithm (in bullet form) for finding an optimal solution to the problem (Dynamic programming might be a good approach).
b. (4 pts) Provide time complexity analysis.
4. (20 points).
A (12 pts). In a directed graph, given a start node and an end node, design an algorithm (in bullet form) to find the minimum number of edges that need to be removed so that the start node and end node are disconnected.
B (8 pts). Prove the correctness of your algorithm.
5. (15 points).
a. (3 pts) Provide a polynomial time algorithm for the traveling salesman problem.
b. (2 pts) Does Maximum Clique require exponential time to solve?
c. (10 pts) Show that Maximum Independent Set is polynomial-time reducible to Vertex Cover in a graph (Reminder: Vertex Cover is a minimum set of vertices where each edge touches at least one of these vertices).
6. (20 points). Design an O(n**2) algorithm to find 3 numbers from an integer array (containing positive and negative integers) of length n so that their sum equals zero.
