Learning Journal

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

 This week, I learned the benefits of concurrency, the C pthreads API, and how locks are used to protect programs from race conditions. Concurrency is beneficial as it is a useful programming abstracting, increases responsiveness, and it can leverage multicore machines and GPUs. On the other hand, concurrency can introduce bugs related to concurrency, and it can cause programs to be non-deterministic. A program is not deterministic when the output of the program is not expected and changed each time it is ran. This is commonly caused by race conditions. A race condition arises when multiple threads of execution enter the critical section (a shared resource) at roughly the same time. The threads will attempt to update the shared data structure and as the schedular will be making the decision on which thread will be run, the output if the program will become undesirable. Programs can avoid these problems by having threads use some kind of mutual exclusion primitive, which will guaran...