### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 618 Class Note for CSE 565 at PSU

### View Full Document

## 29

## 0

## Popular in Course

## Popular in Department

This 15 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 29 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 618 Class Note for CSE 565 at PSU

### 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/06/15

Algerithm Design and Analysis LECTURE 6 Topological ordering Greedy Algorithms Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 952008 Read on your own Graph bipartiteness DF S implementation 0 Homework notation loga l log DY smallest integer 2 1 ceiling Useful property 1 g lt 1 1 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne 952008 Last lecture BFS Recall Digraph G is strongly connected if for every pair of vertices smt and smt Question Give an algorithm for determining if a graph is connected What is the running time 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Strong Connectivity Algorithm Lemma 6 is strongly connected if and only if for any node 5 every other node t has paths to and from 3 Theorem Can determine if G is strongly connected in Om n time Pf Pick any node s I Run from 5 in reverse orientation ofevery edge in G Run BFS from s in Grevf Return true iff all nodes reached in both BFS executions Correctness follows immediately from the previous lemma strongly connected not strongly connected Direc red Acyclic Graphs Def An DAG is a direcTed graph Tha r contains no direcTed cycles Ex Precedence consTrain rs edge vi VJ means vi musT precede VJ Def A Topological order of a direcTed graph G V E is an ordering of HS nodes as v1 v2 vn so That for every edge vi VJ we have i lt j a DAG a topological ordering Precedence Cons rr39ain rs Precedence consTr39ain rs Edge vi VJ means Task vi musT occur39 before VJ Applications Cour39se pr39er39equisi re gr39aph cour39se vi musT be Taken befor39e VJ Compila rion module vi musT be compiled befor39e VJ Pipeline of compu ring jobs ou rpu r of job vi needed To determine inpu r of job VJ Dir39ecTed Acyclic Gr39aphs Lemma If G has a Topological or39der39 Then G is a DAG Pf by conTr39adicTion Suppose ThaT G has a Topological or39der39 v1 vn and ThaT 6 also has a dir39ecTed cycle C LeT39s see whaT happens LeT vi be The lowesTindexed node in C and leT VJ be The node jusT befor39e vi Thus VJ vi is an edge By our39 choice of i we have i lt j On The oTher39 hand since VJ vi is an edge and v1 vn is a Topological order39 we musT have j lt i a conTr39adicTion the directed cycle C 000000 the supposed topological order v1 vn Direc red Acyclic Graphs Lemma If G has a Topological order Then G is a DAG Q Does every DAG have a Topological ordering Q If so how do we compu re one Dir ec red Acyclic Gr39aphs Lemma If G is a DAG Then G has a node wi rh no incoming edges Pf by con rr39adicfion Suppose That 6 is a DAG and every node has at leasT one incoming edge Let39s see what happens Pick any node v and begin following edges backwar39d from v Since v has at leasT one incoming edge u v we can walk backwar39d To u Then since u has at leasT one incoming edge x u we can walk backwar39d To x Repea r until we visi r a node say w Twice Let C denoTe The sequence of nodes encoun rer39ed between successive visi rs To w C is a cycle Topological Sor39Ting AlgoriThm Running Time Theorem Algor39iThm finds a Topological order in Om n Time Pf MainTain The following infor39maTion 7 count w 2 remaining number39 of incoming edges S seT of remaining nodes wiTh no incoming edges IniTializaTion Om n via single scan Thr39ough gr39aph UpdaTe To deleTe v r39emove v from S decr39emenT count w for39 all edges from v To w and add w To 5 if c count w l ll l39S 0 This is 01 per39 edge AlTer39naTive algor39iThm ModificaTion of DFS exercise Design technique 1 Greedy Algorithms A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Greedy Algorithms Build up a solution to an optimization problem at each step shortsightedly choosing the option that currently seems the best Sometimes good Often does not work 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Job j starts at sj and nishes at Two jobs are compatible if they do not overlap Find maximum subset of mutually compatible jobs 31 1 d 023gg9ho me 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Possible Greedy Strategies Consider jobs in some natural order Take next job if it is compatible with the ones already taken Earliest start time ascending order of sj Earliest nish time ascending order of Shortest interval ascending order of fj sj Fewest con icts For each job j count the number of con icting jobs cj Schedule in ascending order of c J 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Greedy Counterexamples for39 earlies r starT Time for shortest interval for fewest conflicts 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne

### 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

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.