CST370 Week 3

    This week I studied a lot more about recursion and search algorithms in order to understand the homework better. 

    We learned about brute force algorithms like exhaustive search, which is useful in finding all permutations of a set. Exhaustive search goes through each possible case and then identifies which of these cases is either most efficient or solves the problem. The time complexity for exhaustive search is dependent on the number of permutations it has [ (n - 1)! ].

    There are two graph traversal algorithms: depth-first search (DFS) and breadth-first search (BFS). 

    DFS makes use of a stack and a mark array to determine what nodes have been visited, and creates a tree with tree edges. Time efficiency for DFS is dependent on the sum of the number of vertices and edges it has: 𝚯 (|v| + |e|).

    BFS makes use of a queue and a mark array to determine what nodes have been visited, and can create a tree for the shortest path from the initial node (a "wider" tree). Time efficiency for BFS is dependent on the number of vertices it has, squared: 𝚯 (|v|²).

    Both can be used for checking connectivity and acyclicity of a graph. DFS is best for determining if a path exists to a node, and BFS is best to find shortest paths from the initial node. I used DFS for backtracking in the homework to check if input edges created a connected graph.

    

    Divide and conquer is a common problem-solving technique where a problem is divided recursively into subproblems, until a subproblem is solvable. Then, merge all of the solved subproblems to obtain the solution or solution set. One example is a binary search. To get the time efficiency for a divide and conquer algorithm, we use the Master Theorem. 

    An algorithm can result in one of three of the following time complexities, where a = number of recursive calls, b = factor that reduces input size (like divide by b=2), and d = time to divide the problem or combine solutions in 𝚯 (n)^d. Master Theorem can also be used to solve recurrence relations T(n) = aT(n/b) + f(n) where  f(n) ∈ 𝚯(n)^d  and d ≥ 0.

    This video helped me understand subsets way better. Since the video makes use of bit manipulation, it made me realize that in order to get the ordering right, I needed to reverse the set first and then search. After finding the suitable subsets, I had to then resort this subset and then push it back to a complete set for printing. I already posted a different article in the Slack channel, so I did not want to take away any potential participation from others.

Isopod Update: There are more orange springtails!