D1 Critical path analysis 01/11/11

• Precedence/dependence tables
• Drawing network from precedence table
• Early and late event times
• Slack on events
• Float on activities
• Critical activities
• Critical path
• Cascade (Gannt) chart

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpOTJiMzkzYTItODE4MC00OWE3LWIzMTEtNzljZTIzMmQzMDll&hl=en_US

D1 Matchings 18/10/11

• Reminder of bipartite graphs
• Matchings - trivial, maximal, complete
• Alternating paths to improve matchings
• Exam questions involving matchings

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpMWQzNzJhMjQtZDZhYi00OTFkLTlkOWUtMWUxNmM4NDQxZTYz&hl=en_US

D1 Shortest path 11/10/11

• Using Dijkstra's algorithm to find shortest path

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpYTg5ZTY0Y2QtZDAzMC00NjI1LTk4MWUtYzhmNDU1ZWNkMTM3&hl=en_US

D1 Route inspection 04/10/11

• Reminder of traversable (Eulerian) and semi-traversable (semi-Eulerian) graphs
• The route inspection problem
• Examples of using the route inspection problem

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpMzhlZmYxMGEtZWUxNS00N2U0LThhMjItMjBjZjc3OTNmMDNm&hl=en_US

D1 Spanning trees 27/09/11

• Spanning trees
• Minimum spanning trees
• Kruskal's algorithm
• Prim's algorithm
• Using a distance matrix with Prim's algorithm

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpOGIxMjFjOTYtNGE0NS00MDdlLTk3YTItZTI0MmY4NmNiZmQ0&hl=en_US

D1 More graphs 20/09/11

• Digraphs (directed graphs)
• Modelling situations with graphs
• Moving around graphs
• Defining path, cycle, tree
• Traversing graphs - Eulerian & Semi-Eulerian graphs
• Odd/even vertices

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpNDQ1YjQwMWUtMDRlZi00ZjljLWIyZTUtMDhmY2U2ODAzNDY3&hl=en_US

D1 Introduction to graphs 13/09/11

• Defining terms relating to graphs
• - nodes, vertices, arcs, edges, isomorphic, connected, disconnected, complete
• - subgraph, loops, multiple edges, bipartite, complete bipartite, degrees
• Relationship between edges and sum of degrees
• Describing a graph using a vertex set and edge set
• Describing a graph using an adjacency matrix
• Network (weighted graph) and distance matrix

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpMTY4ODQ1MmUtZjlmNi00MjQ2LWIxZDYtZWI2Y2JkMzAwMzk1&hl=en_US

• Homework set - revision of Algorithms (past exam questions)

https://docs.google.com/leaf?id=0B2J1T-insOmpZThkMWU2ZDItNGYyNC00ZWEwLThkYjEtMGY2NjliODc3NjM1&hl=en_US