Portal   Forum   Members   Market   Gallery   Events

ok programming guys

Discussion in 'Help Forum' started by Jakeman, Sep 29, 2003.

  1. Jakeman

    Jakeman MSC Founder and Donator

    Joined:
    Feb 26, 2000
    Messages:
    25,758
    Likes Received:
    27
    Market Rating:
    16
    Two question I missed on a recent exam. I disagree with what my teacher says is the correct answer. What do you guys think?

    7. (10 pts) In algorithm analysis it is important to establish:

    a) an exact formula for time requirement as a function of problem size.
    b) a measure of growth of the time requirement as a function of problem size.
    c) a measure of growth of the time requirement as a function of code size.
    d) All of the above.
    e) Just a) and c)

    Correct answer = b
    My answer = a

    My argument: The exact formula is a measure. And if we are arguing importance, the exact formula is needed to come up with the measure, presumably the Big O, of the algorithm.

    13. (10 pts) Traversing and printing data in a linked list involves N + 1 assignments and N print operations. Thus the algorithm is of order O(f(n)) where f(n) is

    a) N + 1.
    b) 2*N +1.
    c) N.
    d) All of the above.
    e) None of the above.

    Correct answer = d
    My answer = c

    My argument: First, Big O only cares about the most significant term of the function. Second, if 2*N + 1 is the exact formula and N is the most significant term (both answers being at least somewhat correct in that respect), how is N + 1 correct since it is only a piece of the function?
     
    Last edited: Sep 29, 2003
  2. Gilgamesh

    Gilgamesh MSC Footman

    Joined:
    Jun 17, 2000
    Messages:
    1,759
    Likes Received:
    9
    Market Rating:
    0
    <whoosh>

    thats the sound of this question going right over my damn head..... Thanks Jake for making me feel really stupid.. :)
     
  3. Jakeman

    Jakeman MSC Founder and Donator

    Joined:
    Feb 26, 2000
    Messages:
    25,758
    Likes Received:
    27
    Market Rating:
    16
    the class is CS 3100, Data Structures and Algorithms (programming 3)

    i'm finding it hard to get anyone to validate or invalidate my position. Everyone in my class feels the same way about these questions, but no one will step forward... pussies. I guess I will go it alone when I go to the student union.
     
  4. Wulf

    Wulf MSC Knight and Donator

    Joined:
    Jul 19, 2000
    Messages:
    4,856
    Likes Received:
    10
    Market Rating:
    0
    hmmm... I'm in a data structures class... I guess I should know this stuff :p
     
  5. Jakeman

    Jakeman MSC Founder and Donator

    Joined:
    Feb 26, 2000
    Messages:
    25,758
    Likes Received:
    27
    Market Rating:
    16
    I think programming 2 is also called "data structures." Are you in 2 or 3? I think most programming 2 classes don't get into Big O and algorithm analysis very deep.
     
  6. Wulf

    Wulf MSC Knight and Donator

    Joined:
    Jul 19, 2000
    Messages:
    4,856
    Likes Received:
    10
    Market Rating:
    0
    Well yeah it wasn't very indepth about that... We covered both of those topics and more in one class period.
     
  7. Elbereth

    Elbereth MSC Commander and Donator

    Joined:
    Jun 17, 2000
    Messages:
    3,356
    Likes Received:
    14
    Market Rating:
    0
    Note: I haven't taken a programming class since HS in 1986...

    I have always used algorithms as a general plan rather than a specific set of formulas/equations/code. Maybe your instructor is just being picky about the definition including "exact formula"?
     
  8. harleyb

    harleyb Peasant

    Joined:
    Aug 12, 2002
    Messages:
    866
    Likes Received:
    9
    Market Rating:
    0
    what'd you get on the exam, jakeo?
     
  9. Jakeman

    Jakeman MSC Founder and Donator

    Joined:
    Feb 26, 2000
    Messages:
    25,758
    Likes Received:
    27
    Market Rating:
    16
    80%. With these two questions I would have 94%.
     

Hitometer: 53,846,912 since 1995