CST370 - Week 3

 

CST370-30_2252: Design & Analysis of Algorithms – Week 3

This is the third week; we continue reviewing various problem-solving techniques. The last module introduced brute force as a direct “just do it” solving the problem. The example of Brute-Force String Matching analysis is based on the text of the string and the pattern of comparison. In a best-case scenario, a direct match is found at the start of the string. The algorithm is simple as we compare the first character of the pattern for a match or shift the pattern one character to the right if there is no match. The worst case requires comparing all the pattern characters for every shift m * (n – m +1) where m characters are in the pattern and n are in the text.

The following exhaustive search-combinatorial problems are new to me, except for the optima route. We reviewed three brute-force approaches with different strategies and time complexity. First is the traveling salesman problem or TSP; it is represented by a directed weighted graph. The idea of TSP is to find the optimal route between vertices among all of the possibilities. The second problem is the Knapsack, which searches for the maximum value of a subset of items with total weight that does not exceed a certain capacity. The subsets generated are for n elements to return Ω (for its algorithm analysis. The third is the assignment problem that assigns one job from n jobs to each person in n persons with the minimum cost possible.

Further, the module introduces depth-first search (DFS) and breadth-first search (BFS) as graph problems. These are fascinating algorithms and powerful graph traversal. However, I still need to do more research to understand their practical applications. There are a few helpful exercises in the textbook to practice the DFS traversal and represent solutions in tree edges. The breadth-first search BFS traversal is different, and it uses a queue instead of the stack used in the DFS. In this case, all adjacent vertices to the starting vertex must be visited first.

The module ends with an introduction to the divide-and-conquer algorithm design. The idea behind this technique is to break down the main problem into small sub-problems until they are small enough to solve directly. The subproblems are solved recursively, then added, and so on until the entire divided problem is resolved. The time efficiency of the divide-and-conquer algorithm is calculated using the Master Theorem.

 

CST370 - Week 2

 

CST370-30_2252: Design & Analysis of Algorithms – Week 2

The second week of this course introduces the asymptotic notations that rank the order of growth. The framework analysis for ranking the orders has three notations: big oh (O), big omega (ꭥ), and big theta(Ꝋ). I found the informal definitions of the notations helpful in understanding their differences. For example, the definition of the big O used the function g(n) as the upper bound of all functions with the same order of growth or lower. On the other hand, ꭥ(g(n)) is for all functions with the same order of growth or higher, and Ꝋ(g(n)) is for all functions with the exact same order of growth.

The formal mathematical definition of the three asymptotic notations asserts the informal definitions. If t(n) is in O(g(n)) if t (n) ≤ cg(n) for Ɐ n ≥ no, and Ǝ c is a positive constant and no is a non-negative number. Similarly, if t(n) is in ꭥ(g(n)) if t(n) ≥ cg(n) for Ɐ n ≥ no, and Ǝ c is a positive constant and no is a non-negative number. The t(n) is in Ꝋ(g(n)) if c2g(n) ≤ t (n) ≤ c1g(n) for Ɐ n ≥ no, and Ǝ c1 and c2 are a positive constant and no is a non-negative number.

We have reviewed the analysis of non-recursive algorithms for simple n × n matrices multiplication with three nested loops. The order of growth was calculated by the triple sum of unchanged variable loops, yielding growth order. The second example highlighted the loop’s variable changes for an algorithm that finds the number of binary representations in a positive number. The halved value of the n in each iteration returns a growth order of.

For the analysis of the recursive algorithm, we evaluated the example of the first n cubes and the tower of Hanoi puzzle using backward substitution. The method uses an initial condition and a general form of the basic operation to reach a result by induction.

The module ends with an introduction to the brute-force method. The approach of this strategy is to solve the problem directly. The textbook illustrates the solution for an exponential calculation of a raised to the power of n, representing the solution as the multiplication of a repeated n times. While the brute-force approach can be inefficient, it is widely used in solving important problems like sorting and searching. The two applications provided were bubble sort and selection sort. Using a brute-force strategy could lead to improvements after the first version of the algorithm. However, a bubble sort, for instance, will remain big theta(n²) in its time complexity. That concludes this module, and I look forward to the next one.

 

CST370 - Week 1

 

CST370 - Design & Analysis of Algorithms

We are back from winter break and almost halfway into the program. I had the chance to rest and take care of some personal business.

The first module of this class is a review of discrete math and an introduction to Algorithms. Each lecture this week provides an example of a challenging puzzle and a strategy to solve the problem at hand. Each problem is presented with sets of input requiring specific outcomes. The idea here is to find the steps or instructions that satisfy the desired result. To calculate the Greatest Common Divisor (GCD) of two positive integers, we followed Euclid’s Algorithms by applying the following equation till the second number is zero.

gcd(m, n) = gcd(n, m mod n)

By definition, all steps of an algorithm must be unambiguous to provide a clear path to the solution. Pseudocode is used as a method to describe algorithms represented by selected notations.

The class covers several types of problems such as sorting, searching, geometric, and numerical. It is worth noting that I have learned from previous courses that sorting plays a vital role in efficiency, especially for searching large data structures. Additionally, a Graph is one type of problem that represents scenarios and applications like networks, delivery paths, navigation, and project management. A graph is mathematically expressed by two sets of vertices V and directed or undirected edges E (i.e., V = {a, b, c, d}, E = {(a, b), (b, c), (c, d), (d, a)}). The adjacency matrix and adjacency list are used to represent unweighted and weighted graphs.

Moreover, we touched on the fundamental data structure trees as a connected graph. Trees are structured to optimize search and sort data efficiently. BST or Binary Search Trees are useful for querying data efficiently and solving various computational problems.

The module introduces an analysis of algorithms represented by order of growth. We learned the eight categories to identify the efficiency of algorithms. The textbook refers to an analytical framework primarily focused on analyzing the time complexity of algorithms. The measuring unit of time relies on the basic operation, which is determined by the most time-consuming operation to the running time. In other words, we count how many times a basic operation ran for input n.

Finally, I have submitted the work of two simple programs written in Java and am waiting for any feedback on them. So far, is an excellent week, and I am excited to return to the usual routine.