CST462S - Final Week

Service Learning Journal Reflections

This marks the final week of our Service Learning experience. Our team successfully completed the final presentation for our MVP and is now awaiting feedback from the professor. Throughout this journey, the Service Learning lectures provided essential knowledge about entrepreneurship and clearly explained key terms we used during the entire process.

Joining Track 2 was definitely the right choice for me. The course facilitated an opportunity to explore the alternative energy industry and engage with real stakeholders and beneficiaries to solve real-world problems. The most impactful part of the experience was the weekly lectures and how the learned materials are applied to the service learning activities in the same week. Modules offered a wealth of context and helped us draw strong connections between what we learned in class and how we applied it during interviews and research.

The biggest challenge I faced was securing interviews with stakeholders and beneficiaries. At first, it was a bit discouraging, especially with all the research involved. But once the team began to understand the MVP more clearly, the team gained momentum and things started to fall into place. We also opened a communication channel with our service learning site supervisor, which led to additional support and valuable mentorship.

Advice for Future SL Students

To future Service Learning students—especially those doing team-based research—use your time wisely and take full advantage of all available resources. In addition to the mandatory class presentations, our team scheduled one or two sessions each week to brainstorm and work on assignments together. I highly recommend creating a clear learning strategy and weekly schedule from the beginning. Read the syllabus carefully to understand the course learning outcomes and try to actively connect those goals with the work you are doing in your service project. Good luck all!

CST370 - Week 7

 

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

In this module, we discuss the non-comparing sorting techniques, Counting sort, and Radix sort. In the counting sort, we use a range of values to calculate the frequency of the values, and then the sum of these frequencies is used to present the distribution. In the Radix, numbers are sorted by applying the counting sort for each digit, starting with the least significant digit. Unlike counting sort, Radix does not require a range of values and runs for the number of digits with time efficiency equal to O(d*(n + k)), where d is the number of digits.

Additionally, the lecture explored the use case of Dynamic programming as a design approach to solve problems with overlapping subproblems. For example, an algorithm that implements a solution to calculate the Fibonacci numbers uses a recursive function to repeatedly call functions for calculation. Applying dynamic programming to store the results from previously called functions in an array to avoid resolving a problem that has already been resolved once.

The coin collection problem is an example of an applied dynamic programming strategy to find an optimal path. The problem is modeled by a robot path with restricted movement to the right or down over a board of cells m x n. The solution highlights the principle of optimality for an algorithm that maximizes the collection of coins in a restricted path. Furthermore, we reviewed the coin-row problem, which calculates the maximum values of coins collected in a row. The constraint of this problem is that we are not allowed to pick up two adjacent coins.

Warshall’s algorithm provides a method of the traverse that determines the reachability of a i^th vertex from the j^th vertex, forming a transitive closure matrix of the digraph. The main idea of the algorithm is to obtain information on the existing path from the row i^th  vertex vi to the j^th vertex v_j, We use a matrix R(k) and immediate predecessor R(k−1) to mark the value 1 for exiting path. Similarly, Floyd’s algorithm for all-pairs shortest paths problem utilizes the same approach as Warshall’s. We can calculate the distance for n vertices in the nxn adjacency matrix for undirected and directed weighted graphs. The calculation is completed for each vertex to reach the final solution all pairs shortest path.

Finally, the module explains the Greedy technique to reach an approximate optimal solution. The logarithm finds the local optimal decision (greedy) for each step while adhering to any constraints. Once a step is performed, it cannot be changed until all steps are taken, yielding the final aggregated optimal solution. The minimum spanning tree (MST) utilizes the greedy concept in Prim’s algorithm to find the smallest weight of an undirected connected graph.

CST370 - Week 6

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

The Lecture this week covers a variety of terms, starting with the AVL tree and the 2-3 tree. A binary search tree must be balanced to enhance the time efficiency for searching, insertion, and deletion. The AVL tree represents a self-balanced structure that preserves the average time complexity of a BST to the Ꝋ(log n). The main property of the AVL tree is that the difference between the right and left subtree heights must be 0 or +1 or −1 at any node. Rotation techniques (R, L, LR, RL) are used to rebalance the AVL trees in the case of insertion or deletion. 

A 2-3 Tree data structure with 2 children and one data element or 3 children with 2 data elements

Another structure that can be used to balance BST is the 2-3 tree. The tree could have two nodes for a single key K and two children: the left subtree with keys less than K and the right subtree with values greater than K.  Another type of 2-3 tree is the 3-node with two key values K1, and K2 (K1 < K2). The 3-node has three children: the left subtree contains key values less than K1, a middle child with key values between K1 & K2, and the right child that holds all key values greater than K2. One of the properties of 2-3 trees is that leaves are the same height. We also reviewed inserting a key value in 2-3 trees.  For the worst and average case, the time complexity for searching, insertion, and deletion is Ꝋ(log n).

The module introduces the Heap data structure as an efficient method of processing priority queue operations. There are two essential conditions for a Max Heap structure: 1) the binary tree must be complete except to the rightmost leaves. 2) The value of the key for each node must be equal to or higher than that of the children. A heap could be presented in an array with n elements starting at the index 1 in top-down left-right order. The bottom-up heap construction algorithm provides the necessary steps to set up a binary tree, then heapifies its nodes to construct a heap. Heapify is also used to insert a key into a Heap structure to initiate a key exchange with the parent node as needed. The heapsort could be accomplished by constructing a max heap and then deleting the max number key repeatedly. The result will be the sorted keys.

The final section of this module discusses the implementation of hashing as a method to distribute keys in the hashing table. The hashing function h(K) = K mod m; denotes keys starting from 0 to m-1 (the range of the division remainder). Assigning key values to the same cell of the hash table results in collision. We reviewed two techniques to avoid collision: Separate Chaining and Linear Probing.

 

CST370 - Week 5

 

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

Module 5 introduces Quicksort, another algorithm using the divide-and-conquer technique. Unlike mergesort, division is the primary stage for solving the problem, and not much work for combining subproblems. A pivot is used to partition an array with a value of elements smaller than the pivot to the right and a value of elements larger than the pivot to the left. We can define the best-case scenario, if an array splits in the middle for partitioning. On the contrary, the worst-case scenario occurs if one subarray yields empty – for example, an increasing array with the selected pivot at an index zero.

The decrease and conquer algorithm design technique utilizes three approaches: decrease by a constant, decrease by a constant factor, and variable size decrease. The textbook explains the concept by illustrating solving a^n where a > 0, and n is a nonnegative integer. The exponential problem could be resolved by decreasing by a constant 1 as follows a^n = a^n-1 * a. Applying the recursive function obtained from this relationship leads to the solution to

the original problem. The binary search is an example of a decrease by a constant factor since elements in a list is reduced by 50%. 

Binary Search Tree (BST) with root node 10

In this section, we applied the divide-and-conquer strategy to solve many problems that resemble a binary tree. The standard representation of a binary tree consists of the left subtree, the right subtree, and the root. Additionally, we reviewed the three types of binary tree traversals: preorder, inorder, and postorder.

We also discussed topological sorting for Directed Acyclic Graphs (DAGs). An important aspect of the Depth-First Search (DFS) forest is the absence of back edges, which is essential for topological sorting. In other words, it is necessary for the directed graph to be acyclic in order to resolve the topological sorting problem. Lastly, the module covered presorting to improve overall time complexity. For example, checking element uniqueness in a sorted array can enhance the algorithm's efficiency, reducing the complexity fromꝊ(n^2) to Ꝋ(n log n).

CST370 - Week 4

 

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

We are now halfway through the course after completing the midterm exam. This week was shorter because we were given time to study for the exam. I dedicated most of my study time to reviewing topics covered in previous weeks. Some of the key concepts required significant focus and practice in specific procedures to solve the problems. I also attended the midterm Q&A session, which was very helpful in discussing several topics.

This week's material was relatively light, focusing only on introducing the Merge Sort algorithm. The Merge Sort technique is based on the divide and conquer strategy. An array that needs to be sorted is divided into smaller arrays, and each part is solved individually before merging them. During the merging process, elements are compared between the two arrays to sort them into the array. This process continues until all elements are sorted into a single array. The time efficiency of Merge Sort is calculated using the Master Theorem, resulting in a time complexity of Θ(n log n).

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.