### Create a StudySoup account

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

Already have a StudySoup account? Login here

# ALGORITHMIMPLEMENTATION CS1501

Pitt

GPA 3.77

### View Full Document

## 51

## 0

## Popular in Course

###### Class Notes

##### HIST 1200 (History, Steven Watts, Survey of American History Since 1865)

###### Elizabeth Ronecker

verified elite notetaker

###### Class Notes

##### HIST 1200 (History, Steven Watts, Survey of American History Since 1865)

###### Elizabeth Ronecker

verified elite notetaker

## Popular in ComputerScienence

This 80 page Class Notes was uploaded by Jonas Bartell on Monday October 26, 2015. The Class Notes belongs to CS1501 at University of Pittsburgh taught by Staff in Fall. Since its upload, it has received 51 views. For similar materials see /class/229401/cs1501-university-of-pittsburgh in ComputerScienence at University of Pittsburgh.

## Reviews for ALGORITHMIMPLEMENTATION

### 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: 10/26/15

The three principles of algorithm analysis stated for running time7 although they apply to space 1 Measure time as a function of input size 2 lgnore multiplicative constants and lower order terms 3 Look at time as input size goes to in nity The ve relations for comparing run times An and Bn according to these principles are 0 An Bn if and only if limrHOO 22 is greater than 0 and less than 00 o An OBn if and only if limrHOO 27 is less than 00 o Am 0Bn if and only if limnnm 37 is 0 o An if and only if limrHOO is greater than 0 o Am wBn if and only if lim nm 342 is 00 The average running time An of an algorithm A on a particular probability distribution is 2 Probability of I given I E In Running time of A on input I 161 Here In represents the collection of inputs of size n The important point is that the average case case time depends on the input distribution It is quite possible that the average case time for A will be different for different input distributions The expected running time An of a randomized algorithm A max Expected time of A on I 161 Here In represents the collection of inputs of size n The important point is that you are taking the worst case input7 and looking at the expectation over random events internal to the algorithm iH 4m Piem Rattan my 115 it Huichao Xue Department of Computer Science Universities of Pittsburgh Algorithm Implementation Spring 2009 313 Concepts 0 Priority Queue 0 Operations on Priority Queues 0 Heap Algorithms O Initializing 0 Storage 0 Inserting 0 Removing mum 0 Concepts 0 Priority Queue I I itilon g A structure in which elements are processed in order from the largest or from smallest but not necessarily all at once law mm mm b cmtz largest or from smallest but not necessarily all at once This means we don39t have to sort the elements up front so we may be able to do better than ONlog N law 0 Concepts 0 Operations on Priority Queues at 439 Grammar me wge o constructa priority queue from N items 0 inserta new item into the priority queue 0 remove the largest item from the priority queue o changethe priority of an item mum at 439 Grammar memwge o constructa priority queue from N items 0 inserta new item into the priority queue 0 remove the largest item from the priority queue o changethe priority of an item Read chapter 11 in the text We will implement a priority queue as a heap data structure mum 0 Concepts 0 Heap fD ef T Hi o n A full binary tree is one that is filled in at every level from the root to the leaflevel KW fD ef T Hi o n A full binary tree is one that is filled in at every level from the root to the leaflevel KW A full binary tree is one that is filled in at every level from the root to the leaflevel v This tree is full wasp p quotE 39 i t ibh A complete binary tree is full at every level except possibly the last but the nodes at the bottomlevel are filled in with no gaps from left to right quotE 39 i t ibh A complete binary tree is full at every level except possibly the last but the nodes at the bottomlevel are filled in with no gaps from left to right l i A complete binary tree is full at every level except possibly the last but the nodes at the bottomlevel are filled in with no gaps from left to right This tree is not a complete binary tree mm This tree is a complete binary tree A heap is a complete binary tree in which each node has priority greater or equal to each of its children W511 A heap is a complete binary tree in which each node has priority greater or equal to each of its children Assign priority values to the nodes so that every node has priority greater or equal to its children and we get a heap Max Heap mm 9 Algorithms 0 Initializing Initializing a heap PQ PQint max i a new intmax store for the priorities N 0 number of priorities 9 Algorithms 0 Storage An example An example 15 12 20 Here is how it is stored 9 Algorithms 0 Inserting Algorithm Void PQ upheap1nt V aN place N parent place2 V whileparentgt0 ampamp aplace gt a swap aplace aparent place parent parent lt parent place2 An Example Let39s add v 48 to the heap above An Example Let39s add v 48 to the heap above A call to upheap48 is made 0 N is incremented to 11 Let39s add v 48 to the heap above A call to upheap48 is made 0 N is incremented to 11 Q a11 48 so the array now contains 12 31415161718 59 45 3211713712512115 0 N k CO mum An Examplecont 15 12 20 48 An Examplecont 17 48 25 15 12 20 37 An Examplecont 17 45 25 15 12 20 37 9 Algorithms 0 Removing Remove the max item int PQ remove H downHeap l eturn V downheap Void PQ downHeap root ifroot is not a leaf root must have a left child child 2root ifroot has a right child rightChild child l ifarightChild gt achild child rightChild index of larger child ifaroot lt achild swaparoot achild downHeap child FordFulkerson Algorithm A digraph G VE with an integer valued function c capacity function define on its edges is called a capacitated network Two distinguished vertices exist The first vertex s has in degree O is called the source and the second vertex t has out degree O is called the sink The capacity of edge ij is cij20 12 6 A flow in the network is an integer valued function f defined on the edges of G satisfying 0 S fij S cij for every edge ij in E Conservation Condition For every vertex j in V where j is not the source s or the sink t the sum of the flow into j equals the sum of the flow out of 39 A flow that satisfies the conservation condition is called a feasible flow Let f be a feasible flow in a network G The flow of the network denoted by fG is the sum of flows coming out of the source s The Ford Fulkerson algorithm determines the maximum flow of the network Let f be a feasible flow in G Edge ij is said to be a saturated if fij Cij b free if fij O c positive if 0 lt fij lt cij An augmenting path is an alternating sequence of vertices and edges of the form s e1 v1 e2 v2 m ek t in which no vertex is repeated and no forward edge is saturated and no backward edge is free The r idual capacity rc of an edge ij equals cij 7 fij when ij is a forward edge and equals fij when ij is a backward owcap Forward edge c flow Backward edge flowcap flow rc D Q Q D Example Augmenting Path 38 67 26 49 The excess flow capacity of an augmenting path equals the minimum of the residual capacities of each edge in the path We can increase the flow in the path from s to t in the above diagram by determining the excess flow capacity of this path From left to right the residual capacities the amount flow can be increased on the edge are the first number on each edge minimum5 l 2 5 l Theorem A flow in a capacitated network is a maximum flow if and only if there is no augmenting path in the network Augmenting path s gtX gtW gtt Excess capacity of s gtX gtW gtt min4 3 5 3 Augmenting path s gtX gtt Excess capacity of s gtX gtt minl 5 l Augmenting path s gtZ gtY gtt Excess capacity of s gtZ gtY gtt min6 4 4 4 At this point there are no remaining augmenting pathsl Therefore the flow is a maximum 8 K 3 Pmi lbirn tier 2quot gram nn Huichao Xue Department of Computer Science Universities of Pittsburgh Algorithm Implementation Spring 2009 Hiram mmw Outline 0 Basic Concepts 0 Connectivity 0 More definitions about connectivity 3 An example a Detecting articulation nodes 0 Graph Representation 0 DFS with backedges 0 min values 0 Basic Concepts 0 Connectivity Hwy o Void search int Count the number of calls made to visit from the search method described in lecture count 1n1t1allze for k lt fork unseen Vlsltk added step gmmtmmmmmw 0 Basic Concepts 0 More definitions about connectivity A graph is biconnected if and only if there are at least two different paths connecting each pair of vertices mmwm w Definition A graph is biconnected it and only it there are at least two different paths connecting each pair of vertices quotDefinition An articulation point in a connected graph is a vertex that it deleted would breakthe graph into two or more pieces Wowmw 0 Basic Concepts 3 An example What are the articulation points in this graph An example What are the articulation points in this graph An example e Detecting articulation nodes 0 Graph Representation Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG e Detecting articulation nodes 0 DFS with backedges Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D Z ode Neighbor list IQT IH IUOmb BHEHF AHF DHF CHFH AHGHH AHBHCHD EHH EHG D A vertex X is NOT an articulation point it every child y of X has some node lower in the tree connected to a node higher in the tree than X 0 32 is not an articulation point because child F3 connected to A1 in original graph H m wmiw A vertex X is NOT an articulation point it every child y of X has some node lower in the tree connected to a node higher in the tree than X 0 32 is not an articulation point because child F3 connected to A1 in original graph 0 C4 is not an articulation point because child D5 connected to F3 in original graph H m wmiw e Detecting articulation nodes 0 min values values int Vlslt1nt kH DFS adjacency list struct node t int m min Valk ld fort adj k t I z t trgtnextn fva1trgtv unseenH m 1fmltm1n min m r F A and E in this order if mgtval k Systemloutprlntln name k else fValtgtV lt min min Valtgtv return min The articulation points are those vertices whose DFS numbers are less or equal to the min values of ANY of their descendents in the DFS tree o E is an articulation point since its number 7 g minG g minH 7 Hiram Qm mmw 48 m G co m 01 I 7 i F t t C l 1 D Iii I do co 1 The articulation points are those vertices whose DFS numbers are less or equal to the min values of ANY of their descendents in the DFS tree o F is an articulation point since its number 3 g minC minD 3 g minl 5 Hiram Qm mmw The articulation points are Lquot 1 those vertices whose DFS V 39 numbers are less or equal to quotJ 7 the min values of ANY of their descendents in the DFS tree I o D is an articulation point since its number 5 g minl 5 Hiram Qm mmw The articulation points are L yl 1 those vertices whose DFS 7 numbers are less or equal to is 7 the min values of ANY of their descendents in the DFS tree I o A is the root and is an articulation point Because it has branches Hiram Qm mmw

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

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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

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