• Content count

  • Joined

  • Last visited

Community Reputation

151 Neutral

About Krumble

  • Rank
  1. Why not just use arrays as your base and add your node to the end of the array? You can then use the following formulas for children and parents: If your current node is i, then: parent: (i-1)/2 (integer division) left child: 2*(i+1)-1 right child: 2*(i+1)
  2. STL priority_queues

    Keep in mind if you are using pointers with your own comparison function, if you change the 'value' of anything in the priority queue it will not be updated. If you need to be able to raise or lower the priority of a value you will have to write your own priority queue.
  3. Proof or Counter-example

    Quote:Original post by NotAnAnonymousPoster Quote:Original post by Krumble First you must show that each of these subsequences converge to the same limit (This is necissary, but not sufficient for convergence).It is necessary and sufficient. Any sequence consisting of two subsequences convergent with a common limit also converges to that limit. a_n = (-1)^n is divergent. Take the even terms and the odd terms as seperate subsequences. Each of those are convergent to different limits. Or take the even terms, and the terms that are powers of 2. Each of these sequences converges to the same limit, but the original sequence is divergent. If you mean two (or more, but finite) subsequences that comprise the entire original sequence at infinite and they all converge to the same limit, I'd believe you :)
  4. Proof or Counter-example

    Hopefully this isn't giving too much away, but if you take the sequence of even terms and the sequence of odd terms seperately, you can show that one of these sequences is monotonically increasing and one of the sequences is monotonically decreasing. As you stated, the sequence is bounded both below and above, so both these subsequences are convergent. This in itself is not enough to prove that the original sequence is convergent though. First you must show that each of these subsequences converge to the same limit (This is necissary, but not sufficient for convergence). Next if you show that the 'upper' sequence is always >= the 'lower' sequence, you can use the squeeze principal to show convergence of the original sequence. As stated by another poster, the limit is indeed the golden ratio.
  5. Overload the copy constructor and the assignment operator if your class uses pointers internally.
  6. Sorting a class array

    When using stl sorting (or stl with any user defined class for that matter), be sure your class correctly implements the copy constructor and assignment operator if you are using dynamic memory though.
  7. Sorting algorithm.

    It has been shown that comparison based sorting(with no other information pertaining to the distribution of elements etc.) can have no better than O(nlgn) in the best case. Just use your favorite O(nlgn) algorithm that has already been implemented countless times for you.
  8. Heap Tree Sort

    Transforming an array into a heap (in place) is actually an O(n) algorithm. Heapsort can also be done in place, therefore it doesnt require a second array either. Algorithm: Build your heap (use a max heap if you want to sort in ascending order). O(n) for i from n-1 to 1 do swap elements i and 0 in your array max-heapify(array, 0) done The basic idea of this is, is if you are using an array to model your heap, the first element will be the biggest element (using a max heap). The biggest element must also be the last element in a sorted array. By swapping the biggest element into its correct sorted position and decreasing the heap size by 1 we now have an almost heap and the last element in its correct sorted position. By calling max-heapify on our heap, we recreate a valid heap. Max-heapify is an O(lgn) operation, and we must do it O(n) times, this is where the O(nlgn) complexity comes from.
  9. I'm developing a web application using JSP and Apache Tomcat 5. I have a series of class files tucked away in WEB-INF/classes/... I'm trying not to put too much code in the actual jsp files themselves. Tomcat seems to have an issue where if I alter the files in the class directory, it wont reload them unless I physically restart the server. Is there anyway that I can get Tomcat to check for changes in the .class files while I'm developing my application? or just have tomcat reload them every time? Thanks.
  10. Computing the (Discreet) log of a number.

    Choose x=0 and your formula is undefined.
  11. Computing the (Discreet) log of a number.

    The discrete log is dependant on the operation that you are performing. It doesnt really make sense to talk about 'the discrete logarithm of a number' since you haven't stated the operation at all. I'm assuming you mean how is the discrete logarithm of a number that has been multiplied by itself modulo n. The problem is in general hard without additional information. With respect to RSA, I'm sure there might be some 'smarter' methods of doing it than trying every number, but there is no known polynomial time algorithm for it AFAIK.
  12. Points on convex hulls

    Look up a Graham Scan on goggle. It runs in nlogn time, so you wont get much better than that unless you know anything in particular about the data you enter.
  13. I don't quite understand your question, but binary search is O(logn) which is so much better than O(n).
  14. binomial coefficients

    To calculate a binomial coefficient you need to calculate 3 factorials, which can be done with 3 loops. Beware of overflow though.
  15. Webcam script

    Upload the image to a temporary file then move the temporary file over the image you are viewing.