TADM2E 3.11 - Revision history

Mytreya: Undo revision 702 by Mytreya (talk)

2019-09-27T10:05:23Z

Undo revision 702 by Mytreya (talk)

Mytreya: Undo revision 703 by Mytreya (talk)

2019-09-27T10:04:50Z

Undo revision 703 by Mytreya (talk)

Mytreya at 09:48, 27 September 2019

2019-09-27T09:48:05Z

Mytreya: /* 2. Design a data structure that uses O(n) space and answers queries in O(\log n) time. */

2019-09-27T09:46:24Z

‎2. Design a data structure that uses O(n) space and answers queries in O(\log n) time.

Supermatthew at 00:22, 18 May 2019

2019-05-18T00:22:50Z

Supermatthew: /* 2. Design a data structure that uses O(n) space and answers queries in O(\log n) time. */

2019-05-17T19:44:59Z

‎2. Design a data structure that uses O(n) space and answers queries in O(\log n) time.

Ajitq at 12:20, 3 May 2018

2018-05-03T12:20:40Z

Benw at 23:08, 7 January 2015

2015-01-07T23:08:20Z

Benw at 22:53, 7 January 2015

2015-01-07T22:53:15Z

Algowikiadmin: Recovering wiki

2014-09-11T18:13:22Z

Recovering wiki

New page

# Use an nxn matrix populated with the distance between the nodes at the two indices.
# Solution two choice 2:
#* http://en.wikipedia.org/wiki/Cartesian_tree[http://en.wikipedia.org/wiki/Cartesian_tree]
#* http://en.wikipedia.org/wiki/Treap[http://en.wikipedia.org/wiki/Treap]

← Older revision		Revision as of 10:05, 27 September 2019
Line 45:		Line 45:

	--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)		--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)
−
−	'''Question:''' Why not use a sorted array? The queries can be executed with O(1) processing on O(n) space. The question does not require anything other than O(logn) query time and O(n) space. i.e., no requirements on insert and delete or any such other operations. <math>x_i</math> is always going to be the answer for any (i,j) because we have them sorted :-) And O(1) is definitely O(logn)

← Older revision		Revision as of 10:04, 27 September 2019
Line 45:		Line 45:

	--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)		--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)
		+
		+	'''Question:''' Why not use a sorted array? The queries can be executed with O(1) processing on O(n) space. The question does not require anything other than O(logn) query time and O(n) space. i.e., no requirements on insert and delete or any such other operations. <math>x_i</math> is always going to be the answer for any (i,j) because we have them sorted :-) And O(1) is definitely O(logn)

← Older revision		Revision as of 09:48, 27 September 2019
Line 45:		Line 45:

	--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)		--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)
−
−	'''Question:''' Why not use a sorted array? The queries can be executed with O(1) processing on O(n) space. The question does not require anything other than O(logn) query time and O(n) space. i.e., no requirements on insert and delete or any such other operations. <math>x_i</math> is always going to be the answer for any (i,j) because we have them sorted :-) And O(1) is definitely O(logn)

← Older revision		Revision as of 09:46, 27 September 2019
Line 45:		Line 45:

	--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)		--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)
		+
		+	'''Question:''' Why not use a sorted array? The queries can be executed with O(1) processing on O(n) space. The question does not require anything other than O(logn) query time and O(n) space. i.e., no requirements on insert and delete or any such other operations. <math>x_i</math> is always going to be the answer for any (i,j) because we have them sorted :-) And O(1) is definitely O(logn)

@@ Line 22: / Line 22: @@
 For example, say we have elements indexed 0 to 15, and we are interested in querying the minimum of elements 1 to 14, inclusive.
 Then following the above procedure will require visiting nodes [1], [2,3], [4,7], [8,11], [12,13] and [14], a total of <math>O(\log n)</math> nodes (since there are at most 2 queried nodes per level of the tree), but requiring a distance of 8 to traverse.
-Indeed, for any <math>n=2^k - 1</math> and query <math>[1,2^k-2]</math>, <math>O(\log n)</math> nodes will be visited, with <math>O(n)</math> traversal time.
+Indeed, for any <math>n=2^k - 1</math> and query <math>[1,2^k-2]</math>, <math>O(\log n)</math> nodes will be visited, with <math>O(n)</math> traversal time. See below for a true <math>O(\log n)</math> algorithm (basically the above algorithm branches down the tree from the root in multiple directions, while the below algorithm begins at a leaf and takes a single path up and then down the tree).
 '''
@@ Line 41: / Line 41: @@
 If the range is 3-14, for example, the build-up would be 3; 4-7; 8-11; 12-13, and 14. This is O(log n).
 The minimum of the values of these ranges gives us the desired answer. To calculate the minimum of m unsorted values is O(m), and since m is O(log n), the minimum calculation is also O(log n).
 --[[User:Ajitq|Ajitq]] ([[User talk:Ajitq|talk]]) 12:20, 3 May 2018 (UTC)

@@ Line 16: / Line 16: @@
 * Otherwise return the lowest of the results from calling the query function on the left child and the right child.
 The query function will visit at most two leaf nodes, and runs in <math>O(\log n)</math> time.
 --[[User:Benw|Benw]] ([[User talk:Benw|talk]]) 18:08, 7 January 2015 (EST)

← Older revision		Revision as of 12:20, 3 May 2018
Line 19:		Line 19:

	--[[User:Benw\|Benw]] ([[User talk:Benw\|talk]]) 18:08, 7 January 2015 (EST)		--[[User:Benw\|Benw]] ([[User talk:Benw\|talk]]) 18:08, 7 January 2015 (EST)
		+
		+	==== 2. (Alternate explanation)
		+
		+	We can assume, w.l.o.g., that n is a power of 2. For instance, if n is 16.
		+	We can then calculate minima for the following ranges:
		+	* 0-15
		+	* 0-7 and 8-15
		+	* 0-3, 4-7, 8-11 and 12-15
		+	* 0-1, 2-3, 4-5, 6-7, 8-9, 10-11, 12-13, 14-15
		+
		+	Note that this is O(n) space, or more precisely, (n-1) space.
		+	Now, to calculate the minimum for a particular range, build up non-overlapping ranges from the above set of ranges that cumulatively cover the desired range.
		+	If the range is 3-14, for example, the build-up would be 3; 4-7; 8-11; 12-13, and 14. This is O(log n).
		+	The minimum of the values of these ranges gives us the desired answer. To calculate the minimum of m unsorted values is O(m), and since m is O(log n), the minimum calculation is also O(log n).
		+
		+	--[[User:Ajitq\|Ajitq]] ([[User talk:Ajitq\|talk]]) 12:20, 3 May 2018 (UTC)

← Older revision		Revision as of 23:08, 7 January 2015
Line 17:		Line 17:

	The query function will visit at most two leaf nodes, and runs in <math>O(\log n)</math> time.		The query function will visit at most two leaf nodes, and runs in <math>O(\log n)</math> time.
		+
		+	--[[User:Benw\|Benw]] ([[User talk:Benw\|talk]]) 18:08, 7 January 2015 (EST)

@@ Line 1: / Line 1: @@
-# Use an nxn matrix populated with the distance between the nodes at the two indices.
+==== 1. Design a data structure that uses <math>O(n^2)</math> space and answers queries in <math>O(1)</math> time. ====
-# Solution two choice 2:
-#* http://en.wikipedia.org/wiki/Cartesian_tree[http://en.wikipedia.org/wiki/Cartesian_tree]
+Build an <math>n × n</math> lookup table with the answer to every possible query, indexed by <math>i</math> and <math>j</math>.
-#* http://en.wikipedia.org/wiki/Treap[http://en.wikipedia.org/wiki/Treap]