MIT 6 006  QUIZ 2 REVIEW NOTES (4 pages)
Previewing page 1 of 4 page document View the full content.QUIZ 2 REVIEW NOTES
Previewing page 1 of actual document.
View the full content.View Full Document
QUIZ 2 REVIEW NOTES
0 0 61 views
Other
 Pages:
 4
 School:
 Massachusetts Institute of Technology
 Course:
 6 006  Introduction to Algorithms
Introduction to Algorithms Documents

3 pages

22 pages

36 pages

SpeedUp Techniques for ShortestPath Computations
14 pages

21 pages

21 pages

15 pages

6 pages

16 pages

7 pages

5 pages

22 pages

3 pages

2 pages

24 pages

16 pages

19 pages

4 pages

13 pages

Text Justification, Knapsack, Pseudopolynomial Time
6 pages

18 pages

8 pages

13 pages

10 pages

52 pages

Linear Bounds LinearTime Sorting
5 pages

7 pages

3 pages

5 pages

4 pages

24 pages

27 pages

60 pages

3 pages

4 pages

6 pages

6 pages

3 pages

17 pages

5 pages

27 pages

17 pages

28 pages

64 pages

7 pages

18 pages

Scheduling and Binary Search Trees
6 pages

16 pages

4 pages

7 pages

6 pages

17 pages

12 pages

6 pages

5 pages

6 pages

48 pages

5 pages

9 pages

3 pages

5 pages

4 pages

23 pages

2 pages

2 pages

4 pages

7 pages

5 pages

10 pages

5 pages

19 pages

15 pages

3 pages

4 pages

6 pages

9 pages

16 pages

BreadthFirst Search and DepthFirst Search
6 pages

Graph Search and Representations
9 pages

7 pages

3 pages

Lecture 6: Hashing II: Table Doubling, Rolling Hash, KarpRabin
7 pages

11 pages

14 pages

7 pages

4 pages

3 pages

43 pages

54 pages

9 pages

4 pages

6 pages

12 pages

4 pages

27 pages

41 pages

3 pages

13 pages

23 pages

6 pages

6 pages

26 pages

2 pages

37 pages

3 pages

4 pages

6 pages

18 pages

15 pages

27 pages

22 pages

48 pages

3 pages

4 pages

Hashing I  Chaining, Hash Functions
7 pages

3 pages
Sign up for free to view:
 This document and 3 million+ documents and flashcards
 High quality study guides, lecture notes, practice exams
 Course Packets handpicked by editors offering a comprehensive review of your courses
 Better Grades Guaranteed
Unformatted text preview:
6 006 Intro to Algorithms QUIZ 2 REVIEW NOTES Part 2 April 12 2011 Graph Representation The two main graph representations we use when talking about graph problems are the adjacency list and the adjacency matrix It s important to understand the tradeoffs between the two representations Let G V E be our graph where V is the set of vertices and E is the set of edges where each edge is represented as a tuple of vertices Adjacency List An 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 Matrix An 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 factor here is small since each entry in the matrix is just a bit Comparison The worst case storage of an adjacency list is when the graph is dense i e E V 2 This gives us the same space complexity as the adjacency matrix representation The V E space complexity for the general case is usually more desirable however Furthermore adjacency lists give you 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 neighbors of a vertex has been essential 6 006 Intro to Algorithms QUIZ 2 REVIEW NOTES Part 2 April 12 2011 BFS BFS breadth first search is an algorithm to find the shortest paths from a given vertex in an unweighted graph It takes V E time DFS DFS depth first search is an algorithm that explores an unweighted graph DFS is useful for many other algorithms including finding strongly connected components topological sort detecting cycles 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 2011 Edge Classification We classify the edges in the resulting DFS tree as one of the following
View Full Document