Week 3

This week focused on the practical implementation of graph algorithms, specifically Depth-First Search (DFS) and the Traveling Salesman Problem (TSP) using exhaustive search. Applying these concepts through programming has highlighted both the elegance of recursive structures and the significant computational challenges associated with NP-hard problems.

Key Concepts & Implementations

- DFS & Systematic Traversal: Implementing DFS for directed graphs reinforced the importance of using a "mark array" to track visitation sequences. A crucial takeaway was ensuring the algorithm follows a numerical ascending order for adjacent vertices to maintain consistency in the output.

- TSP & Exhaustive Search: Tackling the Traveling Salesman Problem required using permutations of vertices to find the optimal Hamiltonian cycle. While effective for a small number of vertices (under 15), this approach clearly demonstrates how quickly the search space grows as more nodes are added.

- Edge Cases in Directed Graphs: A significant portion of the logic involved handling "no-path" scenarios, where a program must return a cost of -1 if a complete cycle back to the starting vertex is impossible.

Current Reflections & Challenges

What is clear: The use of an implicit stack via recursion makes DFS relatively straightforward to implement. I now feel confident in my ability to represent directed graphs using both adjacency lists (for DFS) and adjacency matrices (for TSP weight tracking).

 

What is challenging: The Traveling Salesman Problem is where I find the most conceptual friction. While generating permutations works for this assignment's constraint of <= 15 vertices, I am curious about the transition to more efficient heuristic methods. The current "Brute Force" method is easy to grasp but feels incredibly "heavy" to execute.

 

Questions I'm Pondering:

  1. Scaling: At what exact vertex count does the $O(n!)$ complexity of permutations typically become completely unfeasible for a modern standard CPU?

  2. Disconnected Components: Although the DFS assignment allowed us to assume a connected graph, how would the mark array logic shift if we had to handle multiple disconnected components in a directed graph

Comments

Post a Comment

Popular posts from this blog

Week 4

  Week 4 Learning Journal: Merge Sort, The Master Theorem, and Midterm Synthesis Technical Summary: Week 4 was a pivotal point in CST 370 as we transitioned from basic brute-force techniques to the Divide-and-Conquer paradigm. The primary focus was Merge Sort , a sophisticated sorting algorithm that employs a recursive strategy to achieve $O(n \log n)$ efficiency. The logic involves two distinct phases: the "Divide" phase, where the array is split into $n$ sub-lists (each containing one element), and the "Merge" phase, where those sub-lists are repeatedly merged to produce new sorted sub-lists until only one remains. A major highlight of this week was applying the Master Theorem to analyze algorithm efficiency. The Master Theorem provides a mechanical way to solve recurrence relations of the form T(n) = aT(n/b) + f(n) . For Merge Sort, the relation is T(n) = 2T(n/2) + \Theta(n) . Since the work done at each level of the recursion ( f(n) ) matches the cost of the...
Read more

Week 2

Weekly Learning Journal: Algorithm Analysis & Recursion This week, my study focused on the Algorithm Analysis Framework , specifically the formal application of asymptotic notations ( $O$ , $\Omega$ , and $\Theta$ ). While I previously had a surface-level understanding of Big-O, this module challenged me to define the tight bounds of an algorithm's efficiency using Big-Theta. I learned that while Big-O provides a worst-case "ceiling," Big-Theta is often more useful for describing the actual growth rate of non-recursive loops, such as those found in standard sorting or searching algorithms. A significant portion of my time was dedicated to the analysis of recursive algorithms . This was a step up in complexity from non-recursive analysis because it requires setting up a recurrence relation . I practiced the backward substitution method , which involves expanding the recursive calls until a pattern emerges that can be expressed as a summation. For example, seeing how a...
Read more

Week 1

  Week 1 Learning Journal Entry Module: Introduction to Algorithms and Fundamental Data Structures Date: January 13, 2026 This week, I focused on the formal definition of algorithms and the various ways to measure their efficiency. I studied Euclid’s algorithm for finding the Greatest Common Divisor (GCD) and compared it to the consecutive integer checking algorithm, noting how algorithm choice significantly impacts performance. I also reviewed fundamental data structures, specifically focusing on graph representations (adjacency matrices vs. adjacency lists) and how they differ for weighted and unweighted graphs. Implementing the Palindrome puzzle was a great exercise in string manipulation; it taught me how to effectively use the two-pointer technique and the importance of data preprocessing, such as filtering non-alphanumeric characters and normalizing case to ensure logical correctness. Finally, the "Fake Coin" and "Mislabeled Baskets" puzzles served as a s...
Read more