CIS 1210 Midterm 2 Flashcards
39 Questions
100 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the runtime of DFS?

  • O(log n)
  • O(n^2)
  • O(n)
  • O(n+m) (correct)

    • What is the runtime of BFS?

  • O(n+m) (correct)
  • O(n)
  • O(log n)
  • O(n^2)

    • What method do you use to check for a removable vertex?

    DFS

    What method do you use to check if a graph is bipartite?

    <p>BFS</p> Signup and view all the answers

    What function checks if a path exists?

    <p>HasPath</p> Signup and view all the answers

    How do you find the shortest cycle in a graph?

    <p>BFS from every vertex and check last edge</p> Signup and view all the answers

    What method do you use to count connected components?

    <p>BFS</p> Signup and view all the answers

    What method do you use to find the longest connected component?

    <p>BFS</p> Signup and view all the answers

    What method do you use to find the shortest path in an unweighted graph?

    <p>BFS</p> Signup and view all the answers

    What is the Topological Sort method known as 'Magic'?

    <p>Tarjan's Topo Reverse DFS</p> Signup and view all the answers

    What is the runtime of Tarjan's Topo Algorithm?

    <p>O(n+m)</p> Signup and view all the answers

    What is Kahn's Algorithm used for in Topological Sort?

    <p>Kahn's with indegree 0</p> Signup and view all the answers

    What is the runtime of Kahn's Topo Algorithm?

    <p>O(n+m)</p> Signup and view all the answers

    What is used to check for time consistency in a graph?

    <p>DFS</p> Signup and view all the answers

    What is the method to find all Strongly Connected Components?

    <p>Kosaraju's Inversion</p> Signup and view all the answers

    What is the runtime of Kosaraju's Algorithm?

    <p>O(n+m)</p> Signup and view all the answers

    How do you find a mother vertex using indegree 0?

    <p>Kosaraju's Inversion</p> Signup and view all the answers

    What algorithm is used for finding the shortest path with weights?

    <p>Dijkstra's Algorithm</p> Signup and view all the answers

    What is the runtime of Dijkstra's Algorithm?

    <p>O((V+E)lgV)</p> Signup and view all the answers

    What is the runtime of Dijkstra's Algorithm if the graph is connected?

    <p>O(ElgV)</p> Signup and view all the answers

    How can you prove Dijkstra's algorithm?

    <p>Induction on the size of S that the path Pu is the shortest path for all u in S</p> Signup and view all the answers

    What is the runtime for extracting min once per vertex in Dijkstra's Runtime?

    <p>O(lgV)</p> Signup and view all the answers

    What is the runtime for building the heap in Dijkstra's algorithm?

    <p>O(V)</p> Signup and view all the answers

    What is the runtime for decreasing the key E times in Dijkstra's algorithm?

    <p>O(lgV)</p> Signup and view all the answers

    What method do you use to find the shortest path in a directed acyclic graph (DAG)?

    <p>Toposort</p> Signup and view all the answers

    What is the method for finding the longest path in a DAG?

    <p>Shortest path * -1</p> Signup and view all the answers

    What algorithm is similar to Dijkstra's for Minimum Spanning Tree?

    <p>Prim's MSTs</p> Signup and view all the answers

    What is the runtime of Prim's MST algorithm?

    <p>O(mlgn)</p> Signup and view all the answers

    What method is used for Minimum Spanning Tree by adding edges with Union-Find?

    <p>Kruskal's MSTs</p> Signup and view all the answers

    What is the runtime of Kruskal's MST algorithm?

    <p>O(mlgn)</p> Signup and view all the answers

    What method is used for Minimum Spanning Tree by removing edges?

    <p>Reverse-Delete MSTs</p> Signup and view all the answers

    What is the runtime of Reverse-Delete MSTs algorithm?

    <p>O(m^2)</p> Signup and view all the answers

    What principle is used to prove Kruskal's algorithm?

    <p>Cut Property</p> Signup and view all the answers

    What principle is used to prove Prim's algorithm?

    <p>Cut Property</p> Signup and view all the answers

    What principle is used to prove Reverse-Delete algorithm?

    <p>Cycle Property</p> Signup and view all the answers

    How many nodes does the root of rank k have?

    <p>At least 2^k nodes</p> Signup and view all the answers

    How many nodes are there at most of rank k?

    <p>n/2^k</p> Signup and view all the answers

    What is the runtime for Huffman's algorithm?

    <p>O(nlgn)</p> Signup and view all the answers

    What is the runtime for Binary Heap Insert?

    <p>O(lgn)</p> Signup and view all the answers

    Study Notes

    Graph Algorithms Runtime Complexity

    • Depth-First Search (DFS) runtime is O(n + m), where n is the number of vertices and m is the number of edges.
    • Breadth-First Search (BFS) runtime is also O(n + m).

    Graph Characteristics and Checks

    • Removal of a vertex can be checked using DFS.
    • To determine if a graph is bipartite, BFS is utilized.

    Path and Cycle Determination

    • The existence of a path can be verified using the HasPath function.
    • The shortest cycle can be found by performing BFS from every vertex and checking the last edge.
    • BFS is also used to count connected components and identify the longest connected component.
    • BFS is optimal for finding the shortest path in unweighted graphs.

    Topological Sorting Methods

    • Tarjan's Algorithm provides a topological sort using a reverse DFS method.
    • Kahn's Algorithm for topological sorting operates on vertices with an indegree of zero.

    Algorithm Runtimes

    • Both Tarjan's and Kahn's topological sort algorithms run in O(n + m).
    • Dijkstra's Algorithm, used for finding the shortest path in weighted graphs, runs in O((V + E) log V) if the graph is connected, with V as vertices and E as edges.

    Dijkstra's Specifics

    • Proving Dijkstra's efficiency involves induction on the size of the path.
    • Extracting the minimum once per vertex in Dijkstra's results in a time complexity of O(log V).
    • Building the heap during Dijkstra's Algorithm takes O(V).
    • Decreasing a key value E times in Dijkstra's runs in O(log V).

    Directed Acyclic Graphs (DAG)

    • To find the shortest path in a DAG, a topological sort is performed.
    • The longest path in a DAG is computed as the shortest path multiplied by -1.

    Minimum Spanning Tree (MST) Algorithms

    • Prim's Algorithm, similar to Dijkstra's, has a runtime of O(m log n).
    • Kruskal's MST algorithm, focused on adding edges, also runs in O(m log n).
    • Reverse-Delete MST, which removes edges, operates with a runtime of O(m²).

    Proving MST Algorithms

    • Kruskal's and Prim's algorithms are proven using the Cut Property.
    • The Reverse-Delete algorithm is demonstrated through the Cycle Property.

    Union-Find Structures

    • A root of rank k has at least 2^k nodes.
    • There are at most n / 2^k nodes of rank k in a union-find structure.

    Other Key Algorithms

    • Huffman's Algorithm has a runtime of O(n log n) for constructing optimal prefix codes.
    • Inserting into a binary heap has a runtime of O(log n).

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Description

    Test your knowledge with flashcards from CIS 1210 Midterm 2. This quiz covers various algorithms and their runtimes, such as DFS and BFS, as well as properties of graphs. Perfect for preparing for your midterm exam in computer science.

    More Like This

    BFS vs DFS
    8 questions

    BFS Quiz: Compare BFS vs DFS Algorithms

    ChivalrousSmokyQuartz avatar
    ChivalrousSmokyQuartz
    Algorithm Selection: DFS vs BFS
    12 questions

    Algorithm Selection: DFS vs BFS

    NoiselessCharacterization4759 avatar
    NoiselessCharacterization4759
    Graph Theory and DFS Algorithm Quiz
    50 questions

    Graph Theory and DFS Algorithm Quiz

    EliteCarnelian3565 avatar
    EliteCarnelian3565
    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser