DATA STRUCTURES & ALGORITHMS

Tutorial 2 Questions
Linked List and Stack

Required Questions

Linked List

We use linked lists to represent polynomials whose coefficents are integers. For exampel,
the list in Figure 1 will represent for f0 = 6x3 + 5x2 + 8x + 3

Figure 1.
Question 1.
Draw the lists for the following expressions
a. f1 = 2x + 1
b. f2 = 2
c. f3 = 0
c. f4 = 5x4 + x2 + 1
d. f5 = f1 + 5
e . f6 =f1+ f4
e. f7 = f1*f4
f. f8 = f1*f4
f. f9 = f4\f1

Note: Operation ‘ \’ denotes our “polynomials division”, where the remainders will be
discarded and the result coffeicients will be rounded to integer values. For more
information of polynomial division, refer to
http://www.ltcconline.net/greenl/courses/152a/polyexp/polydiv.htm

For example:
(x2 +1) \ 2 = (1/2)x2+1/2 = x2+1 (coefficients rounded) ;
x4 + 3x2– 5 \ x2 + 4x = x2 - 4x + 19 (remainder discarded)

Solution:

a. f1

head 2 1

b. f2
 head 2

c. f3

head 0

d. f4

head 5 0 1 0 1

e. f5

head 2 6

f. f6

head 5 0 1 2 2

g. f7

head 10 5 2 1 2 1

h. f9

head 3 -1 2 0

Question 2.

The list is implemented as a class List.In Listing 1 is the algorithm of a method to

calculate f+k, where fisthe object calling the method and k a constant.

algorithmaddConstant (val k<int>)

1. tmp = head
2. while (tmp->next is not NULL)
1. tmp = tmp->next
3. tmp-> data = tmp->data+ k
4. return

endaddConstant
Listing 1

Develop similar algorithms for the methods of the following operations:

 a. f – k
b. f *k
c. f\ 10
d. f\ x
e. f* f2
Solution:

a) f – k
algorithmsubConstant (val k<int>)

1. tmp = head
2. while (tmp->next is not NULL)
1. tmp = tmp->next
3. tmp-> data = tmp->data- k
4. return

endsubConstant

b) f * k
algorithmmulConstant (val k<int>)

1. tmp = head
2. while (tmp is not NULL)
1. tmp-> data = tmp->data * k
2. tmp = tmp->next

3. return

endmulConstant

c) f \ 10
algorithmdiv10 ()

1. tmp = head
2. while (tmp is not NULL)
1. tmp-> data = tmp->data / 10
2. tmp = tmp->next

3. return

enddiv10
 d) f \ x
algorithmdivX ()

1. if ( head == tail)
1. head->data = 0
2. return
2. tmp = head
3. while (tmp->next != tail)
1. tmp = tmp->next
4. tmp->next =null;
5. delete tail
6. tail = tmp

enddivX

e) f * f2
algorithmaddPolynomial(val f2<list>)
1. min_size = min(this.size(),f2.size())
2. this.reverseList()
3. f2.reverseList()
4. tmp = head
5. i=0
6. while(i <min_size)
1. f2.retrieve(i,data)
2. tmp->data += data
3. tmp = tmp->next
4. i++
7. i = min_size
8. if(this.size() < f2.size()) then
1. while(i < f2.size())
1. f2.retrieve(i,data)
2. addFist(data)
3. i++
2. end while
9. end if
10. this.reverseList()
11. f2.reverseList()
12. return
endaddPolynomial

algorithmmulPolynomial(val f2<list>)

1. result_list = new list

2. i = 0
3. while(i < f2.size())
1. f2.retrieve(i,data)
2. if(data != 0) then
1. tmp_list = new list
2. tmp_list.append(this)
3. tmp_list.mulConstant(data)
4. j = i + 1
5. while(j < f2.size())
1. tmp_list.addLast(0)
 2. j++
6. result.addPolynomial(tmp_list)
3. end if
4. i++
4. returnresult_list
endmulPolynomial

Stack

Suppose that the following algorithms are implemented:

- pushStack (ref stack<Stack>, val n <data>): push the value n to the stack
stack
- popStack(ref s <Stack>, ref n <data>): remove the top element of the stack
stackand assign the data of that top element to n
- emptyStack(val s <Stack>): check whether the stack stackis empty

Question 3

Imagine we have two empty stacks of integers, s1 and s2. Draw a picture of each stack
after the following operations:

pushStack (s1, 3);

pushStack (s1, 5);
pushStack (s1, 7);
pushStack (s1, 9);
while (!emptyStack (s1)) {
popStack (s1, x);
pushStack (s2, x);
} //while
pushStack (s1, 11);
pushStack (s1, 13);
while (!emptyStack (s2)) {
popStack (s2, x);
pushStack (s1, x);
} //while

Solution:
9
7
5
3
13
11
S1 S2

Question 4
Write an algorithm for a function called removeFist that removes the first element of a
stack. The order of other elements in the stack must be the same after the removal.
algorithmremoveFirst (ref sourceStack<Stack>)
This algorithm removes the first element in the sourceStack. The
order of the remaingelements must be preserved after the removal.

Pre None
Postthe sourceStackbeing removed its first elemnt
Return None

endremoveStack

Solution:

algorithmremoveFirst (ref sourceStack<Stack>)

1. tmpStack = new Stack
2. while ( !emptyStack(sourceStack) )
1. popStack( sourceStack, x )
2. pushStack ( tmpStack , x )
3. popStack( tmpStack , x )
4. while ( !emptyStack(tmpStack) )
1. popStack( tmpStack , x )
2. pushStack (sourceStack , x)
5. return
endremoveStack

Appendix
Formal parameters and actual parameters

Simply speaking, formal parameters are those that are declared in algorithms/functions
prototypes, meanwhile actual parameters are those that are passed when the
algorithms/function are actually invoked.

Example 1.Let’s consider the following piece of pseudo code

algorithmsearch( valn <datatype>)

Return position of the list element whose data is equal to n
…
end search
…
//in another algorithm
…
p = Search(number)
…

In this example, the algorithm search takes a formal parameter named n and returns the
position of the list element whose data is equal to n. Later then, in another example
algorithm, search is invoked with the actual parameter number.

Notation of parameter passing

When developing algorithms, we adopt the following notations regarding mechanisms of
parameter passing:

- ref: parameters are passed by reference. When passed by reference, the actual
parameter is a reference of the formal parameter. In other (and simpler) words,
any value change that occurs in the formal parameter will also apply
immediately on the actual parameter.
- val: parameters are passed by value. When the function is invoked, the value
of actual parameter will be copied to that of the formal parameter. Since then,
any change on formal parameters will not affect the actual parameters and
vice versa.

Example 2.Let’s consider the following piece of pseudo code representing a method in
the class List implementing a linked list

algorithmcountPositive(val n <int>)
This algorithm counts thenumber of elements whose data are positive
numbers (incorrect version).
Pre None
Postn holdsthenumber of elements whose data are positive numbers

1. count = 0
2. pTemp = head;
3. loop (pTemp!=NULL)
1. if(pTemp->data > 0) then
1. count++
2. end if
3. pTemp = pTemp->link
4. end loop
5. n = count

endcountPositive

As easily observed, this method intends to use the parameter n to return the positive data
counted. However, since n is passed by value, the value cannot be passed properly to the
actual parameters when countPositive is called.

One way to correct the method is to take away the parameter and directly return the result
as follows.

algorithmcountPositive()
This algorithm counts thenumber of elements whose data are positive
numbers
Pre None
Post None
Return the number of positive elements

1. count = 0
2. pTemp = head;
3. loop (pTemp!=NULL)
1. if(pTemp->data > 0) then
1. count++
2. end if
3. pTemp = pTemp->link
4. end loop
5. returncount

endcountPositive

Alternatively, we can use the passing by reference mechanism to correct the method as
follows

algorithmcountPositive(ref n<int>)
This algorithm counts thenumber of elements whose data are positive
numbers.
Pre None
Postn holdsthenumber of elements whose data are positive numbers

1. count = 0
2. pTemp = head;
3. loop (pTemp!=NULL)
1. if(pTemp->data > 0) then
1. count++
2. end if
3. pTemp = pTemp->link
4. end loop
5. n = count
endcountPositive

Method and global function

In Example 2, we are in the situation of developing a method for the class List, thus we
can assume that we can access the (private) internal member head of the class. However,
in some case, you may be requested to write a global function, or function for short,
which is generally unable to access internal members of the class. In that case, your
algorithm should avoid touching any class properties and instead call the suitable method.

Example 3.Write a function that counts in a list the number of elements whose data are
positive numbers

algorithmcountPositive(ref list <Linked List>, ref n <int>)

This algorithm counts thenumber of elements whose data are positive
numbers
Pre None
Postn holdsthenumber of elements whose data are positive numbers

1. count = 0
2. i = 0
3. loop (i <list.size())
1. list.retrieve(i, data)
2. if (data > 0) then
1. count++
3. end if
4. i++
4. endloop
5. n = count
endcountPositive

In this example, we assume that the class List has already been implemented with
methods size(), which returns the number of elements in the list, and
retrieve(valpos<int>, ref dataOut<data>), which retrieves the data field of the element
at the position pos in the list and assigns that data to the dataOut parameter.

-- End --