Learning Journal

 This week, I learned about the merge sort algorithm, an algorithm that uses the divide-and-conquer technique for sorting. Basic Idea     1. Split the input array into two halves     2. Sort the first half of the input array recursively     3. Sort the second half of the input array recursively     4. Merge the two sorted halves together Merge of the two sorted array B and C: 1) Compare the first element in arrays B and C 2) The smaller element is added to array A 3) The index of the array with the smaller element is increased by one (pointing to the next element) 4) Repeat until all elements from B and C are copied into A (sorted) Example: Time Analysis Of Merge Sort Algo: Mergesort(A[0, ... n-1]) if n > 1     copy A[0..[n/2]] to B[0..[n/2]-1]     copy A[n/2.. n-1] to C[0.. [n/2] - 1]     Mergesort(B[0..[n/2]-1]     Mergesort(C[0..[n/2]-1])     Merge(B, C, A) Recurrence relation:  ...

     This week, I learned multiple algorithms that apply different techniques to solving problems. They include Brute force and Divide-and-Conquer. Brute-force String Matching Given a string of n characters, text, and a string of m characters called the pattern, find a substring of the text that matches the pattern. Basic idea for solving string problems with Brute Force 1. Character by character comparison 2. If a mismatch occurs, shift a character and restart the comparison Efficiency for best case: If there is an immediate match, minimum number of comparisons will occur. (m) E.g. - Text: CSUMBGO - Pattern: CSU Efficiency for worst case: If there is no matching pattern, may iterate through entire text. Exhaustive Search and TSP Exhaustive search : A brute-force approach to solving combinatorial problems. Basic idea:     1. Generate all potential solutions (or all possible cases) to the problems.     2. Evaluate each case one by one     3. D...

 This week, I learned to mathematically analyze algorithms using Asymptotic notations on algorithms such as non-recursive and recursive. Asymptotic Notations Algorithm analysis is to identify the time category of an algorithm (time complexity). The most common categories are: 1, log n, n, nlogn, n^2, n^3, 2^n, n! Three notations that represent an algorithm's efficiency: O(f(n)) <- upper bound ,  Θ  (f(n)) <- tight bound , and  Ω (f(n)) <- lower bound . f(n) written as O(n^2), Θ (n), Ω(nlogn) Upper bound : All functions with lower or same order of growth as f(n). Ex: f(n) = O(n^2) Functions that satisfy: 1, n, nlogn, n^2, 5n, 7n^2, 500.  Tight bound : All functions with the same order of growth as f(n). Ex: f(n) =  Θ (n). Functions that satisfy: 4n, 20n Lower bound : All functions with same or higher order of growth as f(n). Ex: f(n) =  Ω (n*logn). Functions that satisfy: n*logn, n, n^2, n^3, 4n^3  Two Rules to Simplify T(n) T(n) => ...

 This week I learned what Algorithms are, important problem types in Algorithms, fundamental data structures, and analysis of algorithms. Algorithm: A sequence of clear instructions for solving a problem. Algorithms produce output in a finite amount of time. It is advised to solve a problem by choosing the right algorithm first before coding the solution. Euclid's Algorithm: An algorithm used to calculate GCD (Greatest Common Devisor). The GCD is the largest integer that divides both m and n evenly, with a remainder of zero. m and n can't be 0 at the same time. If one of the two values m or n is 0, the other non-zero input is the answer. (e.g. gcd(60,0) = 60) Ex:  gcd(0,0): 0/0 = Invalid gcd(6, 4) Numbers that can divide evenly between both: 1, 2, 3  (Can't divide 4), 4  (Can't divide 6) Largest is 2, so answer is 2. Euclid's algorithm is: gcd(m, n) = gcd(n, m mod n) until n becomes 0. At that point, m is the answer. Ex: gcd(60, 24) = gcd(24, 60 mod 24) = gcd (24, ...

 Final thoughts on service learning What went well? What would you improve? What was the most impactful part? What challenges did you face? For our service-learning project, we were able to complete a portion of an existing mobile application that contains an admin view for staff to view student information and view QR codes for rooms where students can check into and checkout of by using their respective QR codes. I think one part I would improve, is to make it more clear on what tasks the team will be responsible for at the beginning of the project. One challenge our team faced was initially getting requirements from our site supervisor, turning them into user stories, and then creating implementation details for our team to work on. What advice do you have for future SL students? One piece of advice I have for future SL students who are working on a software project, collaboratively, is to learn how to use git for version control and to be familiar with the code review process. ...

 This week I learned more about conditional variables, semaphores, and how to write code using semaphores. One of the solutions we came up with was the polling solution. In this case, we want to occasionally read from the shared resource. An example of this could look something like: static int some_value = 0; void* read(void* thread) {     while (1) {          sleep(1);          some_value = get_value();     } } void* api(void* thread){ while (1) {      if (some_vaue != old_value) {          old_value = some_value;     } } } In this example, the shared resource (some_value) is being constantly read inside our loop. This ensures that we can run some condition whenever the value store inside our variable changes. However, this introduces some problems. This solution is inefficient as it is constantly running to check to the value stored inside some_value, caus...