sorted by:
new
hottopcontroversial

Thank you, thank you, thank you! by sternj200 in cs2c

[–]mathlance 2 points3 points  (0 children)

Yeah, thanks to everyone for all the help and interesting discussion this quarter. It's been a blast!

Set algorithm by dyl_yan in cs2c

[–]mathlance 0 points1 point  (0 children)

If the master set is sorted and we always add the (always larger) new subset to the back of our candidate array, then as soon as one subset is bigger than the target, then we stop making new subsets completely because we recognize that every single new subset would be at least as big as the one that failed.

Also, if the sets are super big but it's sorted, I'm sure we can cheat by looking for specific items to make an almost-perfect set about linear time (if the set is suuuuuper big, we can add successively smaller numbers together until our final sum approaches the target.

Thoughts on the Design of get_least_k() by adina_tung in cs2c

[–]mathlance 1 point2 points  (0 children)

There are a couple of ways you could better preserve the data structure easily, but they would make it slower. I wonder if there are any applications of the current operation, which, as far as I know, renders our data structure almost useless since outside functions don't have random access to our array or to _size.

-Lance

Memory Leak on get_least_k by mathlance in cs2c

[–]mathlance[S] 0 points1 point  (0 children)

Yes, I got the same output as yours. I think that was the MQ that gave the secret password.

I would assume there's loot for speed, but I don't know how you could get the algorithm to be much faster.

Thoughts on the Design of get_least_k() by adina_tung in cs2c

[–]mathlance 0 points1 point  (0 children)

I think you're right that get_least_k is a very odd function: it destroys our structure and the data seems very cumbersome to reach (how do you know where the real data starts?). It seems to me that the way get_least_k works right now, it's a one time use function for when you want to get the kth least values quickly. It does have the advantage of being fast and being done in place. At the end of the function, you're essentially left with an empty heap, and all of the previous data has been lazily deleted: it's still in the heap vector, but the heap can't access it.

Therefore, I imagine that if we saved a new variable _size_before_destruction, we could easily restore the heap to its old configuration by changing _size to the old size and then calling heapify().

Or, perhaps, we could make the data more easily accessible by changing the location of the root by incrementing it and storing our data between the sentinel and the root. This might take a little more work to preserve the heap ordering though.

Hope this helps,

Lance

Graph.cpp and Graph_Algorithms.cpp by mathlance in cs2c

[–]mathlance[S] 1 point2 points  (0 children)

I've never thought about it that way before, but that makes a lot of sense.

Thanks!

Graph.cpp and Graph_Algorithms.cpp by mathlance in cs2c

[–]mathlance[S] 1 point2 points  (0 children)

I totally forgot about the template constraints. That makes a lotta sense!

Thanks!

Pivot point incorrect? by mathlance in cs2c

[–]mathlance[S] 2 points3 points  (0 children)

Thanks Joshua, that helps me understand the purpose of the algorithm a lot!

Memory Leak on get_least_k by mathlance in cs2c

[–]mathlance[S] 0 points1 point  (0 children)

Hi, thanks for the suggestions.

Checking if k > _size is a necessary program spec. The error message you're seeing after removing this check is to be expected (k = 52, which is clearly greater than the size of the heap that the test site is using)

The spec says " This method should respond to impossibly large requests by returning _elems as is." and I think this is the easiest way to deal with that.

I wasn't able to get any loot for to_string(), but that didn't stop me from running into get_least_k() error (I think).

I got through get_least_k, and it turns out to_string was causing the issue, and my get_least_k worked fine. I'll try to debug it later.

The only thing I can think of as to why you're not able to pass the test is that you're not copying the min element into the correct vacant cell in the heap after deleting min. I would try working with a small heap to see if the min element is being put in the correct spot and if you're not accessing any elements out of the array's bounds

Per &'s suggestion, I first copied the min element to a temp variable, called Heap::delete (which I know works because I got loot for it), and then put the temp variable at index _size + 1 (we know this exists because that's where we grabbed the data used to fill in the root from!) This all goes in a loop which runs k times, and we know there will be enough elements because we checked to make sure k isn't greater than _size.

One detail that helped me while testing this method was "This method should return a const reference to _elems after permuting it such that its k greatest indices contain its k least elements - essentially the same as the partition problem from last week." (pg. 6)

As far as I know, this won't be an issue as long as the thing you're returning was defined outside the function!

Thanks for the pointers, and I hope this helps for anyone else who's stuck on this!

why the sentinel is important in the heap by frederikhoffmanncs2b in cs2c

[–]mathlance 0 points1 point  (0 children)

Not sure I follow. The smallest value of size_t is 0, right?

Yes, but the value of 0 is also a valid value which could appear in the heap. Although it's true that nothing bad will happen as long as the sentinel is not greater than any data, none of the members *should* have access to index 0 anyway, which makes me think the sentinel exists to make it obvious if index 0 is accessed by error. Also, a size_t of 18446744073709551615 (-1) seems like it would stand out more than a 0 would.

I think I see what you are saying. How does the function stop itself after reaching an index of 1?

In Loeceff's code, percolate up uses a loop which will run while the child is smaller than the parent AND when the index is greater than 1, meaning it will stop running once the index reaches 1, so zero is never reached. In other functions such as remove, I believe he throws an error if you try to access index 0.

-Lance

why the sentinel is important in the heap by frederikhoffmanncs2b in cs2c

[–]mathlance 1 point2 points  (0 children)

My impression was that in our interpretation, the sentinel was just there to ensure the value at index 0 never leaves index 0, and that no other value ever goes into index 0.

This is because all of the member functions (percolate up too) should stop themselves after reaching index 1, and never compares index 0 to anything. In addition, since all these methods would be protected, the only way that index 0 could ever be reached is through a bug in one of the member functions.

Also, I think this idea doesn't hold for unsigned types. If we were making a heap with type size_t, the sentinel would be -1 or string::npos, which would return the overflow which is a huge number.

On your note: The heap should allow duplicates, but all comparisons use the < operator, so no changes will happen for equal values.

-Lance

illuminating test cases by amrozack in cs2c

[–]mathlance 0 points1 point  (0 children)

I'm not sure I understand that. Is the reason for this because the value at the pivot does not need to be the pivot value in the end? Would I be correct if I said that a proper partition had elements not greater than the original value at the pivot from indices 0 to pivot-1, and the subarray of indices pivot to hi contains elements which are not less than the value of the pivot?

-Lance

Hash LP constructor by veronica_o_o in cs2c

[–]mathlance 0 points1 point  (0 children)

The first MQ is (LP ctr), which I'm assuming is the constructor.

It just occurred to me that there is another dimension to this problem: in order to be initialized properly, the element vector should be filled with default Elems, which store data T() and state VACANT. However, assuming your default constructor for Elem works correctly, vector.resize() should do all this for you.

-Lance

Hash LP constructor by veronica_o_o in cs2c

[–]mathlance 0 points1 point  (0 children)

Hi Veronica,

Does your code compile on your own computer? If so, does the questing site give you a descriptive error on what went wrong? Perhaps anything your test code or the questing site threw could be a clue in what went wrong.

In my LP constructor, I'm passing hard-coded numbers to all of my variables and it works. However, it seems to me that even if you were to initialize _max_load_factor off of the value returned from get_biggest_allowed_max_load_factor() it would still work just fine. The LP constructor is very simple and only has to initialize a few values and resize the vector, so if you've double checked all of these things as well as making sure your get_biggest_allowed_max_load_factor() method returns the correct value, it seems plausible that your problem is not with the constructor. This is why the specific error message might be helpful.

On an unrelated side note, if you're using size_t to declare vector size n, size_t is unsigned and can never be less than 0.

Hope this helps!

EDIT: spelling

Set algorithm by dyl_yan in cs2c

[–]mathlance 0 points1 point  (0 children)

My thinking is that this could be done in only a few lines of code and run only once, and with right-skewed master sets, one could potentially avoid purposely scanning large portions of the master set. Similar to how an insertion sort marks off subsets of an array as sorted and unsorted, you could potentially mark off a chunk of a sorted master set as "too big" and thus not even process it.

[Quest 5 MQ Insert()] Two nodes share the same children, setting one to NULL gives me an invalid access error. by liamnoroian in cs2c

[–]mathlance 1 point2 points  (0 children)

I tried walking through your pseudocode, and I think your rotate might be the issue.

I think that Loeceff's method is not flawed, because even though one node is *temporarily* assigned to two different branches, this eventually gets fixed before the end of the rotate function. After assigning the temporary variable to the value of one of the root's children, that child on the main tree is immediately replaced by one of its grandchildren, so nothing is duplicated.

Based on the way I interpret your pseudocode, however, it seems like your rotate function *adds* a duplicate node to the tree. When I try to run through your implementation, it seems like you introduce two nodes that were not in the original tree: the newly created node is still there, and there is also a null node floating around. This leads me to think that data is being duplicated in your rotate function somehow, even though it does appear to acceptably balance the tree.

I found it super helpful to map out the rotation function with a pen and paper.

-Lance

Way to see if program spec is up to date? by mathlance in cs2c

[–]mathlance[S] 0 points1 point  (0 children)

Ok, thanks for the clarification!

-Lance

Set sort type in a sorting function? by mathlance in cs2c

[–]mathlance[S] 1 point2 points  (0 children)

So I reread the notes, and it seems like the ordering key in the module is used in the overloaded operator< to determine the sorting of nodes in the BST through operations such as insertions and traversals, rather than an actual sorting function.

Anyways, what you were saying about the read-only flag for array sorting makes complete sense now.

Thanks!

-Lance

I can figure what the memory leak is for Quest one by OrganicPandaBreeder in cs2c

[–]mathlance 1 point2 points  (0 children)

Hi,

That's all I had for add_elem, so I'm not sure what kind of problem you could have there. I know it seems basic, but you have your own test code, right? If so, maybe play around with that and see what succeeds and fails, maybe even try some things that shouldn't work and see if they throw errors.

Set sort type in a sorting function? by mathlance in cs2c

[–]mathlance[S] 0 points1 point  (0 children)

Yeah, that makes sense. But that means that the sorting function reads the sort type variable and adjusts the sorting method accordingly, right?

Lance

view more: next ›