Difference between pages "7.21" and "Main Page"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
(Created page with "(a) Compare every possible set of three vertices and test if there is an edge between the three. (b) One may be tempted to use DFS to find cycle of length 3, by maintaining a...")
 
 
Line 1: Line 1:
(a) Compare every possible set of three vertices and test if there is an edge between the three.
+
The Wiki is an experiment, a grass-roots effort to create an answer key to aid self-study with Steven Skiena's The Algorithm Design Manual. Students and other readers are encouraged to contribute hints and answers to all odd numbered problems in the book, or expand/improve the solution contributed by others.
  
(b) One may be tempted to use DFS to find cycle of length 3, by maintaining an array parent[I] and check any backedge u-v whether grandparent of u is equal to v. However this is incorrect, consider the graph
+
Please do not use this resource to cheat on your class homework. Recognize that no authority certifies the correctness of these solutions; they could well have been submitted by the idiot who sits in the back row of your class. Also recognize that other students in your class have equal access to these solutions, and it is typically easy for professors to recognize when two students submit the same solution.
  
A - B - C - D - A (square)
+
[[Chapter List]]
  
D - E - F - G - D (another square, connected to the first one through D)
+
== Getting started ==
 
+
* [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Configuration settings list]
A - G (edge that closes the triangle A - D - G).
+
* [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki FAQ]
 
+
* [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce MediaWiki release mailing list]
 
+
* [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Localise MediaWiki for your language]
DFS would produce:  
+
* [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Learn how to combat spam on your wiki]
 
 
A -> B - > C -> D (grandParent of D is B) -> A (nothing to do, back up the recursion to D and move to the next edge) -> E -> F -> G (grandparent of G is E)
 
 
 
At this point we find a cycle when considering the edge G - D, but the grandparent of D isn't connected to G. So we continue and consider A, and then the recursion ends and we process back every node till A, and consider the last edge: A -G. Since A isn't connected to the grandfather of G, we don't find the triangle.
 
 
 
Some possible solutions can be found in : http :// i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_t.pdf
 
 
 
----
 
Alternative solution
 
 
 
<pre>
 
1. O(|V|^3)
 
- If only adjacency lists are available, convert adjacency lists to the adjacency matrix
 
- If an adjacency matrix is available, traverse the matrix O(|V|^2) get a vertex U and an adjacent M, traverse the M row O(|V|) and check the vertices
 
for adjacency with U O(1)
 
 
 
2. O(|V|*|Е|), |V| <= |E|
 
- Data preparation
 
- - Let's analyze the case with the largest upper bound => assume that |V| = |E|
 
- - If an adjacency matrix is available, create additional adjacency lists O(|V|^2)
 
- - If adjacency lists are given, create an additional adjacency matrix O(|V| + |E|) = O(2 * |V|) by assumption ~ O(|V|)
 
- - At this stage, we have adjacency lists and an adjacency matrix, and each element of the adjacency lists also stores its coordinates from the adjacency matrix
 
 
 
- Algorithm
 
- - Traverse adjacency lists O(|V| + |E|) vertex U is the owner of the current list, vertex M is a list item
 
- - - Traversing a list owned by M O(|V|) vertex M is the owner of the list, vertex C is a list item
 
- - - - Checking C for adjacency with U O(1), since the coordinates of the vertices are known => row U and column C are known
 
- - Time complexity O(|V| + |E|) * O(|V|) * O(1) ~ O(|V|) * O(|V|) = O(|V|^2) ~ O(|V| * |E|), by assumption |V| = |E|
 
</pre>
 
--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 10:16, 5 July 2020 (UTC)
 
 
 
 
 
Back to [[Chapter 7]]
 

Revision as of 17:26, 28 September 2020

The Wiki is an experiment, a grass-roots effort to create an answer key to aid self-study with Steven Skiena's The Algorithm Design Manual. Students and other readers are encouraged to contribute hints and answers to all odd numbered problems in the book, or expand/improve the solution contributed by others.

Please do not use this resource to cheat on your class homework. Recognize that no authority certifies the correctness of these solutions; they could well have been submitted by the idiot who sits in the back row of your class. Also recognize that other students in your class have equal access to these solutions, and it is typically easy for professors to recognize when two students submit the same solution.

Chapter List

Getting started