Learning Journal

For week 3 of CST370 Design and Analysis of Algorithms we learn about quick sort. Quick sort was first proposed by C.A.R Hoare in 1962. It uses Divide-and-Conquer and very popular but its efficiency can be tricky. Basically quicksort an n-element array it "Divides", in partition, the array into two subarrays around a pivot such that elements in the lower subarray elements in upper subarray. It then concquer recursively sort the two subarrays and combine. Quicksort worst case scenario when the data is already sorted and its has O(n^2) at its worst. Best case however it has O(nlogn) and its average case and use has that efficiency.  We also learn this week about Binary tree traversals. A binary tree is a divide and conquer ready data structure. One classic problem with binary trees is to systematically visit each node. There are three binary tree traversals called inorder, preoder and postorder. Preorder, from the word "Pre", traversal visites the node in the order Ro...

Week 4 is a short week and only few things was discussed. In particular this week we learn about merge sort. Merge sort basic idea is to split the input into two halves. Sort the first half of the input recursively. Sort the second half of the input array recursively. Then merge the two sorted halves together. Merge sort uses the divide and conquer technique to sort an input array with n elements. During the time analysis of merge sort, using master Theorem, it shows that the case is O(n log n). Since the recurrence relation T(n) = 2* T(n/2) + n-1 which is 2* T(n/2) + O(n). With master theorem a = 2, b = 2 and d = 1. This relation shows that a = b^d which is 2 = 2^1 which shows that it is O(nlogn). Other than that I basically had a review with everything from week 1 to week 3. Week 4 is midterm that is why it is short. Basically re-learn everything that I learned in the past plus the new Merge Sort concept.

 For week 3 of CST370 Design and Analysis of Algorithms we learn about Brute force string matching and exhaustive search.  With the string matching problem, we basically try to match the characters in a text and find a substring of the text that matches the pattern. Brute-Force matching basic idea is to compare the characters by character. If a mismatch occurs shift a character and restart the comparison. The best case for this is when immediate match occurs, a minimum number of comparisons will occur. It is often easy to think about the best case scenario but worst case is not. A worst case scenario may not be too obvious since it may require more comparisons.  Exhaustive search is a brute force approach to solve combinatorial problems. The basic idea of this are to generate all potential solutions to the problem. Evaluate each case one by one and determine the solution among the possible cases. For example Traveling Salesman Problem (TSP) is to find the shortest tour th...

Week 2 of this class was a lot to take in but I was able to follow along well. Algorithm Analysis is the process to identify the category or order of growth of an algorithm. We learn about the three notations which are the upper bound, tight bound and lower bound. We learn about Asymptotic Notations for Algorithm analysis. An algorithm’s running time t(n) is said to be in O(g(n)), denoted t(n) ∈ O(g(n)), if there exist positive constants c and n0 that satisfy the following condition. As a sample if t(n) = n^2 + 3*n + 5 then we can say that t(n) is O(n^2) since we can ignore the constants and the function has n^2 as the highest power. We also learn about the order of growth of algorithms. First is constant which is O(1) then it goes for more execution time. Logarithmic O(log N), Linear O(N), Log-linear O(N log N), Quadratic O(N^2), Cubic O(N^3), Exponential O(2^N) and lastly Factorial O(N!).  Another topic that was discussed was the Non-Recursive algorithms which are algorithms that...

 This week I learn about general knowledge about algorithm. Basically an algorithm is a sequence of order/instruction for a solution of a problem. In the context of computer science it is best to use the least amount of instruction to achieve the output we desire. This doesn't happen all the time but it would be considered as the most efficient way. I also learn about Euclid's algorithm for GCD. This algorithm mainly solves or finds the greatest common divisor by doing gcd(m,n) = gcd(n, m mod n) where n is the smaller number while m is the bigger number. This algorithm will go on until one of the number is 0. We also tackle about other gcd calculations alternative solutions. Overall problems can be solve different ways and it is in our best interest to use the most efficient way to save time and memory depending on the algorithm. We also learn about Pseudo-code and how to write it. Pseudocode is basically a high level description of algorithm. It is written for people to be abl...

  Wk07/08: Learning Journal Summary   Looking back to HW 1 I would approach it differently on how I initially did it. When I first did it I didn't check the test cases first. Now that I know checking the test cases can help me understand what each function or code does, I will try to read the test cases first before jumping into coding. Second, I would do the functions that doesn't have dependency of other methods. Doing so helps me understand the flow of the logic. While I was initially reading through the documentation, I would jump from one method to another just because I don't fully understand the flow of it. Implementing methods that can work by itself helps me understand the workflow logic. Other than those two things I can't think of any major approach that I need to change. Maybe some minor changes I can do is to clean up the documentation and make sure the TODOs are done before submitting my work.   Overall through out the entire class I'm really proud and...