Conversation started Sep 26, 2011 at 18:55.
Sep 26, 2011 18:55
This one?
2
Q: Help with a recursion algorithm

OghmaOsirisOk, this may seem trivial to some, but I'm stuck. Here's the algoritm I'm supposed to use: Here’s a recursive algorithm. Suppose we have n integers in a non-increasing sequence, of which the first is the number k. Subtract one from each of the first k numbers after the first. (If there are f...

On the SciFi site, we usually go to the chat room if the question needed clarification.
@RMartinhoFernandes Yepper.
@OghmaOsiris Oh, that's not really feasible on SO. SO is huge.
If this isn't the right chatroom to ask that, I can try to find another one. lol
Ok, so you're having trouble with your insertion sort, that it?
Well, its with the algorithm itself. I got the sort sorted out (lulz). But I'm having trouble with the base case in the recursive function
Sep 26, 2011 19:01
@CatPlusPlus Whats wrong with ObjC? (queue flame war)
At least, I think I'm having trouble with the base case. My output is completely different than the answer sheet the prof gave me.
Is your inSort function producing correct results?
Btw, what language is that?
@RMartinhoFernandes C++
Is there a reason not to use std::vector and friends?
@RMartinhoFernandes We haven't gotten to vectors, yet.
Sep 26, 2011 19:05
Ok.
So, have you tested inSort on its own?
I'm testing it now, Just a sec.
@CatPlusPlus Whats wrong with ObjC? (queue flame war)
@RMartinhoFernandes It looks to work with the exception of the very last element of the array.
It seems to blow up: ideone.com/eArKT
Let's see what's wrong with it.
You're probably going out of the bounds of the array.
So, you're testing for (i < length) && (x[i] < key).
And you're accessing x[i] and x[i+1].
@RMartinhoFernandes Oh, I updated the bounds per one of the answers. I will update my question to reflect.
Sep 26, 2011 19:10
So, what happens when i is length-1?
@OghmaOsiris Oh, please do.
user457812
@Moshe Probably not much of a flame war there.
@nil heh
@RMartinhoFernandes When length was length-1 it crashed. when it was length-2 it went through.
Ok, that fixes the out of bounds. But it's not producing correct results. ideone.com/1RmEi Let's see why.
Wait, my test there is wrong.
I should be comparing a with a known sorted vector, not the original. Duh-
user457812
Oh goody, I can buy ICO and Shadow of the Colossus for the PS3 soon
@nil SotC was way ahead of its time.
sbi
sbi
@RMartinhoFernandes That is actually fairly easy. I haven't really programmed in C++ for 2.5 years, and even when I hacked C++ for a living, I never read the standard.
@OghmaOsiris It's messing up things.
user457812
So I've heard. I never played it, though I've wanted to.
sbi
sbi
@OghmaOsiris Is it just me or is there something fundamentally wrong with this statement?
Sep 26, 2011 19:17
@nil You'll love it. (If you don't, I pity you.)
@sbi I've learned my lesson about going ahead of the class, lol... It's only gotten me in trouble. So I do what I'm told within the boundaries of what they assign.
"3 3 3 4" is indeed sorted, but in the reverse order and not with the original values.
So, what could be causing the code to overwrite everything with 3?
@RMartinhoFernandes Should I do a swap?
@OghmaOsiris Don't worry about the order. Let's focus on why the original values are being destroyed.
@RMartinhoFernandes x[i+1] = x[i], then when x gets to x[i+1] it will always be that 3.... I think
sbi
sbi
Sep 26, 2011 19:20
@OghmaOsiris No, it's not you who is wrong there, it's your teacher. When I taught C++, std::vector appeared in the 2nd or 3rd lesson, right after "Heloo, world!", std::string, and std::cin/std::cout. It's the Swiss Army Knife of containers in C++. When I was programming in C++, I hardly ever had a .cpp file where it wasn't used. It's plain stupid to not to teach this early on.
@OghmaOsiris Right. Curious why it doesn't get to overwrite the last one, huh?
@RMartinhoFernandes because it stops at the bounds of the array.
Ok, so the body of the loop is obviously the problem.
How should we fix it?
create a temp value to store what's currently in x[i+1] then assign x[i] to that?
That's similar to what you currently have. key = x[j]; is doing something like that.
Sep 26, 2011 19:24
@sbi You know how many times I hear this from programmers? lol. Everyone always says, "Why aren't they teaching [insert commonly used shortcut here] day 1?"
And the answer is, "I just do what they tell me like a good little student." lol
@RMartinhoFernandes Then if the temp value is currently stored, what is the problem?
Hiya boys and .... well boys
Think about it. Given my "3 4 1 6" example, you're storing 4. Then you proceed to copy 3 over that place "3 3 1 6". That's good so far, we didn't lose 4. But then what happens next? You copy that 3 over to the next "3 3 3 6". Ooops, we just lost the 1.
How can you avoid losing the 1?
How did you not lose 4?
@LewsTherin It's stored in key! We can get it back if we want.
Oh wait...I will read from the beginning
ok so 4 is stored in a temp variable?
Sep 26, 2011 19:29
Yes.
I see :)
I did insert sort before..I can't remember how to do it until I see the algorithm again :(
@RMartinhoFernandes Would I put the 4 in the front then store the 3?
which would check against the 1, then store the 1 and it would check against the 6.
sbi
sbi
@OghmaOsiris No, I'm not debating about just another feature you could have learned before some other features. I'm debating the fundamental approach here. Basically, there's two didactic schools for teaching C++.
The old school teaches the old, C-style stuff first, and modern, C++-style stuff later, and never teaches to use anything unless its innards can be fully understood. Which means students will have to unlearn stuff later in order to use the "right", good, safe idioms once they understand them. The new school teaches the right idioms from day one, never mind how the stuff works under the hood. That is only explained later. You can probably guess that I'm a violent advocate of the modern approach.
@sbi I support the modern approach
C++ is just not C with classes, it's much much more than that
@OghmaOsiris That could probably be made to work, but you'd end up with bubble sort instead :)
Sep 26, 2011 19:34
@RMartinhoFernandes Which I know isn't efficient.
sbi
sbi
@vivek You rarely ever hear someone who has understood these two support the old approach. Sadly, that leads me to believe that the fact that it's still taught so much is based on teacher not having fully understood what they are teaching.
@OghmaOsiris Ok, so since you were wandering into bubble sort territory, let's recap how insertion is supposed to work.
@RMartinhoFernandes That would be helpful as I've never done it before, lol.
Ok, insertion sort works by always keeping the initial part of the array sorted.
Basically, each (outer) cycle you grab the next value, and put it in its place in that initial sorted portion (the part with the outlines in the picture).
Do you understand that?
@RMartinhoFernandes Yeah. I get that.
Sep 26, 2011 19:38
Ok. I think it's better if you rewrite the algorithm instead of working what you have into that.
Let's start with the inner loop, which is responsible for the "put it in its place in that initial sorted portion" part.
So, say you have elements 0 through i-1 (I'm going to use i for the outer loop and j for the inner loop) already sorted. As if you can see from the animation, the first thing the inner loop should do is store the element that we will be putting into place, which is at index i.
why do floats get padded with 0's as the numbers get bigger
So, we get something like int current = a[i];.
Now, after that, the elements in the sorted portion are shifted to the right until a suitable position is found for our current element.
How do we determine a suitable position?
@RMartinhoFernandes if current < previous?
Right, because we're sorting in decreasing order (I almost forgot that).
And the shifting part we already know how to do, x[j+1] = x[j];.
So, we'll have for(???; current < x[j]; ???) { x[j+1] = x[j]; }.
Now, look at that animation above and notice in what order the elements are shifted.
We shift the elements on the right first.
That's so we don't write over anything we will need later.
So, that means the inner loop will work backwards.
With me so far?
@RMartinhoFernandes A little...
Sep 26, 2011 19:49
See if you can fill in the blanks in the inner for loop.
for(int i = current; i < x[j]; i--)
?
Almost. current stores the value not the index. (And you swapped i and j:) It should be something like:
for(int j = i-1 /* start from the index before current */;
    j >= 0 /* don't go past the beginning */ && current < x[j];
    --j /* decrease */)
(Again I'm using i for the outer loop and j for the inner loop)
You get that?
Ok, I think I get it.
Neat. Now, what happens after the shifting?
on the inner loop I'm doing the x[i+1] = x[i]; right?
And the outer loop I'm storing the current value?
Sep 26, 2011 19:57
Right. You store current before starting the inner loop.
I don't see where my initial went wrong then.
The loop. It's backwards.
Ok. I see that now.
Yours was forwards.
How would I reverse the order then?
Sep 26, 2011 19:59
Swap the comparison. > instead of <.
on both?
for(int j = i-1 /* start from the index before current */;
j <= 0 /* don't go past the beginning */ && current > x[j];
--j /* decrease */)
?
No, just the current vs x[j] part.
You don't want j to be <= 0!
Ok, I switched just the one comparison, and its still in increasing order.
Show the code.
for(j = 1; j < length; j++) // Start with 1 (not 0)
{
key = x[j];
for(i = (j - 1); (i >= 0) && (key > x[j]); i++) // Smaller values move up
{
x[i+1] = x[i];
}
x[i+1] = key; //Put key into its proper location
}
Sep 26, 2011 20:02
@OghmaOsiris You forgot the -- instead of ++ :)
If you do that, it works fine: ideone.com/ooGm2
I honestly don't see the difference between your code and what I had, other than that one --
That ++ makes all the difference :)
What I meant was, i fixed the -- and it still wasn't working.
It just would be difficult for me to explain it without just giving it out :)
Can someone explain why a double when it is pow(2.0,1000.0) returns a number that loses precision? It gets padded with 0...setprecision doesn't work
Sep 26, 2011 20:05
@OghmaOsiris The sort or the whole isGraphical thing?
@LewsTherin Because you have a number with 4 digits?
@RMartinhoFernandes The sort.
@OghmaOsiris ?
@OghmaOsiris Oh, wait, you got a typo in the condition. You need to use key > x[i] (note i instead of j). Guess I should've gone with your loop variables :( Sorry about that.
@RMartinhoFernandes It works now, with your code lol.
But now I need to figure out the recursive algoritm.
@OghmaOsiris Ok, you need help to get it working or to understand it?
Sep 26, 2011 20:09
@RMartinhoFernandes A little from column a, a little from column b.
Ok. Gimme few secs to re-read the problem description.
I think I get the overall concept, but I'm guessing my base case is off, or what I do with the array after I test the base case is off.
  if (degrees[start] == 0){
      if(degrees[end] < 0)
         return false;
      else
         return true;
  }
This?
Let me see if I understand. Since the array is sorted, you're assuming that if the first value is 0, it's either all zeroes, or it ends with a negative number.
Did I get that right?
@RMartinhoFernandes Yeah
If it has a negative number at the end after being sorted, then the graph isn't graphable.
Ok, first problem is what end means. Note the loops you have all around. You're stopping those loops when i < end. And here you're accessing degrees[end]. Either end is not a valid index, and that's why you want i less than it but degrees[end] is wrong; or it is a valid index, meaning degrees[end] is right but the loops are not going through the whole array.
Sep 26, 2011 20:17
So echo $LINES outputs 26 - as expected - but getenv() returns null pointers for it. It works with every other environment variable. Any ideas?
The first option (end is actually the length, and thus not a valid index) is the simplest, I believe. Just change degrees[end] to degrees[end-1] and it's all valid now.
Bah, the GCC concept checks haven't been updated for C++11 :(
@RMartinhoFernandes That fixed it... lol
It works for all test inputs you have at hand?
Hmm, I think it's not completely correct yet :)
@RMartinhoFernandes Yeah. I was reading in a file and it worked for all the arrays in the file.
Sep 26, 2011 20:19
      isIt = isGraphical(degrees, start+1, end);
Only it's off by 1. It's outputting 1 extra at the end.
Why are you incrementing start?
Because I'm incrementing through the array.
As I understand it, the recursive call should still work on the whole sequence.
This is the prototype given to me in the assignment.
Sep 26, 2011 20:20
Wait, I understood it wrong.
;)
Here are a couple of hints. The easiest way to do the sorting for this problem is to use the insertion sort algorithm you learned in CS 191. For your recursive algorithm, you’ll need three parameters: the address of the array, the starting index, and the ending index. Suppose your function has the prototype
bool isGraphical(int degrees[], int start, int end);
For the recursive call, the address of the array and the ending index don’t change, but you drop the first array element by increasing the starting index by one. Therefore, the recursive call looks like this: isGraphical(degrees, start
That's the rest of the assignment, lol
Yeah, that's right. I was confused.
@RMartinhoFernandes Believe me, you're not the only one, lol
But now to figure out the off by 1 error... Let me update my question so you have my current code.
Paste it somewhere instead (like ideone.com). It's a bit weird to make existing answers meaningless.
Yet another "I have a reinterpret_cast and I'm not afraid to use it" question:
0
Q: char* to double and back to char* again ( 64 bit application)

user965772I am trying to convert a char* to double and back to char* again. the following code works fine if the application you created is 32-bit but doesn't work for 64-bit application. The problem occurs when you try to convert back to char* from int. for example if the hello = 0x000000013fcf7888 then c...

@OghmaOsiris hope your lecturer doesn't find this :P
Sep 26, 2011 20:25
@LewsTherin Doesn't find what?
This transcript or whatever, from what I know they have a way to check assignments and stuff... My college is really against it...try not give him the answer but explanation should be ok
There's something very wrong with the educational system when you're punished for seeking help.
3
@RMartinhoFernandes The answers are still correct. And all the edits are saved in the question history.
5
A: In C++11, what is the point of a thread which "does not represent a thread of execution"?

Howard HinnantNot just guessing: "thread object" refers to a std::thread. "thread of execution" refers to the OS's collection of hardware registers that represent a thread. C++11 is doing nothing but papering over the OS's API for access to OS threads in order to make C++ threading portable across all OS's....

i like the sarcasm with "not just guessing" :)
3
A: In C++11, what is the point of a thread which "does not represent a thread of execution"?

davmacJust guessing, but it simply means that the thread is not started. In other words, it is just an object like any other - there's not necessarily an actual OS thread behind it. To put it another way, if threads were implemented on top of pthreads, creating a C++11 thread object doesn't necessarily...

@RMartinhoFernandes Well, since I'm writing the code and figuring all this out, it's like going to the comp sci rescource center here at UMKC. Only you guys know how to help me, lol
@RMartinhoFernandes Also, I updated my code for your viewing pleasure, lol
Sep 26, 2011 20:28
@RMartinhoFernandes well yeah I think it is to encourage or force students to do it themselves... I believe what they don't like is to copy and paste code from a website
Ok, remind me what was going wrong now?
I included main, because I think the off-by-one is there.
Oh, bad while(!in.eof).
Did you teacher teach you that?
Xeo
Xeo
@RMartinhoFernandes Oh oh
No, lol.
@RMartinhoFernandes What would be better?
Sep 26, 2011 20:30
Oh, good. Because that's a very common wrong way to read until the end.
Xeo
Xeo
while(in >> var) { /*do stuff with var*/ }
What @Xeo said is the canonical way to do it.
@Xeo I'm reading to 2 separate vars, tho
@OghmaOsiris You can outsource all the reading into a function and do something like while(read_one(in, graph)).
Xeo
Xeo
@OghmaOsiris while(in >> var1 >> var2) { ... }
Sep 26, 2011 20:33
@Xeo It's a length prefixed series of values. It must be read in a loop somewhere.
@Xeo I just did while(in >> size) and then the rest of the loop.
it fixed it. :)
@OghmaOsiris That should work as long as the input is wellformed.
I guess that treating ill-formed input is not important here.
@RMartinhoFernandes The input was given to me by the prof. If it's not well formed, it's not my problem, lol.
Right.
So, everything works now?
@RMartinhoFernandes Yep! :D Thanks so much!
Xeo
Xeo
Sep 26, 2011 20:35
@RMartinhoFernandes Oh, sorry, didn't pay attention to what you talked about before :)
@OghmaOsiris nice
Can someone explain why a double when it is pow(2.0,1000.0) returns a number that loses precision? It gets padded with 0...setprecision doesn't work
lol
@OghmaOsiris You're welcome.
 
Conversation ended Sep 26, 2011 at 20:35.