(5/5)

I need a very experienced and professional tutor fully aware of the Computer Science courses of University of Victoria (BC) /Canada. please send me your contact and email, so i can send you the assignment for CSC425 Course (Algorithm Analysis) and its resources and the supportive documents.

CSC 425/520 FALL 2021

ANALYSIS OF ALGORITHMS

ASSIGNMENT 4

UNIVERSITY OF VICTORIA

1. Prove Graham’s Theorem stated in Slide 16 of lecture slides (Chapter 11). It states that

the LPT rule is a 4/3 approximation algorithm. For this problem, you are allowed to

read the proof of this result from online sources but you have to understand and write the

solution in your own words.

2. Suppose you are given a set of positive integers A = {a1, a2, . . . , an} and a positive integer

B. A subset S ⊆ A is called feasible if the sum of the numbers in S does not exceed

B. The sum of the numbers in S will be called the total sum of S . You would like to

select a feasible subset S of A whose total sum is as large as possible. Give a polynomialtime approximation algorithm for this problem with the following guarantee: It returns a

feasible set S ⊆ A whose total sum is at least half as large as the maximum total sum of

any feasible set S ⊆ A. Your algorithm should have a running time of at most O(n log n).

3. Consider the following maximization version of the 3-Dimensional Matching Problem.

Given disjoint sets X, Y , and Z, and given a set T ⊆ X × Y × Z of ordered triples, a

subset M ⊆ T is a 3-dimensional matching if each element of X ∪ Y ∪ Z is contained in

at most one of these triples. The Maximum 3-Dimensional Matching Problem is to find

a 3-dimensional matching M of maximum size. (The size of the matching, as usual, is

the number of triples it contains. You may assume |X| = |Y | = |Z| if you want.) Give

a polynomial-time algorithm that finds a 3-dimensional matching of size at least 1

3

times

the maximum possible size.

4. Model the (unweighted) set cover problem (U, {S1, S2, . . . , Sm}) as an ILP. Show how

you can round the fractional solution obtained by solving its LP relaxation to get a fapproximation algorithm where f is the maximum number of sets in which any element

of u ∈ U appears.

1

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

Get Free Quote!

334 Experts Online