3121/9101 Final Exam Practice Problems
Instructions: Please write the square of a number x as x^2 and write an index
such as ai as a_i. Type your answers in the spaces provided.
1. (a) Write the following complex number in the form a + i b : ω4 (4 pts) (b) Write the following complex number in the form a + i b : ω8 (6 pts)
(c) Compute the convolution of sequences (1, 0, 1) and (−1, 0, −1). (10 pts)
2. You have n items for sale, numbered from 1 to n. Alice is willing to pay a[i] > 0 dollars for item i, and Bob is willing to pay b[i] > 0 dollars for item i. Alice is willing to buy no more than A of your items, and Bob is willing to buy no more than B of your items. Additionally, you must sell each item to either Alice or Bob, but not both, so you may assume that n ≤ A + B. You are given n,A,B,a[1…n] and b[1…n].
(a) Design an algorithm which correctly determines the maximum total amount of money you can earn and which runs in O(n log n) time. (10 pts)
(b) Justify that your algorithm is correct. (10 pts)
(c) Justify that it runs in time O(n log n). (5 pts)
3. You are a photo reporter given an assignment to cover some events in El- bonia. You are given a map of Elbonia which looks like a connected graph with 20 cities c1, c2, . . . , c20 as vertices and with edges connecting some of the cities representing roads. The roads are quite bad and it takes one whole day to traverse any of the roads (i.e., edges of the graph) between any two connected cities. On each day t (1 ≤ t ≤ 30) in each city cj there is an event and you are given the importance value I(t,j) of that event. Your goal is to design an algorithm which determines:
• the largest possible total sum of importances of 30 events that you can cover in 30 days;
• the sequence of the 30 locations you will be at, such that the sum of the importances of the events in those locations at days when you visit them is as large as possible. All of these locations are among cities c1,c2,…,c20; each city can be visited multiple times. Any two consecutive locations must be two cities connected by a direct road between them (thus with an edge in the graph).
You are free to choose the city you will start from on day 1. 1
(a) Formulate precisely the sub problems to be solved. (10 pts)
(b) Formulate precisely the initial values and the recursion equations that the optimal solutions to sub problems have to satisfy. (10 pts)
(c) Formulate precisely how the final solution to the original problem is obtained from the solutions to sub problems, both in regard to obtaining the maximal total importance of the events covered, and in regard to the sequence of cities visited. (5 pts)
4. You are running a Literature class in which students have to write essays. You have 300 students in class and have prepared 300 topics, but you want to let the students choose the topic they will write about. So each student has given you a list of a few topics which they find interesting and would like to write about. You have to design an algorithm which assigns to each student a topic from their list so that every student writes on a different topic. In case this is not possible your algorithm should output a message that the task has no solution.
2