### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CSCI 212 with Professor Choi at GW (3)

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 4 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 17 views.

## Popular in Subject

## Reviews for Class Note for CSCI 212 with Professor Choi at GW (3)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/07/15

George Washington University Department of Computer Science Csci 212 Lecture Notes 2242009 Fractional Knapsack Problem Given A knapsack with capacity M and a list of n elements each with W 101102 wn and a pro t P p1p2 pn Problem Compute X m1z2zn such that 0 g x g 1 where 2 ziwi M and 221 up is maximixed Claim Without loss of generality assume that W and P are sorted in decreasing order by pro t per unit weight of each element In other words the given sets are sorted such that V 7 2 5722 2 2 57 The optimal solution is found when all z 1 for 1 g i lt j zj M7 221 mi and all other xi 0 for j lt i g n In other words we add elements to the solution set in order by pro t per unit weight until we reach M or we use up all elements in the intput set In this solution there is at most one partial element in the solution set All others are either full elements 1 or are not part of the solution 0 Note that from this de nition if there is a partial element ie zj gt 0 then we know that PX M Proof Let X z1m2 mn be a greedy solution Let Y y1y2 yn where the total pro t of Y PY is greater than the total pro t of X PX For analysis we will consider two indicies k and j Let k be the smallest index 1 g k g n such that zk 7 yk Let j be the smallest index such that zj lt 1 From these de nitions of k and j we can say that zk gt yk This can be demonstrated by considering all possible cases for k and j First we assume k gt j More speci cally this means that there is an element zj lt 1 before there is an element zk 7 yk Recall from the de nition ofj that all M before zj must have a value of 1 Also note that after mi all z 0 from the de nition of our greedy solution Thus if zk 7 yk then 0 lt yk 1 However from the de nition of our greedy solution we know that at 7 PX M Since z y for all 1 lt i lt k and M PX Zg1 m we know that M Zg1 yi Thus yk cannot be greater than 0 because that would cause PY to be greater than M making Y an invalid solution Because of this contradiction we have shown that y must be greater than 0 and that it cannot be greater than 0 the case where k gt j cannot occur Next we assume that k lt j This would imply that at zk and yk 1 zk gt 30 This is a valid solution and it supports the argument that zk gt yk Finally we assume that k j This would imply that for all i such that 1 g i lt k 1 xi yi By our de nition of the greedy solution we know that zk zj M 7 2211 m If yk gt zk then yk yj gt M 7 2711yi which would imply that M lt 271 yi Since this is not valid we look at the case where zk yk This would imply that X Y This is because if all M yi in the range 1 g i g j and PX M then all other yi must be 0 otherwise PY gt M making Y and invalid solution Thus we have proven that zk gt yk Now that we have proven that zk gt yk we de ne a new solution Z obtained from Y and de ned such that 2l yi for all i from 1 g i lt k and 2k zk In order for Z to still be avalid so lution the sum of all other 2139 cannot be more than M Thus zkAykwk ELHI A We will now show that Z is at least as good as Y and that Z is closer to X than Y is Let PZ and PY denote the total value of solutions Z and Y respectively PZ PO 311 pm A 1924 Pklt2k A 2419 22 y A 2 Pklt2k A yk ELM 194 i w Ek1 29139 900w E 7k1 59139 900W 5 ELM M 900w H W H 6 w AAA N w l QC w Therefore PZ A PY 2 pkzk A yk A pkzk A zk O This implies that if Y is not optimal we can improve on Y with Z Furthermore if we now treat Z as Y and de ne a new Z in the same was as we de ned Z initially we can improve further on the solution This process can be repeated until Z X Thus our greedy solution X is an optimal solution to the fractional knapsack problem 01 Knapsack Problem Given A knapsack with capacity M and a list of n elements each with W 101102 wn and a pro t P p1p2 pn Problem Compute X 1 2 mn such that M 0 or M 1 where 221 ziwi M and 21 xipi is maximixed Claim The general 01 Knapsack Problem cannot be solved by the greedy solution de ned in the Fractional Knapsack Problem modi ed to ignore the partial element This can be shown easily by example Note however that in the speci c case where wl wg wn and pl 2 pg 2 2 pm the greedy solution is also the optimal solution Proof We will only show that the greedy solution de ned for the Fractional Knapsack Problem is not a general solution for the 01 Knapsack Problem Proof of the special case for the 01 Knapsack Problem is an exercise for the student Let W 0605 03 02 P 221 1 and M 2 Let V be the pro t per unit weight In this case V 062052 031021 12100301 In applying our greedy algorithm modi ed such that there is no partial element the solution set would be simply X 1 0 00 because adding the second element would put PX over M However the optimal solution for this problem is X 10 1 1 Thus the greedy algorithm will not always nd the optimal solution Optimal Merge Pattern Given n les of of sizes S 317 32 7 5 sorted in increasing order Each element is storing some elements7 all sorted in increasing order Problem Find the optimal merge pattern ie7 nd an order in which to merge the les into one large sorted list such that the total time is minimized Solution Remove the two smallest elements 51 and 32 and merge them The result is 3a lnsert 5a back into S while preserving the order of S Repeat the process until 5 1 ie7 repeat until all les are merged into one le This algorithm runs in On log n time Proof The proof for this algorithm is left as an exercise for the students Huffman Code Pre x Code A pre x code is a code in which no two elements contain the same pre x For example7 the code 01 007017100710107101711 is a pre x code7 while the code 62 107 017 0110 is not because the second element contains the same pre x as the third Problem Design a pre x code such that the average code length is minimized Proof The proof for this problem is the same as the proof for the Optimal Merge Pattern Again7 it is left to the student to solve Minimum Spanning Tree Given An arbitrary graph CV7 E7 where V is the set of verticies in the graph7 E is the set of all edges in the graph7 and with weights we assigned to each edge e in E Problem Find a spanning tree T of G such that 286E we is minimized Notes The following are term and notational de nitions that will be used in the discussion of algorithms for solving this problem The size of a graph G is the number of verticies in the graph ie7 n EG is the set of all edges in G VG is the set of all verticies in G A simple graph is one in which there is at most one edge between two nodes7 and there is no self loop A connected graph is one in which there is a path from each node to each other node and a fully connected graph is one in which every node shares an edge with every other node A tree is a connected graph without any cycles A Minimum Spanning Tree MST is a subgraph g of G such that g is a tree that includes all nodes in G ie7 Vg VG7 and the sum of the weights of its edges are minimized Given a simple connected graph G7 n 7 1 EG nn 7 12 Solution 1 Prim7s Algorithm Prim s algorithm nds the MST of a graph G in 0n2 time For simplicity assume you have two sets of verticies V0 and V 7 V0 Let V0 be the verticies in the MST at any given iterationi and initially be empty Start by removing an arbitrary element from VG and placeing it in V0 We then nd the node in V 7 V0 that is connected to V0 whose weight is the minimum if there is a tie choose arbitrarily We then remove this node from V 7 V0 and place it in V0 We then repeat the process of nding the minimal edge connecting V0 to V 7 V0 and placing the end node in V0 until all nodes are in V0 The result will be an MST of G The algorithm as described is actually 0n3 because the list of edges can be 0n2 and we must iterate 0n times over them x 0n2 0n3 This can be solved by using a small optimization that reduces the number of edges to be searched down to Instead of keeping track of all edges leaving V0 we only need to keep track of the minimum edge to any vertex in V7 V0 In other words for each node in V7 V0 we only keep track of the minimum edge connecting it to V0 Thus there are at most 71 7 1 0n edges to inspect on any given iteration to inspect not 7 0n2 edges Solution 2 Kruskal7s Algorithm We can use Kruskal s algorithm to nd the MST of a graph G in log time Let V n and m Let w51 w52 wem We start by letting the MST g of G be composed of only VG but no edges We then iterate through each edge e from 1 g i g m If 5 does not create a cycle we add it to 9 Otherwise we ignore it Clearly this means that Kruskal s algorithm runs in Ocycle time Using the Union Find operations we can determine if there is a cycle in Olog n time Thus using the Union Find functions we can generate the MST of a graph in log n log time

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.