Aha! So here are conventional enqueue and dequeue operations in Scheme
(sorry I'm more familiar with scheme than with lisp :) ). The set-car!
and set-cdr! are self-explanatory.
(define (enqueue! queue item)
(let ((new-pair (cons item nil)))
(cond ((empty-queue? queue)
(set-front-ptr
Googmeister wrote:
> > Hi Gm,
> >
> > If finding this interval requires linear time, then the run time is
> > proprtional to n^2
>
> No. It's the standard n log n recurrence.
>
> > because there is no bound on the size of the
> > interval you're searching for
>
> Yes there is. At each recursive c
Googmeister is right!
A simple and wonderful solution in O(n log n)
The strange thing I notcied is... we are getting algorithms simiar to sorting algorithms like mergesort and quicksort for this problem
Looks like there is a strange connection between sorting and this problem...
On 6/2
Gene wrote:
> Googmeister wrote:
> > Pradeep Muthukrishnan wrote:
> > > I have been trying this problem for quite some time now...but havent
> > > found anything concrete...can anyone solve this?
> > > http://acm.zju.edu.cn/show_problem.php?pid=2642
> >
> > Here's a O(n log n) mergesort style sol
Googmeister wrote:
> Pradeep Muthukrishnan wrote:
> > I have been trying this problem for quite some time now...but havent
> > found anything concrete...can anyone solve this?
> > http://acm.zju.edu.cn/show_problem.php?pid=2642
>
> Here's a O(n log n) mergesort style solution:
>
> * Divide the e
I mean pointers in a purely functional implementation like my lisp
code. The only reason I can think that you'd actually implement with
no pointer mutation in C++ is to improve parallel access in a
mult-threaded system. Then you'd need garbage collection (like smart
pointers for example) to make
Arunachalam wrote:
> Sorry,
> I did not read the Gene's solution properly. Great work Gene. I
> doubt the solution given above.
>
>
> On 6/27/06, Googmeister <[EMAIL PROTECTED]> wrote:
> >
> >
> >
> > Pradeep Muthukrishnan wrote:
> > > I have been trying this problem for quite some time
Sorry,
I did not read the Gene's solution properly. Great work Gene. I doubt the solution given above.
On 6/27/06, Googmeister <[EMAIL PROTECTED]> wrote:
Pradeep Muthukrishnan wrote:> I have been trying this problem for quite some time now...but havent
> found anything concrete...can any
CPP program based on Vikram Venkatesan's Algo:#include #include using namespace std;class arr{ int *a; int n; /*No. of elements in an array*/
public: arr() { a=0; n=0; } arr(int num_of_elements) { n = num_of_element
Arunachalam,
Giving a quick thought... i felt duplicates are not going to affect my algorithm... If you have duplicate minimums you can select any one (may be the most central one) as the pivot and proceed...
Am i correct?
On 6/27/06, Googmeister <[EMAIL PROTECTED]> wrote:
Arunachalam wrote:>
Arunachalam wrote:
> Gene's solution also works fine. But this will also be n^2. since we have
> to scan back to get the upper and lower bound. for each element i, we have
> to go through all the elements and get the lower and upper bound. ( Huh...
> same problem again).
Gene uses balanced BST
Pradeep Muthukrishnan wrote:
> I have been trying this problem for quite some time now...but havent
> found anything concrete...can anyone solve this?
> http://acm.zju.edu.cn/show_problem.php?pid=2642
Here's a O(n log n) mergesort style solution:
* Divide the elements in the middle: a[l..m-1]
12 matches
Mail list logo
