CS1103 Learning Journal Unit 3 - ADTs, Stacks, Queues and Binary Trees

CS1103 Learning Journal Unit 3 - ADTs, Stacks, Queues and Binary Trees

This week, I learned about abstract data type (ADT), stacks, queues, and binary trees. Firstly, ADT “refers to a set of possible values and a set of operations on those values, without any specification of how the values are to be represented or how the operations are to be implemented” (Eck, 2019, p. 450). In this case, “a program that only depends on the abstract definition of the ADT can use either implementation, interchangeably” (UoPeople, n.d.), which is helpful to debug and maintain. Secondly, the stack is a common abstract data type, and it has three methods: push(), pop(), and isEmpty(). We can use several ways to implement a stack, such as a linked list and an array. Thirdly, the queue is another common abstract data type, and it has three methods: enqueue(), dequeue(), and isEmpty(). A queue can also be implemented by a linked list or an array. Fourthly, “a binary tree is a tree data structure in which each node has at most two children” (UoPeople, n.d.). We can traverse a binary tree in three orders: preorder traversal, postorder traversal, and inorder traversal.

In the discussion forum, I discussed the advantages of ADTs (Abstract Data Types) for program modularity. Specifically, there are three benefits: maintainability, reusability, and readability. To better explain these advantages, I first presented the definitions of ADT and program modularity. Then, on this basis, I adopt a linked list to implement a stack and treat it as an example of ADT. Finally, I explained these concepts and advantages in detail with the codes. Through this discussion assignment, I have a deeper understanding of ADT and stack. After posting the assignment, I received some inspiring comments that motivated me to keep going and made me feel empowered and warm. I’m very grateful.

When I was evaluating the programming assignment of Lab 3 Unit 2, I found that the solution provided by our university had some errors. Specifically, in the description of Lab 3, there is a sentence:

1 2	"And a repeated optional element (represented by brackets with dots, [ xxx ]...) can be represented by a while loop" (UoPeople, nd, para. 5).

Thus, in Rule 3 below, “[ ].” means a repeated optional adjective.

1 2	<noun_phrase> ::= <proper_noun> \| <determiner> [ <adjective> ]. <common_noun> [ who <verb_phrase> ]

However, when implementing Rule 3, the standard answer directly prints the “.” after the adjective, resulting in the following output:

1	some pretty. elephant who finds Fred believes that Jane is pretty and some woman sleeps.

Obviously, having a “.” after “pretty” is unreasonable. The “.” here means that there can be multiple adjectives to modify the following nouns, which can be implemented with a while loop. The way I implemented it and the output is as follows:
Codes:

// "[ <adjective> ]." can be represented by a while loop
// The value range of randomRepeatedTimes is: [0, adjectives.length], here is [0, 4]
int randomRepeatedTimes = (int) (Math.random() * (adjectives.length + 1));
while (randomRepeatedTimes > 0) {
    System.out.print(" " + adjectives[randomRepeatedTimes - 1]);
    randomRepeatedTimes--;
}

Outputs:

1	the tiny big unicorn is bald.

As can be seen from the above output, there are two adjectives “tiny” and “big” in front of “unicorn”. It is more reasonable to use multiple adjectives than adding a “.” directly after the adjective.

I also learned something new after reading solutions for exercises unit 2. Specifically, “if N is greater than a certain value, the output of factorial(N) will exceed the limited size of values of type int, resulting in an error. A good solution is to use BigInteger values instead of int values, and this allows the program to work even for fairly large values of N” (UoPeople, n.d.). Although I learned some new things, I found that the solution provided by our university also has some minor bugs. Specifically, in the solution, when the input N is 0, the program will exit, and the corresponding code is as follows:

1
2
3

int N = TextIO.getlnInt();
    if (N == 0)
             break;

However, in this case, factorial(0) cannot be calculated. Therefore, a better approach is that when N equals -1, the program exits, so that factorial(0) can be calculated. The corresponding code is as follows:

1
2
3

int N = TextIO.getlnInt();
    if (N == -1)
             break;

Word count: 707

References

1.Eck, D. J. (2019). Introduction to Programming Using Java.
http://math.hws.edu/javanotes

2.University of the People. (n.d.). Introduction.
https://my.uopeople.edu/mod/book/view.php?id=279532&chapterid=322233

3.University of the People. (n.d.). Lab 3: Silly Sentences and Fancy Fractals.
https://my.uopeople.edu/mod/page/view.php?id=279526

4.University of the People. (n.d.). Solutions for Exercises Unit 2.
https://my.uopeople.edu/mod/page/view.php?id=279542

This is the ending, thanks for reading.