Skip to content

JA4. Learning Journal 4

The Learning Journal is a tool for self-reflection on the learning process. In addition to completing directed tasks, you should use the Learning Journal to document your activities, record problems you may have encountered and to draft answers for Discussion Forums and Assignments. The Learning Journal should be updated regularly (on a weekly basis), as the learning journals will be assessed by your instructor as part of your Final Grade.

Answer the following questions in your Learning Journal

1. Describe what you did. You need to describe what you did and how you did it

This was the 4th week of this course; it was all about graphs, graph traversals, and minimum-cost spanning trees. I started materials assigned in the learning guide, then I did the discussion assignment which was about Kruskal’s algorithm. I also did the programming assignment which was about implementing Prim’s algorithm to determine the minimum spanning tree of a graph.

2. Describe your reactions to what you did

I was excited to dive more into graphs and their properties. I found the minimum-cost spanning tree as a concept to be an interesting problem to solve. However, I found Kruskal and Prim algorithms to be difficult to understand and implement; I found them explained differently in various places and are not clear to me yet.

3. Describe any feedback you received or any specific interactions you had. Discuss how they were helpful

The discussion assignment on Kruskal’s algorithm was interesting. I found some of my colleagues’ explanations to be clear and easy to understand. however, I think the question was a bit vague and open-ended, which made it difficult to compare the answers, and to grade them.

4. Describe your feelings and attitudes

The size of the reading material was a bit overwhelming. I found it hard to understand the algorithms and their implementations. I spent more than 12 hours on the programming assignment alone, and I still don’t understand the topic well. I am a bit worried about the upcoming quizzes and exams.

5. Describe what you learned

A minimum spanning tree (MST) is a spanning tree of a graph with the smallest possible weight among all spanning trees. There may be multiple MSTs for a graph, if placing edges in a different order results in the same weight (Dekai, 2005).

MSTs have many applications, such as computing the shortest set of wires needed to connect a set devices, traveling salesman, and problems of similar nature. There are two common algorithms to find the MST of a graph: Prim’s algorithm and Kruskal’s algorithm. Both are greedy algorithms but they differ in the way they select the next edge to add to the MST (Shaffer, 2011).

Kruskal’s algorithm is a greedy algorithm that grows a collection of trees (a forest) until the forest merges into a single tree. In other words, it starts by dividing the graph into a forest of |V| trees of single vertex each (V is the number of vertices in the graph). Then, it repeatedly selects the cheapest edge that does not create a cycle in the forest and adds it to the MST, slowly merging those trees into a single MST (Shaffer, 2011).

Prim’s algorithm, on the other hand, starts with a single vertex and grows the MST by adding the least-cost edge connected to the current MST. It is a greedy algorithm that starts from any vertex and starts a BFS-like traversal on all vertices connected to the current MST; it maintains those connected vertices in a priority queue and selects the least-cost edge to append to the MST (Shaffer, 2011).

6. What surprised me or caused me to wonder?

The difference between the theory and the implementation of the Kruskal and Prim algorithms was surprising. I found the theory to be clear and easy to understand, despite it being vastly different from source to source. However, the implementation was way more difficult and required a lot of time to understand.

7. What happened that felt particularly challenging? Why was it challenging to me?

The programming assignment was particularly challenging. I found it hard to implement the Prim algorithm to determine the minimum spanning tree of a graph. I spent more than 12 hours on the assignment and I still don’t have a formal way to verify that it my implementation works.

I implemented all auxiliary classes and methods on my own and did not use built-in classes which is a good learning opportunity. However, I found it hard to debug and test the implementation as I am not familiar with the Java environment so that added an extra layer of complexity to the assignment.

8. What skills and knowledge do I recognize that I am gaining?

I am gaining a better understanding of graphs and their properties, the search strategies, and how to apply them in different contexts. Brute force, divide and conquer, and now greedy algorithms are all good skills to be under your belt to solve day-to-day software engineering problems.

Building everything from scratch is also a good learning opportunity; however, I found my implementation to be different from the standard ones; for example MyPriorityQueue class is different from the standard PriorityQueue class in Java in terms of function names and internal implementation, which may be due to my class is not 100% correct; but it works for the assignment.

9. What am I realizing about myself as a learner?

I learned how to implement a graph data structure, how to implement a priority queue, and how to implement the Prim algorithm to determine the minimum spanning tree of a graph. However, I had no way to officially verify their correctness. I am realizing that I lean more towards test driven development TDD and I like to build my own tests before implementing the actual code.

10. In what ways am I able to apply the ideas and concepts gained to my own experience?

There are so many applications for graphs and graph algorithms in software engineering. For example, selecting the best recommended product, optimizing friends suggestions, and even finding the best value for money in a basket of products. All these can be modeled as graphs and solved using the techniques we learned this week.

References