Array list: number: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(8 intermediate revisions by one other user not shown)
Line 1: Line 1:
'''Algorithmic problem:''' [[Linear sequence: number]]
[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=uYTck0kDvl4|500|right||frame}}
'''Algorithmic problem:''' [[Ordered sequence#Number|Ordered sequence: number]]


'''Prerequisites:'''
'''Prerequisites:'''
Line 15: Line 17:


# The pointer <math>p</math> points to the array list item at position <math>i+1</math> (or is void if there is no such item).
# The pointer <math>p</math> points to the array list item at position <math>i+1</math> (or is void if there is no such item).
#The value of is the sum of the values n of all array list items at positions <math>1,...,i</math>.
#The value of <math>c</math> is the sum of the values n of all array list items at positions <math>1,...,i</math>.


'''Variant:''' <math>p</math> is moved one step forward so as to point to the next array list item.
'''Variant:''' <math>p</math> is moved one step forward so as to point to the next array list item.
'''Break condition:''' It is <math>p=</math> void.
'''Break condition:''' It is <math>p=</math> void.


Line 26: Line 29:
'''Implementation:'''
'''Implementation:'''


# Set <math>p:=first</math>.
# Set <math>p:=</math>first.
# Set <math>c:=0</math>.
# Set <math>c:=0</math>.


Line 36: Line 39:


'''Implementation:'''
'''Implementation:'''
# If void, terminate the algorithm and return the value of <math>c</math>.
# If <math>p=</math>void, terminate the algorithm and return the value of <math>c</math>.
# Otherwise:
# Otherwise:
## Set <math>c:=c+p</math>.n.
## Set <math>c:=c+p</math>.n.
Line 45: Line 48:
==Complexity==
==Complexity==


'''Statement:''' Linear in the length of the sequence in the worst case (for a fixed value of ).
'''Statement:''' Linear in the length of the sequence in the worst case (if the arrays of all array list items have identical lengths).


'''Proof:''' Obvious.
'''Proof:''' Obvious.


==Further information==
==Further information==

Latest revision as of 23:10, 19 June 2015

Algorithmic problem: Ordered sequence: number

Prerequisites:

Type of algorithm: loop

Auxiliary data:

  1. A pointer [math]\displaystyle{ p }[/math] of type "pointer to array list item of type [math]\displaystyle{ K }[/math]".
  2. A counter [math]\displaystyle{ c \in \mathbb{N}_0 }[/math].

Abstract view

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

  1. The pointer [math]\displaystyle{ p }[/math] points to the array list item at position [math]\displaystyle{ i+1 }[/math] (or is void if there is no such item).
  2. The value of [math]\displaystyle{ c }[/math] is the sum of the values n of all array list items at positions [math]\displaystyle{ 1,...,i }[/math].

Variant: [math]\displaystyle{ p }[/math] is moved one step forward so as to point to the next array list item.

Break condition: It is [math]\displaystyle{ p= }[/math] void.

Induction basis

Abstract view: Initialize [math]\displaystyle{ p }[/math] so as to point to the first array list item.

Implementation:

  1. Set [math]\displaystyle{ p:= }[/math]first.
  2. Set [math]\displaystyle{ c:=0 }[/math].

Proof: Nothing to show.

Induction step

Abstract view: Add the number of elements in the current array and then go forward.

Implementation:

  1. If [math]\displaystyle{ p= }[/math]void, terminate the algorithm and return the value of [math]\displaystyle{ c }[/math].
  2. Otherwise:
    1. Set [math]\displaystyle{ c:=c+p }[/math].n.
    2. Set [math]\displaystyle{ p:=p }[/math].next.

Correctness: Nothing to show.

Complexity

Statement: Linear in the length of the sequence in the worst case (if the arrays of all array list items have identical lengths).

Proof: Obvious.

Further information