Posts

CST370 - Week 4

 CST370 Week 4 This week is a short week due to midterms. We learned about merge sort, which uses the divide-and-conquer method. Merge sort goes through these steps: Split the original array into two halves, until each individual element is by itself. Sort the first half recursively Sort the second half recursively Merge the two halves together: Compare the first elements of each half Push smaller element to a new result array Increment index of half that pushed the smaller element (Repeat Steps 1-3 until all elements are sorted) For Master Theorem, the time complexity of merge sort is  θ [n*log(n)]. There are two recursive calls, so a = 2, the input size divides by 2 each time, so b = 2, and since the number of comparisons is n, (n^d) = (n^1) => d = 1. I wanted to understand how to derive the Master Theorem from pseudocode, so I looked up some practice exercises online, but there is very little found for it. I decided to get the textbook because I need more exercises to un...
Post a Comment
Read more

CST370 Week 3

Image
CST370 Week 3      This week I studied a lot more about recursion and search algorithms in order to understand the homework better.       We learned about brute force algorithms like exhaustive search, which is useful in finding all permutations of a set. Exhaustive search goes through each possible case and then identifies which of these cases is either most efficient or solves the problem. The time complexity for exhaustive search is dependent on the number of permutations it has [ (n - 1)! ].      There are two graph traversal algorithms: depth-first search (DFS) and breadth-first search (BFS).       DFS makes use of a stack and a mark array to determine what nodes have been visited, and creates a tree with tree edges. Time efficiency for DFS is dependent on the sum of the number of vertices and edges it has: 𝚯 (|v| + |e|).     BFS makes use of a queue and a mark array to determine what nodes have been v...
Post a Comment
Read more

CST370 Week 2

CST370 Week 2 Week 2: I still need more practice on the homework. I am rusty when it comes to manipulating vertices and displaying them correctly. The other homework about manipulating time differences was very easy in comparison.  I learned a great deal about recursion! Biggest concepts to me to not forget are: Big Om notation is an upper bound, so an algorithm must be the same order or lower growth as f(n). So, n^2 would not be within bounds for Omega notation of n. Big Theta notation is a tight bound, meaning an algorithm must remain within the same order of growth as f(n). So, n^2 or log(n) would not be within bounds for Theta notation of n, only n. Big Omega notation is a lower bound, so an algorithm must be the same order or higher growth as f(n). So, log(n) would not be within bounds for Omega notation of n.
Post a Comment
Read more

CST370 - Week 1

CST370 - Week 1 New course! CST370 is Design & Analysis of Algorithms.  Currently, I am wracking my brain trying to remember C++. It's been a while, but I feel more comfortable working with it versus Java.  From what I've read, using pseudocode is the most fundamental way to begin thinking about making programs. Before even translating it to a language, try to walk through the algorithm in your head or on paper. If you find that the algorithm is frustrating to make sense of already, how do you even begin implementing it in code? (Well, you still can, but understanding how it works is why we're here.)  I remember one of the hardest concepts for me to grasp was binary tree traversal. I hope I get a lot more practice out of it in this class!
Post a Comment
Read more

CST426S Week 8 [FINAL]

Ooops. Forgot to update these.      Since I last made a blog post, I learned a great deal more about computer science. I am way more interested in web development, and had a great opportunity working with Eat for the Earth to create a better website. For my capstone project, I am more interested in making a web app resource for my TTRPG, to make it more accessible and easier to parse its content. Tentatively, the name of it is "Monstery Manual", because my TTRPG is called Monstery Dungeon. Might not do well with SEO using that name, so I will come up with a better name later. If you're familiar with Draw Steel's online resource Forge Steel, or LANCER RPG's online resource COMP/CON, it will be very similar to those and draw much of its design inspirations from them.      CST462S was very informative by teaching students how to work in a professional environment. The experience was a lot more laid-back than I expected, but might be because I worked with a non...
Post a Comment
Read more

CST334 - Week 7

Week 7 Reflection This week, we covered a lot about persistence, and how the OS interacts with files, directories, and I/O devices.  I/O devices can range from memory buses to hard drives to keyboards. For a canonical I/O device, the canonical protocol is: While (STATUS == BUSY) ; // wait until device is not busy (polling the device) Write data to DATA register Write command to COMMAND register (Doing so starts the device and executes the command) While (STATUS == BUSY) ; // wait until device is done with your request  The basic protocol to interact with an IDE disk is: Wait for drive to be ready (polling). Write parameters to command registers. Start the I/O. Data transfer. Handle interrupts. Error handling. I/O time, or T I/O , is calculated by the seek delay + rotational delay + transfer delay. In other words,  T I/O  = T seek  +  T rotation +  T transfer The rate of I/O is the size of the transfer divided by the I/O time, or Size transfer  /...
Post a Comment
Read more

CST334 - Week 6

Week 6 Reflection This week, we learned more about semaphores, and the bugs that are commonly faced in concurrency, such as deadlocks.  Semaphores are a synchronization primitive that has a modifiable integer value. The behavior of the semaphore is determined by this value. They can be used as both locks and condition variables for concurrency.  sem_wait() and sem_post() are used to interact with a semaphore. sem_wait() waits for a condition to be met, while sem_post() increments the value of the semaphore, then wakes a waiting thread. If a semaphore's value is negative, this number is equal to the number of waiting threads. For example, -4 equals four waiting threads, incrementing by 1 will change it to -3, waking one thread and now resulting in three waiting threads. Concurrency creates bugs that are difficult or costly to fix correctly. Non-deadlock bugs include atomicity violations and order violations. Atomicity violations occur when instructions that sho...
Post a Comment
Read more