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:
  1. Split the original array into two halves, until each individual element is by itself.
  2. Sort the first half recursively
  3. Sort the second half recursively
  4. Merge the two halves together:
    1. Compare the first elements of each half
    2. Push smaller element to a new result array
    3. Increment index of half that pushed the smaller element
    4. (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 understand the concepts presented in class.
Isopod Update: The trichorhina tomentosas are back.

Comments

Post a Comment

Popular posts from this blog

CST300 - Week 4

Week 4 has been busy! I have gotten work done a lot later than I would have liked. Part 1: Education Goals My educational goals would be to expand my knowledge about Javascript. The most tangible project to put this in practice would be to create a simple interactable website, possibly using React as a frontend. One of my ideas for a capstone project would be to create a website for a tabletop game I am developing, so the practice would be great for it.   The first step would be to learn about networking -- CST311: Intro to Computer Networking and CST336: Internet Programming would be where I hone these skills. Before these classes, I would like to create a single-task web app as a practice. It would have a starting list of about 20 items, and allow the user to arrange them into 6 specific item slots, like a digital pin board. Then, once I am in these classes, I will look back at this project and see what I can do differently or what I have learned since then.   My web develop...
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...
Read more

CST334 - Week 5

Week 5 Reflection      In this week, I learned a great deal about concurrency, threads, and best practices on how to keep threads managed efficiently. A thread is seen as a process that can share the same address space as another thread, and access the same data, rather than needing to occupy a different address space. Multi-threading is handling multiple threads in the same address space using thread control blocks (TCBs) to store thread states. For multi-threaded processes, each thread has its own stack, called the thread-local storage.       In the aside, four key terms are highlighted:  critical section: Code that accesses a shared resource, like a data structure or variable.  race condition (aka data race): If multiple threads enter the critical section at the same time, a race condition occurs. These threads could be executed in any order, leading to the program becoming indeterminate. indeterminate program: A program with one or more r...
Read more