|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On June 01 2017 07:58 travis wrote:
Can you explain why it would return 5, 10 as max start and end instead of 0, 10 ?
I thought I had a clue reading that code but maybe I don't, lol
No, you're right. It's not as trivially reduceable to the maximum congruent subarray problem as I thought. The fact that it's circular allows you to do stuff that cannot simply be replicated by making repeating the array. I guess to use this approach, you'd have to simultaneously find the longest stretch you can within your current subarray with a value less or equal to 0. And then do some magic at the end, if necessary.
|
|
|
I don't understand that solution *at all*, anyone have an explanation?
|
The solution covers 2 cases. The first case is that we can use the normal algorithm (the one blisse linked). We can use this algorithm if we don't have to worry about "wrapping around" our circular array.
A couple examples of that are {5, 5, 5} or {-3, 7, 8, 9} or {-2, 6, 3, -1, 7, -5}
In all of those we do not need to wrap to find our subarray. We now have a way to handle this case, so we can include it in our code - we don't need to worry about it anymore.
However there are cases where we do need to wrap around to find our subarray. Examples could be: {7, -2, 7 } or {1, 2, 3, 4, -5, 6, 7 } etc. These are cases where we need to remove negative stuff from the inside but still use both the ends of the array (since if it was a real necklace the end would connect to the beginning).
For those cases we know we have positive elements on the ends, because it is wrapping. So, we know that the subarray that we are removing is NOT wrapping - it's inside the array - not on the ends.
Because we know the subarray to be removed is inside, we can make all our positives negative, and all our negatives positive.
Then we find the greatest sum with this new array, which is actually the part to be removed because the signs were flipped. So our "start position" will be at the end of this subarray(the one that has the part we need to remove), and our "end position" will be just before it begins.
To cover both cases we need to run both algorithms in our code, and compare to see which gives us the greater sum - and that is the one that we will use.
|
Aahh so the trick is flipping the sign bit so that one loop through will get a max value. But you will also have to solve problem where you find "snip points", so that will add a little more complexity.
E: These kind of tricky problems are frustrating. Good job working through it man
|
Sorry, I don't understand why running my originally suggested algorithm with the array 2x and max N wouldn't work.
Changing {7, -2, 7} to {7, -2, 7, 7, -2, 7} would get you the maximum sequence {7, 7}.
Changing {1, 2, 3, 4, -5, 6, 7 } to {1, 2, 3, 4, -5, 6, 7, 1, 2, 3, 4, -5, 6, 7 } would get you the maximum sequence {6, 7, 1, 2, 3, 4}.
|
In both of those cases the maximum sequence would be the full 2x arrays. {7, -2, 7, 7, -2, 7} has a higher value than {7, 7}
|
|
|
On June 01 2017 08:51 travis wrote:
In both of those cases the maximum sequence would be the full 2x arrays. {7, -2, 7, 7, -2, 7} has a higher value than {7, 7}
> ... with the array 2x and max N wouldn't work.
Should've specified max length N, oops.
|
edit: actually let me make sure I know what I am saying is correct
edit2: My brain is starting to get a bit worn out so I can't prove it but I think you lose linear time efficiency by doing what you are saying. I think that every time you reach "n" length subarray you would have to start over, 1 index from where you started last time, over and over again.
Well I guess there might be other ways but it definitely isn't simple
and if you tried to do it using the algorithm you originally posted, you would have to "snip" the subarray it found to shorten it to N length, which would mean you would have to go through all the N-length subarrays within the subarray that it found
|
Yup. More elegant by far than trying to deal with the wrap-around case by snipping out the middle, although it's essentially the same algorithm. It just looks neater that way 
|
so after taking a break from that really weird c project I brought up in this thread a while ago, I've been working on it all day today to figure out the kinks before the due date tomorrow at midnight
I managed to finish it just now and wow it was pretty frustrating
so basically what I did originally was for the most part fine, it's just that the mips simulator completely bugs out unless I follow some rules:
1) has to be in that old C style the professor used. I rewrote my code according to how he wrote his code
2) must define empty __main() function since the simulator calls for it and gives an error if it's not defined
3) must define empty dummy function and call it in each function I am using pointers to access the stack
4) cannot use printf, must use a separate string printing function the professor defined
5) when compiling it into the needed .s file the .c file used must be the same as the .s file. (did not know this and took hours)
also had to change frame pointer along with return address
if people are still interested in the final code I'll post tomorrow after the due date since I'd rather not chance (albeit hilariously small) someone comes across and copies it before the due date. or PM ing is fine
it's basically what I posted before with all those rules followed above. just save the address of the return address and frame pointer in the setjmp function and have the return address and frame pointer in longjmp function be changed to that of the one from setjmp. doesn't work when I write it like how modern human beings write C code. only in that archaic form does it work in the simulator. top 5 stupidest assignments i've had so far in my life not because of the content but because of the horrible guidelines and directions. And so much effort needed for trying to teach something rather simple.
|
On June 02 2017 13:11 dsyxelic wrote:
so after taking a break from that really weird c project I brought up in this thread a while ago, I've been working on it all day today to figure out the kinks before the due date tomorrow at midnight
I managed to finish it just now and wow it was pretty frustrating
so basically what I did originally was for the most part fine, it's just that the mips simulator completely bugs out unless I follow some rules:
1) has to be in that old C style the professor used. I rewrote my code according to how he wrote his code
2) must define empty __main() function since the simulator calls for it and gives an error if it's not defined
3) must define empty dummy function and call it in each function I am using pointers to access the stack
4) cannot use printf, must use a separate string printing function the professor defined
5) when compiling it into the needed .s file the .c file used must be the same as the .s file. (did not know this and took hours)
also had to change frame pointer along with return address
if people are still interested in the final code I'll post tomorrow after the due date since I'd rather not chance (albeit hilariously small) someone comes across and copies it before the due date. or PM ing is fine
it's basically what I posted before with all those rules followed above. just save the address of the return address and frame pointer in the setjmp function and have the return address and frame pointer in longjmp function be changed to that of the one from setjmp. doesn't work when I write it like how modern human beings write C code. only in that archaic form does it work in the simulator. top 5 stupidest assignments i've had so far in my life not because of the content but because of the horrible guidelines and directions. And so much effort needed for trying to teach something rather simple.
Wow...
What class is that? C? Embedded systems?
Also, to anyone familiar with mips: do you really have to use old syntax for it and some non-standard functions or is it just this weird simulator that enforces this?
Super weird assignment. I feel your pain and am glad you made it work.
|
I'll take a look! I write C/C++ professionally so I'd be pretty interested in peeking.
|
|
|
Yup nesserev got it. Thats the book we use and thats what the class is called. I agree hand writing this in assembly would have taught the same thing with less trouble.
@cecil ill pm you after work! Or just post here since its due around then anyways.
And respect to those who work in c, this language hurts me
edit:
here's the code
+ Show Spoiler +
int *ra; //return address
int *fp; //frame pointer
main()
{
int r;
r = setjmp(r);
if(r==0)
{
fun1();
return(0);
}
else
{
print_str("error\n");
return(2);
}
}
__main()
{
return(0);
}
dummy(v)
int v;
{
return(0);
}
setjmp(v)
int v;
{
int *p = &v;
ra = *(p-1);
fp = *(p-2);
dummy(v);
return(0);
}
longjmp(v)
int v;
{
int *p;
p = &v;
*(p-1) = ra;
*(p-2) = fp;
dummy(v);
return(1);
}
fun1()
{
print_str("start fun1\n");
fun2();
return(0);
}
fun2()
{
int d;
print_str("start fun2\n");
longjmp(d);
return(0);
}
print_str(str)
char *str;
{
int code;
code = 4;
asm(
"add $a0, %1, $zero\n\t"
"add $v0, %0, $zero\n\t"
"syscall"
:
: "r" (code), "r" (str));
return(0);
}
//output is:
//start fun1
//start fun2
//error
|
I was wondering if any of you could glance over my homework solutions for this week's "NP-Completeness" homework. It's really short - but I haven't done stuff quite like this and I am liable to screw it up (and some of it is a bit confusing for me)
Here is a link to the homework
http://www.cs.umd.edu/class/summer2017/cmsc351/hwk-np.pdf
this week we do only part 1 - sorting
so the questions I am wanting checked over is questions 2 and questions 3 of part 1
here are my solutions
http://www.filedropper.com/scan0001_2
(I had to click to download it twice before it actually downloaded it)
If you can't tell - my answer for 3a was to "put all the elements of all lists into a linked list" - or I guess that if they already were linked lists (it's not specific) - then link them all together.
note: if you are worried about helping me "cheat", it's not like that for this class. We can work together and review each other's stuff, we just need to write our solutions ourselves. Also, 87% of our grade is our one midterm and final so homework doesn't matter too much. I mostly just care about it so I will be better on the 2 exams.
|
|
|
On June 04 2017 02:38 Nesserev wrote:Show nested quote +On June 04 2017 01:25 travis wrote:I was wondering if any of you could glance over my homework solutions for this week's "NP-Completeness" homework. It's really short - but I haven't done stuff quite like this and I am liable to screw it up (and some of it is a bit confusing for me) Here is a link to the homework http://www.cs.umd.edu/class/summer2017/cmsc351/hwk-np.pdfthis week we do only part 1 - sorting so the questions I am wanting checked over is questions 2 and questions 3 of part 1 here are my solutions http://www.filedropper.com/scan0001_2(I had to click to download it twice before it actually downloaded it) If you can't tell - my answer for 3a was to "put all the elements of all lists into a linked list" - or I guess that if they already were linked lists (it's not specific) - then link them all together. note: if you are worried about helping me "cheat", it's not like that for this class. We can work together and review each other's stuff, we just need to write our solutions ourselves. Also, 87% of our grade is our one midterm and final so homework doesn't matter too much. I mostly just care about it so I will be better on the 2 exams. Your answers for 2 are correct, but you seem to leave out some steps, which is annoying. In 3a, you seem to have missed that you're also supposed to split that big list back up into all those separate lists afterwards in linear time. How will you do that? The answer 3a will affect your answers for 3b, 3c and 3d, because you have to add the preprocessing and postprocessing times.
Hmm ok, I will be more meticiulous about 2.
As for 3 - are you sure I need to do that? I guess that does make sense, but it doesn't explicitly say it.
As for how I would do it - I honestly have no idea. That sounds impossible. I could separate it into lists of the original sizes, but the elements would be all wrong for each list.
Did the math for what I actually did look correct?
Thank you btw, appreciate your time.
edit: oh quick note, the homework says: "In order to get exact results, for the remaining problems in this section, ignore the cost of preparing the lists for input into the sorting package or processing the results (assuming those costs are within reason)."
|
|
|
|
|
|
|
|
EPT
