Week 3

 Week 3 (1/21-1/27)

This week's content was very interesting to me. Brute Force, TSP, Knapsack, Divide & Conquer, Master Theorem, and Depth-First Search and Breadth-First Search Algorithms were the main concepts for this week. I personally found DFS and BFS the most interesting ones, not just because of the development of their graphs but also because of the logic behind them and their functionality in different situations. DFS plans to go deep in a node (vertices) and backtracks when it gets stuck. Meanwhile, BFS plans to identify each neighbor's node first before moving on. TSP and Master Theorem were both easy to understand for me because it is very clear the time efficiency for them, especially in real world's cases. 

I am actually looking forward to next week's content and apply these algorithms in more advanced settings.

Week 2

 Week 2 ( 1/14-1/20)

This week's content was very math-oriented. Out of all topics, recursive and nonrecursive algorithms, use cases of Theta notation, recurrence relation, and backward substitution, and brute force algorithm, the topic I had the most trouble with was backward substitution. It is good practice to look at different examples to see this algorithm from different perspectives. I attended office hours, which helped me quite a lot. I compare this algorithm to proof by induction in math classes, showing the steps to identify a pattern that eventually leads to the general formula or equation needed to understand the recurrence relation and the initial condition. Below is the example I was having trouble with, along with how each step helped me identify the general number i.

M(n) = M(n-1) + 2 // recurrence relation

As an initial condition, we know that if the input number n is 1, there is no multiplication. We can express it as follows.

M(1) = 0 // initial condition

We can solve the recurrence relation using the backward substitution as below

M(n) = M(n-1) + 2 // replace “M(n-1)” with “M(n-2) +2”

                   = [M(n-2) + 2] + 2

        = M(n-2) + 2 + 2 // replace “M(n-2)” with “M(n-3) +2”

        = [M(n-3) + 2] + 2 + 2

        = M(n-3) + 2 + 2 + 2

…

        = M(n-i) +2*i // For a general number i, we will get this.

...

        = M(1) + 2*(n-1) // Note that the initial condition M(1) = 0.

        = 0 + 2*(n-1)

        = 2*(n -1) (n)

Week 1

 Week 1: Algorithms

This week, I learned pseudocode, GCD, graphs, trees, and the algorithm analysis framework. The book has been a great resource for understanding the content before watching the lectures. What I had the most trouble with was the basic operation. I thought the basic operation was only one: the most used operation in an innermost loop to measure the efficiency of the algorithm, but then I learned that there is not only one basic operation. Sometimes, there are a few operations that depend on each other in the same innermost loop, and together they determine the performance needed for the loop to execute its full cycle.

As an example, from the algorithm analysis framework, the pseudocode Display_2D_Stars:

1. Algorithm Display_2D_Stars (n)

2. // Input: A positive integer number n

3. // Output: Display the * symbol in two dimensions.

4. i ← 0             

5. while ( i < n ) do

6.     j ← 0

7.     while ( j < n ) do

8.         write '*'  

9.         j ← j + 1

10.     write '\n'

11.     i ← i + 1    

12. return 0

Lines 7, 8, and 9 are part of the same innermost loop; lines 8 and 9 depend on the execution of line 7 (the execution difference is small compared to the < operation ). Therefore, all operations on lines 7, 8 and 9: <, write and +) are part of the basic operations.