Learning Journal

 Dijkstra's Algorithm: Solves the problems of finding the shortest path from a single source. It is a Greedy algorithm. It dertermines the shortest path from a single source vertex to each of the other vertices. Has wide applications such as:     - Internet routing     - GPS navigation     - Transportation planning

 This week, I learned about Dynamic programming, which is algorithm design technique for improving the efficiency of certain recursive algorithms, such as Warshall's algorithm and Floyd's algorithm. I also learned about the Greedy technique, which is used to solve optimization problems, such as the Prim algorithm Dynamic Programming To avoid multiple calls for a sub-problem (ex: base case for fib), use an array to keep solutions of sub-problems. Example: Fib(n):     F[0] = 0;     F[1] = 1;      for (i = 2 to n):          F[i] = F[i-1] + F[i-2]     return F[n]; In General:     1. Set up a recurrence relation that describes a solution to a problem with smaller sub-problems.     2. Solve the smaller sub-problems and record the solutions in a table.     3. Solve the original problem using the table. Dynamic Programming - Solving Coin-Row Problem Coin-row problem: There is a row of n coin...

       This week, I learned about two different types of balanced trees and their associated algorithms: AVL Tree and 2-3 Tree. I also learned how to use the Heap data structure to efficiently find maximum and minimum values. Heap can be represented by the bottom-up algorithm. Finally, I learned to use Hashing for storing values in a dictionary/array to perform efficient search operations. AVL Trees Problem: Unbalanced trees result in operations that take O(n) time. AVL Tree : A balanced binary search tree. The difference between the heights on the left and right subtrees is either -1, 0, or 1. ( balance factor = height of left subtree - height of right subtree) Ex: Since each node has a balance factor of -1, 0, or 1, it is an AVL tree. AVL Tree Rotations Rotation : A local transformation of a subtree whose balance factor has become either +2 or -2. Four types of rotations: R(right)-rotation, L(left)-rotation, LR-rotation, RL- rotation Ex:     A   ...

 This week, I learned to apply the "Divide-and-conquer" technique in a sorting algorithm, known as "Quick-sort." I also learned about "Decrease-and-conquer", which is a similar technique to divide-and-conquer and is used in sorting algorithms, such as "Insertion sort" and Khan's algorithm. A third technique I learned is the "Transform-and-Conquer" technique, which is used in "Pre-sorting." I also began to understand the efficiency of the algorithms used for Binary Tree traversal and height calculation. Quicksort Uses the Divide-and-conquer technique. It is "in place", like insertion sort, but not like merge sort (does not take up extra space) Quicksort of an n-element array: 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray < x < elements in upper subarray 2. Conquer: Recursively sort the two subarrays. 3. Combine Example of Partitioning Worst case: O(n^...

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

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

 This week I learned more about managing free space in memory, more translation techniques using paging, and the different policies that determine when a page should be swapped out into disk. In memory, external fragmentation will cause free space to be chopped up into little pieces of different sizes. This may cause some requests to fail as there may be no space left to fit the request. To solve this problem, a free list data structure can be used to manage free space in the heap. A free list looks similar to a linked list data structure. Each node contains an address of where space is free and the length of that free space. When requesting in memory that may be smaller than what is available in a free chunk, the allocator will split a free chunk into two so it can satisfy the request. In the opposite case, when a chunk of memory is free, the allocator will coalesce free space. There are different strategies that are used for managing free space, best fit, worst-fit, and first-fit...

 This week I learned about address spaces, techniques for translating virtual addresses to physical memory, and some C apis for allocating and deallocating memory. An address space is a running program's view of its memory in the system. This program's address space will not be the same as its exact space in physical memory due to virtualization. The purpose of virtualizing the program's memory is that it allows for transparency, efficiency, and protection from other processes or the OS from processes. The program will think its address space starts at 0 (and so will the CPU), but the MMU will translate the program's address space into physical memory by techniques such as, base-and-bounds, segmentation, and paging.  Base-and-bounds translation is a technique for translating virtual addresses into physical ones by having the CPU assign a process a base register and a bounds register. The base register will be its actual location in memory, and the bounds register will b...

The topics we covered this week are processes, how the OS manages them, and the different schedulers that decide which processes should run at a given time. A process is essentially a running program that executes on the CPU. Processes run in user mode and do not have access to privileged instructions. When a process needs to perform a restricted operation, it makes a system call that triggers a trap, allowing the OS to take control in kernel mode and safely execute the requested task before returning to user mode. The different scheduling algorithms that we studied this week include FIFO, a scheduling program that runs the first process in a queue, SJF, a schedular which run the process with the shortest execution time, and Round Robin, a scheduler that switches between processes based on a time splice. I think one of the more difficult topics for me this week was how to schedule process using the Round Robin scheduler. I was able to understand this conceptually but had some difficult...

The topics I learned this week are the basic concepts of an operating system, converting from binary to hexadecimal, and using bash scripts to run C programs. One of the uses of an operating system is to allow programs to share memory and enables programs to interact with devices that are in charge of making sure the system operates correctly and efficiently. An important concept in operating systems that I learned this week is virtualization. Virtualization allows the OS to take physical resources and transform them into a more general, powerful, and easy-to-use virtual form of itself (a virtual machine). I was able to practice these concepts through lab 1 and the first homework assignments. In these assignments, we learned to use docker to host a virtual OS so we could build C programs. Through these assignments, I was able to strengthen my understanding of memory allocation. I had some experience with using pointers in C++, but I was somewhat confused on how malloc() worked and why ...

Briefly summarize what you consider to be the three (3) most important things you learned in this course. Learning MySQL to query/update data from a database. Learning about alternative databases, such as the NoSQL database, and using MongoDB/Java to create a web application. Learning to normalize a database to reduce redundancy in a database by following Third Normal Form or BCNF. 

Compare MongoDB with MySQL.  What are some similarities?  Both have query projections, unique keys, indexes and explain queries What are some differences?  MongoDB does not have transactions, but they can still be atomic. Both have different languages for querying data. When would you choose one over the other? \ MySQL should be used if your data is mostly relational. MySQL has more support for making more complex queries or joins. If your data is not structured, MongoDB may be more beneficial.

 This week I learned how to connect to a database using Java via JDBC. A connection must be created using the database's url, username, and password. SQL statements can be executed in Java using Statements or PreparedStatements. Running executeStatement will return a ResultSet which can be used to read from the returned rows. Statements should always be sanitized to prevent SQL Injection and values should never be concatenated into the SQL string. Transactions are committed automatically but can be turned off using setAutoCommit(false) 

  The web site   "Use the Index Luke"  has a page on "slow indexes".    https://use-the-index-luke.com/sql/anatomy/slow-indexes Links to an external site.   If indexes are supposed to speed up performance of query, what does the author mean by a slow index?  There may be additional costs that need to be made depending on the query. The author states that leaf node chains and table access may slow down lookups. If there are multiple matching entries in a lead node, the database will have to continue to reading data in the next leaf node. If there are multiple rows in a table that is pointed to from an index, each one would need to be read, decreasing performance.

  Briefly summarize 5 things what you have learned in the course so far.   I learned how to query data using MySQL. (select, update, delete statements, etc.) I learned more about the inner workings of SQL by using Java to implement a simple database. Predicates are implemented using a tree data structure, indexes are implemented using a B+ tree data structure. I learned how to use views and subqueries in SQL, which allows us to simplify complex queries. I learned how indexes can be used in a database to improve performance of lookup queries but may be detrimental if a table is often updated as the corresponding index will also have to be updated, affecting performance. I learned how to optimize ER designs by following normalization rules, which will prevent update anomalies and prevent the duplication of unneeded data. List at least 3 questions you still have about databases. How do we use non-relational databases, such as NoSQL? How are complex joins implemented in datab...