程序代写代做代考 algorithm chain python AVL data structure PowerPoint Presentation

PowerPoint Presentation

Faculty of Information Technology,
Monash University

FIT2004: Algorithms and Data Structures
Week 12: Topological Sort and Design Principles

These slides are prepared by M. A. Cheema and are based on the material developed by Arun Konagurthu and Lloyd Allison.

Announcements/Things to note
Lec 12: Topological sort, design principles and final exam
Complete SETU before it closes (21 June)

The post-semester consultation schedule is the same as the in semester consultation schedule

Any changes to the schedule will be announced on Moodle

Overview
Lec 12: Topological sort, design principles and final exam
Topological Sort
Kahn’s Algorithm
Depth First Search
Design Principles (FIT2004 Summary)
Final Exam etc.
Review of all lecture material

Directed Acyclic Graph (DAG)
Lec 12: Topological sort, design principles and final exam
A Directed Acyclic Graph (DAG) is
Directed
Acylcic – has no cycles
Graph
Which of the two graphs is a DAG?

C

B

E

D

A

C

B

E

D

A
Graph 1
Graph 2

DAG: Examples
Lec 12: Topological sort, design principles and final exam
sub-tasks of a project and which “must finish before”
A  B means task A must finish before task B
so, DAGs useful in project management
relationships between subjects for your degree — “is prerequisite for”
AB means subject A must be completed before enrolling in subject B
people genealogy – “is an ancestor of”
A  B means A is an ancestor of B
power sets and “is a subset of“
A  B means A is a subset of B

C

B

E

D

A

Source: wikipedia

Topological Sort of a DAG
Lec 12: Topological sort, design principles and final exam
Order of vertices in a DAG
A < B if AB. Note that if A  B and BD, we have A < B and B < D which implies that A < D (i.e., transitivity). Some vertices may be incomparable (e.g., B and C are incomparable), i.e. A< B and A < C but we do not know whether C < B or B < C. A topological order is a permutation of the vertices in the original DAG such that for every directed edge uv of the DAG u appears before v in the permutation Example: A, B, C, E, D Topological sort of a DAG of “is prerequisite of” example gives an ordering of the subjects for studying your degree, one at a time, while obeying prerequisite rules. C B E D A Topological Sort of a DAG Lec 12: Topological sort, design principles and final exam A DAG can have many valid topological sorts, e.g., let u and v be two incomparable vertices, u may appear before or after v. Which of these is NOT a valid topological ordering of the DAG A, B, C, E, D A, C, B, E, D A, C, E, B, D A, B, E, C, D How to do topological sort? Kahn’s Algorithm C B E D A Overview Lec 12: Topological sort, design principles and final exam Topological Sort Kahn’s Algorithm Depth First Search Design Principles (FIT2004 Summary) Final Exam etc. Review of all lecture material Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A B Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A B Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A B C Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A B C Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A B C E Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A B C E Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v C B E D A Sorted: A B C E D Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v How can we efficiently track the number of incoming edges? C B E D A Sorted: A B C E D Quiz time! https://flux.qa - RFIBMB Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v How can we efficiently track the number of incoming edges? C B E D A Sorted: A B C E D Order: A B C D E 0 1 1 3 1 Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v How can we efficiently track the number of incoming edges? When we remove A, update it’s children by -1 C B E D A Sorted: A B C E D Order: A B C D E 0 1 1 3 1 Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v How can we efficiently track the number of incoming edges? When we remove A, update it’s children by -1 C B E D A Sorted: A B C E D Order: A B C D E 0 0 1 3 1 Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v How can we efficiently track the number of incoming edges? When we remove A, update it’s children by -1 C B E D A Sorted: A B C E D Order: A B C D E 0 0 0 3 1 Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v How can we efficiently track the number of incoming edges? When we remove A, update it’s children by -1 Complexity of such an approach? C B E D A Sorted: A B C E D Order: A B C D E 0 0 0 3 1 Quiz time! https://flux.qa - RFIBMB Kahn’s Algorithm: High level idea Lec 12: Topological sort, design principles and final exam For each vertex v that does not have ANY incoming edge Add v to sorted Remove the outgoing edges of v Loop occurs V times Finding a vertex with 0 in “order” takes O(V) Adding to sorted is O(1) Removing an outgoing edge costs O(1) (using order) This happens E times over the life of the algorithm So this algorithm would be O(V*V + E) = O(V2) Can we do better? Sorted: A B C E D Order: A B C D E 0 0 0 3 1 Quiz time! https://flux.qa - RFIBMB Kahn’s Algorithm: Detailed pseudocode Lec 12: Topological sort, design principles and final exam Loop occurs V times Pop is O(1), append is O(1) Inner loop runs E times in total Removing an edge is O(1) If is O(1), push is O(1) So this algorithm would be O(V + E) Overview Lec 12: Topological sort, design principles and final exam Topological Sort Kahn’s Algorithm Depth First Search Design Principles (FIT2004 Summary) Final Exam etc. Review of all lecture material Depth First Search (DFS) Lec 12: Topological sort, design principles and final exam Below is the DFS algorithm we saw in week 8 function DFS(v): Mark v as Visited For each adjacent edge (v,u) If u is not visited DFS(u) Assume we call DFS(A), which of the following is NOT a possible order in which vertices are marked visited. A, B, D, C, E A, C, E, D, B A, C, D, E, B A, C, E, B, D C B E D A DFS for Topological Sort Lec 12: Topological sort, design principles and final exam C B E D A Sorted: D B E C A Not accessed: DFS not finished yet: Sorted: Overview Lec 12: Topological sort, design principles and final exam Topological Sort Kahn’s Algorithm Depth First Search Design Principles (FIT2004 Summary) Final Exam etc. Review of all lecture material Design Principles (Summing up FIT2004) Lec 12: Topological sort, design principles and final exam Here are some broad strategies to (try to) solve algorithmic problems: Look out for good invariants to exploit Attempt to balance your work as much as possible Do not repeat work (so, store and re-use!) Use appropriate data structures Try well-known problem solving strategies Sometimes greed is good! These are general guidelines. As always, there are many exceptions Look out for good invariants to exploit Lec 12: Topological sort, design principles and final exam Here are some algorithms we considered in the unit that do precisely this! Binary Search (Refer Week 2 lecture) Sorting (Refer Lectures from Weeks 2 and 3) Shortest Paths and Connectivity Dijkstra’s algorithm (Refer Week 8 Lectures) Floyd-Warshall algorithm (Refer Week 9 lectures) Minimum Spanning Tree Algorithms (Refer Week 10 lectures) Balance your work as much as possible Lec 12: Topological sort, design principles and final exam For problems that allow division of labour (eg. Divide and Conquer) Try to divide work equally as much as possible Merge sort achieves this O(N log N)-time always! Quick sort does not necessarily achieve this – depends on the choice of the pivot (Refer week 3) Good pivots give O(N log N)-time Bad pivots give O(N2)-time Choose Data Structures with care Lec 12: Topological sort, design principles and final exam Certain data representations are more efficient than others for a given problem Priority Queue in Dijkstra’s algorithm (Refer Week 8) Union-Find data structure in Kruskal’s algorithm (refer Week 9) Efficient Search and retrieval data structures of various kinds (Refer Weeks 5,6,7 lectures) Don’t repeat work Lec 12: Topological sort, design principles and final exam Do not compute anything more than once (if there is room to store it for reuse) Underpins Dynamic Programming strategy Edit Distance (Refer Week 4 Lecture) Knapsack Problem (Refer Week 4 Lecture) Try well known problem solving strategies Lec 12: Topological sort, design principles and final exam Divide and Conquer (Refer Weeks 3, 4 lectures) Dynamic Programming (Refer Weeks 4, 8, 9 lectures) Sometimes greed is good Lec 12: Topological sort, design principles and final exam A greedy strategy is to make a “local” choice based on current information Sometimes gives optimal solution, e.g. Dijkstra’s single source shortest paths algorithm (Refer Week 8 Lectures) Minimim Spanning Tree Algorithms – Prim’s and Kruskal’s (Refer Week 10 lectures) minimum spanning tree algorithm. Greedy is sometimes a good heuristic! Sometimes gives a “good” solution to a (combinatorial) problem even if not guaranteed optimal Overview Lec 12: Topological sort, design principles and final exam Topological Sort Kahn’s Algorithm Depth First Search Design Principles (FIT2004 Summary) Final Exam etc. Review of all lecture material Final Exam Lec 12: Topological sort, design principles and final exam Time allowed: 2 hours + 10 minutes reading time Total Marks: 60 Exam is open book If a question asks you to describe an algorithm, you can write your idea in plain English If a question asks you to write pseudocode, you must write your idea in a more structured way (like the ones in lecture slides or even Python code) If a question asks for complexity, it means big-O, the tightest bound and the worst case unless otherwise specified Hurdles: At least 16 out of 40 marks in in-semester assessments (assignment + mid-semester test + lecture/tutorial participation) At least 24 out of 60 marks in the final exam At least 50 marks overall Do not miss final exam even if you fail in-semester hurdle. It affects your WAM Non-Examinable Content Lec 12: Topological sort, design principles and final exam Additional material in lecture notes is NOT examinable In other words, anything NOT covered in lectures, tutorials, labs is NOT EXAMINABLE! Advanced questions in tutorials are NOT examinable Anything marked “not examinable” is not examinable Consultations for Final Exam Lec 12: Topological sort, design principles and final exam Please come to the consultations prepared Do not ask questions like “Can you please explain Dynamic Programming from scratch?”. Don’t try getting hints about the questions on final exam! E.g., Is Kruskal’s algorithm going to be on the exam? Don’t ask how hard the exam is It is, on average, easier than questions in the tutorial It is designed to test your knowledge of the unit It is designed to allow everyone a chance to get some marks, but not allow everyone to get full marks (i.e. a spread of difficulty) Suggestions for preparation Lec 12: Topological sort, design principles and final exam Understand how each algorithm works Practice writing pseudocode for each algorithm Understand its complexity analysis Don’t confuse algorithms: Bellman-Ford vs Floyd-Warshall vs Ford-Fulkerson Despite warning, every semester, students mix up algorithms losing all marks for the question Go over the early material and the week 11/12 material Go over the material which was not covered by assignments Overview Lec 12: Topological sort, design principles and final exam Topological Sort Kahn’s Algorithm Depth First Search Design Principles (FIT2004 Summary) Final Exam etc. Review of all lecture material Lecture 1 Lec 12: Topological sort, design principles and final exam correctness proof complexity recap recurrence relations proof by induction Lecture 2 Lec 12: Topological sort, design principles and final exam intro to space complexity comparison costs stability selection sort analysis insertion sort analysis proof of lower bound for comparison based sorrts count sort stable count sort radix sort recursive complexity (space and time) output sensitive time complexity Lecture 3 Lec 12: Topological sort, design principles and final exam quicksort review partition out of place/in place/stable complexity analysis of quicksort (best/worst/average) kth order stats quickselect quickselect complexity median of medians (not examinable) Lecture 4 Lec 12: Topological sort, design principles and final exam intro to DP Fibonacci coin change unbounded knapsack 0/1 knapsack edit distance constructing optimal solutions (finding coins) backtracking vs decision array Lecture 5 Lec 12: Topological sort, design principles and final exam Hash tables direct addressing hashing/collision Birthday paradox collisions always occur ideal properties of a hash open hashing (chaining) closed hashing linear probing with deletion (lazy) primary clustering quadratic probing secondary clustering double hashing cuckoo hashing BST search insert delete worst case shape avl tree balance factor rebalancing complexity analysis of AVL Lecture 6 Lec 12: Topological sort, design principles and final exam trie construction edge-node labels search nodes being arrays pros and cons properties suffix trie substring search lookup counting occurrences of substring using tree longest repeated susbstring using tree suffix tree suffix array querying SA O(n) space SA longest repeated susbstring Construction of SA prefix doubling Lecture 7 Lec 12: Topological sort, design principles and final exam BWT Last-First property justification of symbol clustering k-mers BWT inversion LF-mapping efficient inversion practice substring search + complexity Lecture 8 Lec 12: Topological sort, design principles and final exam graph recap graph definition represntation (adj matrix, adj list) BFS DFS some applications of BFS and DFS BFS for distances in unit weight dijkstras algorithm updating the heap vs double inserting proof of correctness stoppping early with single target recovering path Lecture 9 Lec 12: Topological sort, design principles and final exam dijkstras with negative weights does not work negative cycles make shortest path meaningless bellman ford correctness unreachable cycles all pairs shortest paths floyd warshall correctness transitive closure Lecture 10 Lec 12: Topological sort, design principles and final exam spanning tree minimum spanning tree general strategy of adding safe edges prims algorithm correctness kruskals algorithm correctness union find Lecture 11 Lec 12: Topological sort, design principles and final exam Flow problem Flow network properties For Fulkerson algorithm Augmenting paths Complexity analysis Cuts Max-Flow / Min-Cut Proof of correctness Lecture 12 Lec 12: Topological sort, design principles and final exam Kahn’s algorithm Complexity DFS for topological sort Summary of unit Overview of exam Review of all lecture material Coming Up Next Lec 12: Topological sort, design principles and final exam SWOT VAC