CST370 - Week 5

CST370 Week 5

  • Binary trees: A divide-and-conquer ready data structure. There are three ways to traverse it: preorder, inorder, and postorder traversal methods.
    • Preorder visits from root -> left -> right.
    • Inorder visits from left -> root -> right.
    • Postorder visits from left -> right -> root.
  • Binary search: An application of the decrease-and-conquer algorithm. Complexity is (big O)(logn).
  • Quicksort: For time complexity, the best case is n(logn), while the worst case is n^2. To perform a quicksort, we assign the first value of an array as the pivot, and recursively travel forward (i) and backward(j)  to find a spot where the pivot can create a partition. While traveling, we swap values of i and j whenever i > pivot and pivot > j. This should create a partition where all values preceding the pivot will be smaller than it, and all values after the pivot will be larger than it.
  • Decrease-and-conquer: Technique to reduce the size of a problem into one smaller problem, solve the smaller problem, and then extend the solution to the whole. A common example is the binary search, which decreases the size of a problem by half for each iteration. Topological sorting is also a decrease-and-conquer algorithm because it reduces the size of a problem by a constant (one). Decrease-and-conquer is different than divide-and-conquer because decrease only creates one new subproblem rather than a number of subproblems.
  • DAG = directed acyclic graph. Topological sorting can determine if a graph is a DAG: if there are back nodes, then the graph is not a DAG.
    This week, we practiced the BFS algorithm more in the homework, which I was happy to get working. I took a few hours today troubleshooting why my code was not working. 
    At first, I had trouble understanding what was wrong with my implementation of the BFS algorithm (with the degree of connection array added), since I was not able to traverse through the entire graph. I later figured out that was because the way I implemented the input graph from user data was not correct. Instead of entering data in [x][y] ordering, I had mistakenly pushed data in an [{x y}] format. I had set the initial input graph as a 2D vector of strings, which is why I had to input data in that way. To fix this, I set up the userMap first and then assigned each edge data pair as an int, then pushed it to a 2D vector of ints instead.
Isopod Update: I think I found another pink pak chong, which is exciting!

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