Tree/LogN Min Search - Revision history

Admin: /* Problem 3-11 */

2019-03-09T22:37:24Z

Problem 3-11

← Older revision		Revision as of 22:37, 9 March 2019
Line 9:		Line 9:
	Part a - design a data structure using <math>O(N^2)</math> space, answering queries in <math>O(1)</math> time.		Part a - design a data structure using <math>O(N^2)</math> space, answering queries in <math>O(1)</math> time.

	Part b - design a data structure using <math>O(N)</math> space, <math>O(log N)</math> time.		Part b - design a data structure using <math>O(N)</math> space, <math>O(\log N)</math> time.

	===Part a===		===Part a===
Line 22:		Line 22:

	Part b had me stumped for a while.		Part b had me stumped for a while.

			We want a data structure using <math>O(N)</math> space, and we want lookups to take <math>O(\log N)</math> time.

	The Algorist wiki ([http://www.algorist.com/algowiki/index.php/TADM2E_3.11 link]) gives one possible solution, but that's a bit tricky. Even the solution takes some puzzling over.		The Algorist wiki ([http://www.algorist.com/algowiki/index.php/TADM2E_3.11 link]) gives one possible solution, but that's a bit tricky. Even the solution takes some puzzling over.

	~~Solution~~ involves a log ~~n term~~, so it must be a tree.		The solution involves log lookup time, so it must be a tree. One tree node per array element.

			The tree data structure should look something like a min heap, where a node higher on the tree indicates a "more global" minimum. That is, each node represents a particular range of indices, and the higher on the tree a node is, the larger the range of indices it covers.

			O(N) Space:

			Each node stores a single minimum value that represents the minimum in that range. Constant space for each node means O(N) space is achieved.

	~~Implement a binary tree, where each tree node represents a particular range of indices. The higher in the tree a node is, the larger the range of indices it covers.~~		O(lg N) lookups:

	The root node ~~spans~~ the ~~whole input sequence. The root node's children span the left and right halves~~ of the input sequence. ~~Etc~~.		The root node represents the range of the entire input sequence. It stores the global minimum.

	~~Each leaf spans a single element range~~ of input, ~~meaning there are log(N) levels to~~ the tree ~~(where N is~~ the ~~number of indices~~ in ~~the array)~~.		The root node's children span the left and right halves of the input sequence. Similar to a binary search, each level in the tree cuts the array size in half.

	~~The lowest value~~ in the ~~range~~ is the value at that ~~position in the input sequence~~.		Each leaf spans a single element range of input, so there are lg N levels in the tree. (N = number of items in our array) If there is a single node, the minimum for that one-element span is the value of that element.

	Total O(N) nodes in tree.		Total O(N) nodes in tree.

Admin: /* Part b */

2019-03-09T22:29:36Z

Part b

← Older revision		Revision as of 22:29, 9 March 2019
Line 21:		Line 21:
	===Part b===		===Part b===

	~~I puzzled over part~~ b ~~fora long~~ while.		Part b had me stumped for a while.

	The Algorist wiki ([http://www.algorist.com/algowiki/index.php/TADM2E_3.11 link]) gives one possible solution, that's a bit tricky. Even the solution takes some puzzling over.)		The Algorist wiki ([http://www.algorist.com/algowiki/index.php/TADM2E_3.11 link]) gives one possible solution, but that's a bit tricky. Even the solution takes some puzzling over.

			Solution involves a log n term, so it must be a tree.

	Implement a binary tree, where each tree node represents a particular range of indices. The higher in the tree a node is, the larger the range of indices it covers.		Implement a binary tree, where each tree node represents a particular range of indices. The higher in the tree a node is, the larger the range of indices it covers.

Admin: /* Part a */

2019-03-09T22:27:14Z

Part a

← Older revision		Revision as of 22:27, 9 March 2019
Line 13:		Line 13:
	===Part a===		===Part a===

	~~For part a =~~ use a hash table. ~~We pass it every combination of~~ (i,j) and ~~save~~ the minimum value ~~as a value~~. ~~Use~~ <math>O(N^2)</math> space, <math>O(1)</math> time.		Part A: using <math>O(N^2)</math> storage space means we do pairwise pre-processing of our values.

			The solution here is to use a hash table. During pre-processing we iterate over all <math>N^2</math> combinations (i,j) and compute the minimum value for each and store it.

			Uses <math>O(N^2)</math> space, <math>O(1)</math> time.

	===Part b===		===Part b===

Admin: /* Problem 3-11 */

2019-03-09T22:25:16Z

Problem 3-11

← Older revision		Revision as of 22:25, 9 March 2019
Line 3:		Line 3:
	==Problem 3-11==		==Problem 3-11==

	'''Problem 3-11:''' Suppose we're given a sequence of values x1, x2, ~~...~~, ~~xn and~~ we seek to quickly answer questions of the form: given i, ~~given~~ j, find the ~~samllest~~ value in xi, ~~...~~, xj.		'''Problem 3-11:''' Suppose we're given a sequence of values <math>x_1, x_2, \dots, x_n</math>

			Now suppose we seek to quickly answer questions of the form: given <math>i, j</math>, find the smallest value in the subsequence <math>x_i, \dots, x_j</math>.

	Part a - design a data structure using <math>O(N^2)</math> space, answering queries in <math>O(1)</math> time.		Part a - design a data structure using <math>O(N^2)</math> space, answering queries in <math>O(1)</math> time.

Admin: /* Flags */

2017-09-07T12:16:14Z

Flags

← Older revision		Revision as of 12:16, 7 September 2017
Line 41:		Line 41:

	[[Category:Trees]]		[[Category:Trees]]
			[[Category:Binary Trees]]
			[[Category:Intervals]]
			[[Category:Skiena]]
			[[Category:Computer Science Problems]]

Admin: /* Question */

2017-09-07T12:15:24Z

Question

← Older revision		Revision as of 12:15, 7 September 2017
Line 1:		Line 1:
	=Skeina, The Algorithm Design Manual, Chapter 3=		=Skeina, The Algorithm Design Manual, Chapter 3=

	==~~Question~~==		==Problem 3-11==

	'''Problem 3-11:''' Suppose we're given a sequence of values x1, x2, ..., xn and we seek to quickly answer questions of the form: given i, given j, find the samllest value in xi, ..., xj.		'''Problem 3-11:''' Suppose we're given a sequence of values x1, x2, ..., xn and we seek to quickly answer questions of the form: given i, given j, find the samllest value in xi, ..., xj.

	Part a - design a data structure using O(N^2) space, answering queries in O(1) time.		Part a - design a data structure using <math>O(N^2)</math> space, answering queries in <math>O(1)</math> time.

	Part b - design a data structure using O(N) space, O(log N) time.		Part b - design a data structure using <math>O(N)</math> space, <math>O(log N)</math> time.

	===Part a===		===Part a===

	For part a = use a hash table. We pass it every combination of (i,j) and save the minimum value as a value. ~~Ues~~ O(N^2) space, O(1) time.		For part a = use a hash table. We pass it every combination of (i,j) and save the minimum value as a value. Use <math>O(N^2)</math> space, <math>O(1)</math> time.

	===Part b===		===Part b===

	I puzzled over part b fora long while~~. [This wiki](http://www.algorist.com/algowiki/index.php/TADM2E_3.11) gives one possible solution. A bit tricky, and even the solution takes some puzzling over~~.		I puzzled over part b fora long while.

	~~Implement~~ a ~~binary tree - each tree node will hold~~ the ~~lowest value for a particular range of indices~~.		The Algorist wiki ([http://www.algorist.com/algowiki/index.php/TADM2E_3.11 link]) gives one possible solution, that's a bit tricky. Even the solution takes some puzzling over.)

	The ~~root~~ node ~~spans~~ the ~~whole input sequence~~.		Implement a binary tree, where each tree node represents a particular range of indices. The higher in the tree a node is, the larger the range of indices it covers.

	The root node's children span the left and right halves of the input sequence.		The root node spans the whole input sequence. The root node's children span the left and right halves of the input sequence. Etc.

	~~Etc~~.		Each leaf spans a single element range of input, meaning there are log(N) levels to the tree (where N is the number of indices in the array).

	~~Each leaf spans a single element range of input.~~		The lowest value in the range is the value at that position in the input sequence.

	~~Lowest~~ value in range is the value at that position in the input sequence.

	Total O(N) nodes in tree.		Total O(N) nodes in tree.

Admin: /* Flags */

2017-06-10T19:51:43Z

Flags

← Older revision		Revision as of 19:51, 10 June 2017
Line 41:		Line 41:

	{{TreesFlag}}		{{TreesFlag}}

			[[Category:Trees]]

Admin: /* Part b */

2017-06-10T19:51:21Z

Part b

← Older revision		Revision as of 19:51, 10 June 2017
Line 37:		Line 37:
	* Otherwise return lowest results from calling query on LH and on RH (minimum of two, only checking query.low > node.low or query.high < node.high)		* Otherwise return lowest results from calling query on LH and on RH (minimum of two, only checking query.low > node.low or query.high < node.high)
	* Query visits maximum of 2 leaf nodes		* Query visits maximum of 2 leaf nodes

			=Flags=

			{{TreesFlag}}

Admin: Created page with "=Skeina, The Algorithm Design Manual, Chapter 3= ==Question== '''Problem 3-11:''' Suppose we're given a sequence of values x1, x2, ..., xn and we seek to quickly answer ques..."

2017-06-10T15:32:20Z

Created page with "=Skeina, The Algorithm Design Manual, Chapter 3= ==Question== '''Problem 3-11:''' Suppose we're given a sequence of values x1, x2, ..., xn and we seek to quickly answer ques..."

New page

=Skeina, The Algorithm Design Manual, Chapter 3=

==Question==

'''Problem 3-11:''' Suppose we're given a sequence of values x1, x2, ..., xn and we seek to quickly answer questions of the form: given i, given j, find the samllest value in xi, ..., xj.

Part a - design a data structure using O(N^2) space, answering queries in O(1) time.

Part b - design a data structure using O(N) space, O(log N) time.

===Part a===

For part a = use a hash table. We pass it every combination of (i,j) and save the minimum value as a value. Ues O(N^2) space, O(1) time.

===Part b===

I puzzled over part b fora long while. [This wiki](http://www.algorist.com/algowiki/index.php/TADM2E_3.11) gives one possible solution. A bit tricky, and even the solution takes some puzzling over.

Implement a binary tree - each tree node will hold the lowest value for a particular range of indices.

The root node spans the whole input sequence.

The root node's children span the left and right halves of the input sequence.

Etc.

Each leaf spans a single element range of input.

Lowest value in range is the value at that position in the input sequence.

Total O(N) nodes in tree.

Algorithm:
* Query function is recursive, and passes the query (which has a low and high value), starting from the root
* If the query range matches the current node's range, return the current node's value
* If the query range is entirely within the left/right hand side (query.low > node.low && query.high < node.high), return the result of calling query on left/right hand node
* Otherwise return lowest results from calling query on LH and on RH (minimum of two, only checking query.low > node.low or query.high < node.high)
* Query visits maximum of 2 leaf nodes