Skip to content

JA5. Learning Journal 5

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 5th week of this course; it was all about dynamic programming. I started materials assigned in the learning guide, then I did the discussion assignment which was about comparing the dynamic programming and brute force approaches for solving the knapsack problem. I also did the programming assignment which was about implementing the knapsack problem using dynamic programming.

2. Describe your reactions to what you did

I was excited to dive more into dynamic programming and its applications. I found the knapsack problem to be an interesting problem to solve, but its dynamic programming approach was difficult to understand and implement. I found it hard to come up with the recursive formula for the problem, but I accepted it as is in the textbook (Hristakeva & Shrestha, 2005).

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

The feedback on my discussion assignment were particularly positive. I represented each of the two approaches (brute force and dynamic programming) in a table format the summarizes necessary computations.

Looking at the generated tables, we can see that the dynamic approach’s table is less dense in space, and computation simply relies on checking the previous cell; hence, it is preferred over the brute force approach as the problem size becomes large enough.

4. Describe your feelings and attitudes

I felt tired as the size of workload was really huge this week with other courses also being also heavy. However, I liked that both the reading and programming assignments talked about the same topic; despite the topic being complex, I think this helps students to understand that topic better.

5. Describe what you learned

We learned about various patterns of algorithms including greedy algorithms, dynamic programming, and randomized and divide-and-concur algorithms. Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.

Randomized algorithms are a form of bounded rationality, where we make decisions that are as rational as possible, but there are options, factors, or considerations that we leave up to chance. Divide and conquer gains efficiency by breaking a large problem into subsequently smaller problems until those small problems can be easily solved and then combined together to get a solution for the larger problem.

Dynamic programming is an optimization technique that is applicable to problems that can be divided into overlapping subproblems. The results of the repeated subproblems are stored and reused rather than recomputed. The sub-problems are ordered from the easiest to solve to the hardest.

Skip lists are a form of randomized algorithms that are used to implement a data structure that allows for fast search, insert, and delete operations. A skip list is an advanced form of a linked list that holds many layers of pointers to the next node in the list, with the number of pointers decreasing as you move down the list (Shaffer, 2011).

6. What surprised me or caused me to wonder?

The concept of the skip list data structure seemed particularly smart. By adding a few more layers of increasing distance pointers to the linked list; we can achieve greater performance in operations on the list if we can guarantee a cheap sorting (after insertion) and some randomness in the distribution of the pointers in the layers.

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

The knapsack problem using the dynamic programming approach was particularly challenging. It was much easier to understand the brute force approach, but the dynamic programming approach was difficult to understand and implement. I accepted it as is in the textbook (Hristakeva & Shrestha, 2005). I did not the basis of choosing the previous cell to copy the value from when there is not need to recompute the value of the current cell; here is the formula I used to fill the table:

n = 4 # number of items
c = 10 # capacity of the knapsack
weights = [0, 2, 3, 5, 6]
values = [0, 6, 5, 4, 3]
table = [[0 for _ in range(c+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, c+1):
        if weights[i] > j:
            table[i][j] = table[i-1][j]
        else:
            table[i][j] = max(table[i-1][j], table[i-1][j-weights[i]] + values[i])

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

I am gaining a better understanding of dynamic programming and its applications. I heard this topic a lot in the past few years, in some podcasts or blogs; I thought it was more related to functional programming and it is done automatically by the compiler at the lower levels. However, I found it to be a manual process that requires a lot of thinking and understanding of the problem and can be done using normal procedural languages.

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

I am realizing that I tend to complicate things while programming. I think this is normal when you are tackling a new topic or a new problem; you tend to overthink and over-complicate things. I also think that simple code requires more energy and time than complex one; I will try to keep things simple and straightforward in the future.

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

There are so many applications for dynamic programming in software engineering. For example, finding the shortest path in a graph, finding the longest common subsequence between two strings, and finding the longest increasing subsequence in an array. All these can be modeled as dynamic programming problems and solved using the techniques we learned this week.

References