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

Username
  

Password
  





Search Forums

(Advanced Search)

Forum Statistics
» Members: 150
» Latest member: Spooky Boogie
» Forum threads: 112
» Forum posts: 361

Full Statistics

Online Users
There are currently 5 online users.
» 2 Member(s) | 3 Guest(s)
fplux, sammaryland

Latest Threads
log log n Interpretation
Forum: Exam 1
Last Post: sammaryland
1 hour ago
» Replies: 1
» Views: 7
MRT Question
Forum: Exam 1
Last Post: sammaryland
9 hours ago
» Replies: 2
» Views: 37
freeing strings and token...
Forum: Project 1
Last Post: NiceHam
Yesterday, 03:57 PM
» Replies: 2
» Views: 107
Review Session
Forum: Study Groups
Last Post: kamadson
Yesterday, 03:19 AM
» Replies: 0
» Views: 12
Tokens or quoted strings
Forum: Project 1
Last Post: sbcarp
02-17-2018, 05:26 PM
» Replies: 2
» Views: 83
extractHEAP
Forum: Project 1
Last Post: chibbluffy
02-17-2018, 05:50 AM
» Replies: 2
» Views: 103
What was it I said I woul...
Forum: Miscellany
Last Post: sammaryland
02-16-2018, 08:07 PM
» Replies: 1
» Views: 46
Is root node a leaf node?
Forum: Project 1
Last Post: lusth
02-16-2018, 03:36 PM
» Replies: 2
» Views: 109
Max or min heap
Forum: Project 1
Last Post: chibbluffy
02-16-2018, 08:01 AM
» Replies: 1
» Views: 121
Heap test
Forum: Project 1
Last Post: chibbluffy
02-16-2018, 03:50 AM
» Replies: 4
» Views: 144

 
  displayBST() Question
Posted by: DavidTurner - 02-15-2018, 04:01 AM - Forum: Project 1 - Replies (1)

I struggled a bit trying to make sense of the specifications for displayBST(). This is the output for my tree entered in the order 68, 54, 53, 45, 48, 50, 55, 74, 70, 75, and 80. Does this appear to be correct?

Output:

[68 [54 [53 [45 [48 [50]]]] [55]] [74 [70] [75 [80]]]]

Thanks in advance!  Heart Heart Heart Heart Heart

Print this item

  swapToLeafBST() Clarification
Posted by: sbcarp - 02-15-2018, 12:31 AM - Forum: Project 1 - Replies (2)

Quote:extern BSTNODE *swapToLeafBST(BST *t,BSTNODE *node);

swapToLeafBST
 - This method takes a node and recursively swaps its value with its successor's (preferred) or its predecessor's until a leaf node holds the original value. It calls the BST’s swapper function to actually accomplish the swap, sending the two nodes whose values need to be swapped. 



To my understanding, the function should work like this:

I. Check if the node is Null or leaf
    a. If yes
        i. Exit or return leaf node (Edited: Thanks to DavidTurner)
    b. If not
        ii. go to II

II. Find successor of the node. 
    c. If successor exists
        iii. Swap value
    d. If not
        iv. Find predecessor of the node
            1. Swap value

III. Go to I by recursion





=================================================
Does this sounds correct?

Print this item

  statisticsBST
Posted by: WLoumakis - 02-14-2018, 11:01 PM - Forum: Project 1 - Replies (4)

Just to make sure I am understanding the specs correctly, how should the following behave when calling statisticsBST?

                            16
                         /        \
                   15               27
                 /                 /      \
             12               25         29
           /     \            /
        9         14     23
      /          /        /   \
    1        13      20     24
  /
0

should statisticsBST on t result in:
Nodes: 14
Minimum depth: 1
Maximum depth: 5

or:
Nodes: 14
Minimum depth: 2
Maximum depth: 6

Note here that the node that gives minimum depth has value of 15 since it's right child is null, and 0 has the maximum depth since it is the furthest node from the root with a null child. I'm just curious if we're effectively counting the number of edges or the number of vertices we visit.

Print this item

  submission2.tgz
Posted by: aam659 - 02-14-2018, 06:45 PM - Forum: Project 0 - Replies (2)

Trying to make sure that my files are good to go for the resubmit with submission2.tgz, but I noticed that the files included in this directory aren't the most recent ones used for the last round of testing.

Print this item

  Disjoint Sets as SLLs
Posted by: WLoumakis - 02-14-2018, 05:09 PM - Forum: Miscellany - Replies (1)

In class it was mentioned that disjoint sets implemented as SLLs could be unioned in lg(n) time in the worst case, provided you union from the small list to the larger. I was wondering if this would be asymptotic runtime or if this is amortized because the more I think about it, the more it makes sense for it to be O(n) for any given union, since union(A, B) where num(A) = n, num(B) = m, n >= m would run in n/2 time, in the worst case, which is O(n). Let me know where I am going wrong here if I am, please!

Print this item

  Free Function of BST Node
Posted by: sbcarp - 02-14-2018, 04:37 PM - Forum: Project 1 - Replies (1)

Quote:extern void    freeBSTNODE(BSTNODE *n,void (*free)(void *));
This is the definition from BST requirement, the free function pointer called "free". Will the name with built-in function 'free'?

Print this item

  Behavior of compareSTRING
Posted by: fplux - 02-12-2018, 11:09 PM - Forum: Project 1 - Replies (2)

For the compareSTRING function, what is considered to be greater than and less than? Are we comparing the lengths of the strings?

Print this item

  When will we get Project 0 Score?
Posted by: sbcarp - 02-12-2018, 09:46 PM - Forum: Project 0 - Replies (2)

When will we get Project 0 Score of first submission, thanks

Print this item

  Decrease Key for Fib Heap Notes
Posted by: azhall - 02-12-2018, 06:36 AM - Forum: Miscellany - Replies (1)

For the Fibonacci Heap notes posted on the website, I try and click the "Decrease value" link at the end of union and it says that the page is not found. Anyone else having this problem and know how to fix it?

Print this item

  Sorting reals
Posted by: grayson - 02-12-2018, 03:45 AM - Forum: Project 1 - Replies (3)

How should we sort real numbers with our heapsort executable? The comparator for heap expects an integer function, but the compareREAL function in the real.c file returns a double.

Print this item