Welcome, Guest
You have to register before you can post on our site.

Username/Email:
  

Password
  





Search Forums

(Advanced Search)

Forum Statistics
» Members: 106
» Latest member: rlrice2
» Forum threads: 244
» Forum posts: 1,036

Full Statistics

Online Users
There are currently 4 online users.
» 0 Member(s) | 3 Guest(s)
Google

Latest Threads
TEST #9 set-1-18.c
Forum: Project 3
Last Post: sbcarp
4 hours ago
» Replies: 0
» Views: 2
RBT working perfectly on ...
Forum: Project 2
Last Post: avevans
6 hours ago
» Replies: 6
» Views: 67
Submission1 test not avai...
Forum: Project 3
Last Post: humblebeast
7 hours ago
» Replies: 0
» Views: 8
How to check if x is the ...
Forum: Project 2
Last Post: sbcarp
10 hours ago
» Replies: 1
» Views: 15
Alternate Disjoint Set Se...
Forum: Project 3
Last Post: sbcarp
10 hours ago
» Replies: 1
» Views: 22
Different Expected Test R...
Forum: Project 3
Last Post: sbcarp
Yesterday, 10:39 PM
» Replies: 2
» Views: 24
rotation clarification
Forum: Project 2
Last Post: lusth
Yesterday, 03:26 PM
» Replies: 5
» Views: 82
Question about Path Compr...
Forum: Project 3
Last Post: sbcarp
Yesterday, 01:08 AM
» Replies: 3
» Views: 30
Extra credit for Assignme...
Forum: Project 2
Last Post: jdtubbs3
11-13-2018, 07:45 PM
» Replies: 2
» Views: 2,067
last semester's final KEY
Forum: Final exam
Last Post: sbcarp
11-13-2018, 03:41 PM
» Replies: 0
» Views: 21

 
  TEST #9 set-1-18.c
Posted by: sbcarp - 4 hours ago - Forum: Project 3 - No Replies

https://www.diffchecker.com/8E7hek41
(Left side is expected result)
Looks like path compression is still exists in server disjoint set file.




(7 hours ago)humblebeast Wrote: This belongs in project 3, not 2. But yeah, I though we weren't supposed to print based on predecessors, not on findSet

Yeah, moved to Project 3.

Print this item

  Submission1 test not available for download
Posted by: humblebeast - 7 hours ago - Forum: Project 3 - No Replies

wget beastie.cs.ua.edu/cs201/testing/3/submission1.tgz says that the resource cannot be found, and putting the link in my browser gives me a 404

Print this item

  How to check if x is the root in rotate
Posted by: dmwever - 10 hours ago - Forum: Project 2 - Replies (1)

So for some reason, my code seg faults whenever I get to this line in my rotate functions. This basically checks if x is the root. 


if (getRBTroot(bree) == x) setRBTroot(bree, y);

The reason I use this instead of:

if (getTNODEparent(x) == 0)

Is because in Lusth's tests, he sets his root->parent to equal itself, so I had to modify my code so it would work on his tests. Perhaps I am misunderstanding the way that I have to implement my code, but it simply did not work when I set the root's parent to null, and worked when I set it to equal itself, and likewise, it isn't working now when I set the root's parent to itself.

What am I doing wrong?

Print this item

  Alternate Disjoint Set Segfault Bug
Posted by: JackODonohue - 11 hours ago - Forum: Project 3 - Replies (1)

I was testing my project against the test cases on the server, and my code segfaulted when tested with the alternate disjoint set. I was able to remedy this by setting the set freer to a no-op. Next I removed my calls to setSETfree, and I compiled my code with -fsanitize=address and -fsanitize=undefined, and I got the following output.

Code:
ASAN:DEADLYSIGNAL
=================================================================
==32097==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x560e8de68341 bp 0x6030000017b0 sp 0x7ffd1649eaa0 T0)
==32097==The signal is caused by a READ memory access.
==32097==Hint: address points to the zero page.
   #0 0x560e8de68340 in freeSETNODE /home/drop/cs201/lusth/test3/jrodonohue@crimson.ua.edu/set.c:180
   #1 0x560e8de55f17 in freeDA /home/drop/cs201/lusth/test3/jrodonohue@crimson.ua.edu/da.c:209
   #2 0x560e8de6b286 in freeSET /home/drop/cs201/lusth/test3/jrodonohue@crimson.ua.edu/set.c:135
   #3 0x560e8de51737 in solve /home/drop/cs201/lusth/test3/jrodonohue@crimson.ua.edu/kruskal.c:264
   #4 0x560e8de51737 in main /home/drop/cs201/lusth/test3/jrodonohue@crimson.ua.edu/kruskal.c:70
   #5 0x7f2db3172b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
   #6 0x560e8de528e9 in _start (/home/grader/cs201/lusth/test3/jrodonohue@crimson.ua.edu/kruskal+0x288e9)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /home/drop/cs201/lusth/test3/jrodonohue@crimson.ua.edu/set.c:180 in freeSETNODE
==32097==ABORTING

I found this behavior to be quite surprising since the set constructor doesn't have a freer parameter and other data structures that we have written don't exhibit this behavior, so this seems like a bug in the alternate disjoint set. Has anyone else had similar problems?

Print this item

  RBT working perfectly on my machine but segfaults on the test server
Posted by: cmtudor - Yesterday, 11:30 PM - Forum: Project 2 - Replies (6)

RBT works perfectly on my machine...works perfectly on Lusth's server when he runs MAKE TEST...but segfaults immediately upon trying to delete 3 (test is rbt-0-0.c). Anyone have ideas as to why this might be? I've attached the output I get, along with the valgrind output I get. 

Output: 
.png   Screen Shot 2018-11-15 at 17.26.29.png (Size: 24.16 KB / Downloads: 3)

Valgrind 1: 
.png   Screen Shot 2018-11-15 at 17.28.10.png (Size: 263.24 KB / Downloads: 4)
Valgrind 2: 
.png   Screen Shot 2018-11-15 at 17.28.23.png (Size: 244.89 KB / Downloads: 3)

Print this item

  Different Expected Test Results
Posted by: sbcarp - Yesterday, 12:29 AM - Forum: Project 3 - Replies (2)

I submitted to test 3 dropbox 2 times today, the expected outputs for set-0-2.c are not identical. 

5:21 AM Version

Quote:TEST #2
     test program is set-0-2.c (alloted time: 2s)

EXPECTED RESULTS:
--------------------------------------------------------------
REAL test of SET, simple
0: 8.000000(0)
1: 4.000000(0)
2: 0.000000(0)
3: 12.000000(0)
4: 18.000000(0)
5: 6.000000(0)
6: 14.000000(0)
7: 16.000000(0)
8: 10.000000(0)
9: 2.000000(0)
unioning 8 and 4
unioning 3 and 9
unioning 2 and 1
unioning 4 and 5
unioning 1 and 5
unioning 5 and 2
unioning 8 and 8
unioning 3 and 7
0: 8.000000(0)
1: 4.000000(2)
2: 0.000000 4.000000
3: 12.000000(1)
4: 18.000000 4.000000
5: 6.000000 18.000000 4.000000
6: 14.000000(0)
7: 16.000000 12.000000
8: 10.000000 18.000000 4.000000
9: 2.000000 12.000000
--------------------------------------------------------------




6:18 PM Version
Quote:TEST #2
     test program is set-0-2.c (alloted time: 2s)

EXPECTED RESULTS:
--------------------------------------------------------------
REAL test of SET, simple
0: 8.000000(0)
1: 4.000000(0)
2: 0.000000(0)
3: 12.000000(0)
4: 18.000000(0)
5: 6.000000(0)
6: 14.000000(0)
7: 16.000000(0)
8: 10.000000(0)
9: 2.000000(0)
unioning 8 and 4
unioning 3 and 9
unioning 2 and 1
unioning 4 and 5
unioning 1 and 5
unioning 5 and 2
unioning 8 and 8
unioning 3 and 7
0: 8.000000(0)
1: 4.000000(2)
2: 0.000000 4.000000
3: 12.000000(1)
4: 18.000000 4.000000
5: 6.000000 4.000000
6: 14.000000(0)
7: 16.000000 12.000000
8: 10.000000 4.000000
9: 2.000000 12.000000
--------------------------------------------------------------

FindDiff
https://www.diffchecker.com/dx6JsvXC

Print this item

  Question about Path Compression
Posted by: amjohnson36 - 11-14-2018, 10:18 PM - Forum: Project 3 - Replies (3)

One of the examples given on the assign3 page is this:

   $ cat g2
   10 0 9 ;
   6 7 11 ;
   5 9 1 ;
   4 8 7 ; 10 8 6 ;
   11 12 2 ;
   1 6 5 ;
   0 6 10 ; 0 5 3 ; 0 4 8 ; 0 3 2 ; 0 1 4 ;
   $ kruskal g2
   0: 0
   1: 3(0)2 5(0)3 1(0)4 4(0)8
   2: 9(5)1 6(1)5 8(4)7
   3: 10(8)6 7(6)11
   weight: 47
   $



I understand why this is, but I'm also a bit confused. If we implement Kruskal's to where you call findset() on the two vertices, wouldn't path compression bring them up? Like when we add 10 to the MST, it is like this 10 > 8 > 4 > 0. But later when we check the edge between 10 and 0, it runs findset() on 10 and therefore it ends up being 10 > 0, 8 > 0, and 4 > 0.


EDIT: Also for clarification, shouldn't this say EMPTY as the nodes 11 and 12 are not connected?

Print this item

  rotation clarification
Posted by: aaduerr - 11-14-2018, 09:48 PM - Forum: Project 2 - Replies (5)

I'm not sure what the target node would be in accordance with Lusthian pseudo code (http://beastie.cs.ua.edu/cs201/insert-rb.html) when calling rotate. In the following, if 1 was just inserted would it be rightRotate(3) or rightRotate(2)?

.          3
.         /
.       2*
.      /
.    1*


On second thought, I supposed it doesn't matter as long as we're consistent. But what would be the easier/better way?

Print this item

  last semester's final KEY
Posted by: sbcarp - 11-13-2018, 03:41 PM - Forum: Final exam - No Replies

I know everyone is busy during final, so here is the key for convenience. 

Page 1
1. C
2. G
3. A
4. A
5. C

Page 2
6. C
7. F
8. E
9. A
10. E
11. G

Page 3
12. A
13. D
14. F
15. C
16. H
17. F

Page 4
18. A
19. F
20. D
21. E
22. F
23. A
24. F

Page 5
25. F
26. E
27. F
28. C
29. E

Page 6
30. F
31. T
32. C
33. C
34. H
35. C
36. D

Print this item

  bi-weekly gradings
Posted by: lusth - 11-13-2018, 03:08 PM - Forum: Miscellaneous - No Replies

I'm going to start grading Thursday evenings now until the end of class. The deduction for not passing all tests will drop to 5 points for each grading. So, if you only submit weekly, there will be no change.

This applies to all projects.

Print this item