Learning Journal

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...

  Who did you work with?  Tim Shaker   What was your strategy for solving the Markov assignment? My Strategy is the same as last time but with at the same time bringing along the few things I learn from my previous projects and peer reviews feed back. I try to read the whole project and understand what is needed. Briefly go over the test cases on what are being tested to understand the functions. When it actually comes to coding I've use my previous strategy of coding methods that doesn't uses any other methods. I code the field type and constructor first then jump to methods. I was able to run the code successfully initially but was giving the wrong output and only 2 test cases pass. That is the time I try to fix the bug 1 by 1. I look for where the bug is by debugging 1 test cases at a time. Stepping through the code and check the output each steps. Once everything is done and all test cases are passing and main is running, I add the javadocs for methods. At this point...

  You can work with up to three people (you MUST work with at least one other person) With whom did you work? I work with Tim Shaker What was your strategy for solving the assignments? Did you start writing code right away? Did you plan it out on paper?  Initially I read the documents of the requirements for the program. I then check the test cases involve within the project. I then started coding the things I can easily understand. I writing the codes of methods that doesn't require any other methods. Once I wrote all the necessary methods and classes needed I check the test cases to see which one fail. I try to solve each bug one at a time until everything passes.  What was THEIR strategy for solving the assignments His strategy was to first read the documentation, then scaffold out out the classes and resolve any syntax errors so that the code would compile. From there, he worked on implementing the logic as it was described in the documentation, focusing on gett...