C++ homework

Discussion in 'OT Technology' started by mrburner, Oct 5, 2003.

  1. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    i have this short homework assignment for my c++ class...i'm not asking anyone to do it for me, but just help me get started...i don't even know what they are looking for in this

    alright, its setup with directions at the top and then 4 boxes with seperate calls in each one

    directions: Given a list containing N data items, develop worst-case, order-of-magnitude estimates of the execution time of the following List ADT operations, assuming they are implemented using an array. Briefly explain your reasoning behind each estimate

    first box: insert O( )
    explanation:

    second box: remove O( )
    explanation:

    third box: gotoNext O( )
    explanation:

    fourth box: gotoPrior O( )
    explanation:

    any help is appreciated in getting me started or even explaining to me what i'm supposed to do...the directions just aren't clear to me
     
  2. unrealii

    unrealii professor of plant biology

    Joined:
    May 6, 2001
    Messages:
    2,037
    Likes Received:
    0
    Location:
    So CALI
    Look at the ADT, then think to yourself in terms of "N" how long would it take for this method to run?

    Suppose you have this chunk of code:
    for(int i=0;i>n;n++)
    blah;

    Assuming the "blah" runs in a fixed amount of time INDEPENDENT of N then the worse case:
    O() = N

    Example: Since you are using a List with an array, for removing an item out of the list, what would be the longest it would take given you remove from the front, middle or end. You are looking for the worst case which will take the longest in terms of N.
     
  3. Penguin Man

    Penguin Man Protect Your Digital Liberties

    Joined:
    Apr 27, 2002
    Messages:
    21,696
    Likes Received:
    0
    Location:
    Edmonton, AB
    What it's looking for is the order of magnitude for the runtime of each of those functions when they're implemented using an array (presumably a standard C++ array, not a linked list or fancy vector class). I don't know how you've learned execution time magnitudes, but I learned them using big-O notation. So, if a function takes one step for each data member passed to it, it's said to have a magnitude of O(n). If it takes the same amount of time no matter how many members there are, it's O(1). If it's slower for lots of members, but not by much, it's O(log(n)) or O(nlog(n)), if it increases quickly as more members are added, it's O(n^2). I think there are more than that, but I don't remember them all (it's probably the thing I was worst at in the AP C++ curriculum and I haven't done it since May anyway ;)).

    Edit: Damn, you beat me to it :p
     
  4. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    ok so with what you are saying, shouldn't all the 4 functions above just be O(n)? i mean an insert function should just insert a value into the array and that should just take one step...it's not telling me to move all the elements in the array or at least some of them and then pass in the insert function to the open space...or am i thinking of it wrong? i mean should i be thinking that with an insert function, i have to find the cursor, make the array bigger to fit the new value and then insert it?

    same with remove...with that would i have to find the cursor, tell the cursor to go to a specific value, remove that value, and then make the array smaller by 1?

    the gotoNext and gotoPrior both also seem like 1 step functions...am i missing something? i mean this is a "Laboratory 3: Postlab Exercise" but it doesn't say that i should be relating this to lab 3 in any way...it just says "given a list containing n data items"

    thanks in advance
     
  5. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    It's asking you about the worst case scenario for those list operations. And, you must consider the complete operation, meaning moving the cursor/pointer to the desired element, inserting or removing, and then moving data elements to create or fill-in the gap.
     
  6. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    so am i right to assume the first 2 are O(1) and the second 2 are O(n)?
     
  7. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Well, no. Give your explainations and I'll try to point out where you went wrong.
     
  8. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    ok for the insert: worst case you will have to find the cursor, make the array larger by 1, move all the elements of the array (upto where you want to insert) forwards by one, leaving room to insert, move teh cursor to that spot, and insert. O(1) is used if it takes the same amount of time per item no matter how many items we aretrying to insert

    remove: find the cursor, move it to the data item you want to reomve, remove that item, move all the items in the array up to that one down by 1 and make the array smaller by 1. same as above where it takes the same amount of time no matter how many items we are trying to remove

    gotoNext: this just advances teh cursor and the function takes one step for each data member passed to it

    gotoPrior: this just moves the cursor back which also only takes 1 step
     
  9. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    The big-O notation is used to describe the relationship between the time it takes to perform an operation, and the size of the data set being operated on.

    For insert or remove, you're moving the cursor up to N times. You're also going to move up to N elements in the array. The total time it takes to perform an insert or remove is linearly related to the number of elements in the array, so it is O(n).

    Advancing or reversing a cursor one element is a constant time operation. The time it takes to move the cursor one element does not depend on how many elements are contained in the array, so it is O(1).
     

Share This Page