DOC PREVIEW
MIT 6 006 - QUIZ 2 REVIEW NOTES

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.006 Intro to Algorithms QUIZ 2 REVIEW NOTES - Part 2 April 12, 2011Graph RepresentationThe two main graph representations we use when talking about graph problems are the adjacencylist and the adjacency matrix. It’s important to understand the tradeoffs between the two repre-sentations. Let G = (V, E) be our graph where V is the set of vertices and E is the set of edgeswhere each edge is represented as a tuple of vertices.Adjacency ListAn adjacency list is a list of lists. Each list corresponds to a vertex u and contains a list of edges(u, v) that originate from u. Thus, an adjacency list takes up Θ(V + E) space.Adjacency MatrixAn adjacency matrix is a |V | × |V | matrix of bits where element (i, j) is 1 if and only if the edge(vi, vj) is in E. Thus an adjacency matrix takes up Θ(|V |2) storage (note that the constant factorhere is small since each entry in the matrix is just a bit).ComparisonThe worst case storage of an adjacency list is when the graph is dense, i.e. E = Θ(V2). This givesus the same space complexity as the adjacency matrix representation. The Θ(V + E) space com-plexity for the general case is usually more desirable, however. Furthermore, adjacency lists giveyou the set of adjacent vertices to a given vertex quicker than an adjacency matrix O(neighbors)for the former vs O(V ) for the latter. In the algorithms we’ve seen in class, finding the neighborsof a vertex has been essential.6.006 Intro to Algorithms QUIZ 2 REVIEW NOTES - Part 2 April 12, 2011BFSBFS (breadth first search) is an algorithm to find the shortest paths from a given vertex in anunweighted graph. It takes Θ(V + E) time.DFSDFS (depth first search) is an algorithm that explores an unweighted graph. DFS is useful for manyother algorithms, including finding strongly connected components, topological sort, detectingcycles. DFS does not necessarily find shortest paths. It also runs in Θ(V + E) time.6.006 Intro to Algorithms QUIZ 2 REVIEW NOTES - Part 2 April 12, 2011Edge ClassificationWe classify the edges in the resulting DFS tree as one of the following four types:1. Tree edge - an edge that is traversed during the search.2. Back edge - an edge (u, v) that goes from a node u to an ancestor of it in the DFS tree.3. Forward edge - an edge (u, v) that goes from a node u to a descendant of it in the DFS tree.4. Cross edge - any other edge in the original graph not classified as one of the above threetypes.Selected Past Test Questions6.006 Intro to Algorithms QUIZ 2 REVIEW NOTES - Part 2 April 12, 2011Other Important TopicsWe did not have time to cover all possible topics regarding Graphs/BFS/DFS at the review session.You should also review anything else in the lecture/recitation notes. For example:• Beginning/Finishing times for DFS• Topological sort• BFS queue vs DFS stack• Rubik’s cube graph• Proofs of correctness and runtime• DAG’s• Connected


View Full Document

MIT 6 006 - QUIZ 2 REVIEW NOTES

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download QUIZ 2 REVIEW NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view QUIZ 2 REVIEW NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view QUIZ 2 REVIEW NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?