Algorithms

CSUDH Computer Science Department CSC401: Analysis of Algorithms CSC501: Algorithm Design and Analysis

Final Examination (open book) Name: All questions are equally credited. 1. Dynamic programming: Warshall’s algorithm uses dynamic programming technique to compute the transitive closure of a directed graph based on the adjacency matrix. However, Warshall’s algorithm uses many intermediate matrices which are not necessary. Explain how to implement Warshall’s algorithm without using extra memory for storing elements of the algorithm’s intermediate matrices. And then rewrite your modified algorithm (pseudo-code).

CSC401/501 Final Examination 1 2. Greedy technique: Consider the single machine scheduling problem where we are given a set of T of tasks specified by their start time and end times. We wish to maximize the number of tasks that this single machine performs. Design a greedy algorithm for this single machine scheduling problem and analyze the running time of your algorithm. Suppose you are given a set of tasks specified by pairs of the start times and finish times as T={(1,4), (1,3), (1,2), (2,4), (3,7), (4,8), (5,6), (6,8), (7,9)}. Solve the task scheduling problem for this set of tasks using your greedy algorithm.

CSC401/501 Final Examination 2 3. Iterative improvement: Consider a network that is a rooted tree, with the root as its source, the leaves as its sinks, and all the edges directed along the paths from the root to the leaves. Design an efficient algorithm for finding a maximum flow in such a network. Analyze the time efficiency of your algorithm?

CSC401/501 Final Examination 4. Limitations of Algorithm Power: 1) What is the tight lower bound of a problem? 2) What are the CIRCUIT-SAT problem and the VERTEX-COVER problem? 3) True or False: A P problem is one that can be solved in polynomial time, while a NP problem is one that can not be solved in polynomial time. 4) Describe the process of showing that a problem is NP-Complete.

3

CSC401/501 Final Examination 4 5. Branch and Bound: Assignment problem is to assign n people to n jobs so that the total cost of the assignment is as small as possible. 1) Give an example of the best-case input for the branch-and-bound algorithm for the assignment problem. 2) In the best-case, how many nodes will be in the state-space tree of the branchand-bound algorithm for the assignment problem. 3) Explain what the best-first branch-and-bound strategy is. 4) Solve the following instance of the assignment problem by the best-first branch-and-bound algorithm with the bounding function based on matrix columns rather than rows (Note: The textbook solves the problem with the bounding function based on matrix rows).

CSC401/501 Final Examination 5 6. (CSC501 only) NP-Complete problem: A SUBSET-SUM problem is defined as: Given a set of integers and a distinguished integer K, is there a subset of the integers that sums to K? A PARTITION problem is defined as: Given a set S = {s1, s2, ... , sn} of numbers and asks if there is a subset T of S such that Σt∈Tt = Σs∈S-Ts . That is, it asks if there is a partition of the numbers into two groups that sum to the same value. Given that the SUBSET-SUM problem is NP-Complete, show that the PARTITION problem is NP-complete.