cst370 Week 3

 This week we continued with brute force techniques including an example involving string matching. This was a helpful illustration of how brute force algorithms work in practice and also showed that the worst case scenario for an algorithm is not always as obvious as it may initially seem. Lectures then covered several classic example problems like the traveling salesman problem, knapsack problem, and assignment problem which demonstrated how different types of problems often require different algorithmic approaches.

We also went into more depth on the graph traversal techniques depth first Search (DFS) and breadth first search (BFS). While these concepts were a review for me, the information was valuable because it introduced new perspectives on analyzing their time efficiency. Later in the lectures we covered the divide and conquer algorithms and the master theorem, including on how to identify the time complexity of recursive problems using this method. 

The week’s homework tied everything together me having to write an algorithm to search a graph using DFS and then later solve a traveling salesman problem using a brute force approach that required checking all permutations of a graph.

Comments

Post a Comment

Popular posts from this blog

CST334 Week 2

    This week has been a great introduction to how CPU process selection works in operating systems. We covered a range of scheduling algorithms, including FIFO (First In, First Out), LIFO (Last In, First Out), Shortest Job First (SJF), and Round Robin (RR). I learned how each algorithm has its own strategy for picking which process should run next, and how these choices affect system performance and metrics like response times.      I also learned to calculating those performance metrics such as response time, turnaround time, average arrival time, and average turnaround time. For Round Robin scheduling in particular, I learned how to calculate how long a process will stay in the system based on the time slice and the number of other processes in the queue. These exercises helped me understand the mechanics of how schedulers work and why the design choices made are so important.      One of the most interesting parts was comparing the pros and ...
Read more

CST334 Week 5

     This week I focused on concurrency and how it allows processes to run multiple threads in parallel, allowing tasks to be handled in the background while the main application continues. While I’ve previously worked with multithreading in Java, learning how the operating system manages concurrency gave me a better understanding of how multithreading works in the CPU. I learned that threads can share certain resources, such as virtual address space which makes communication between them efficient, but also introduces its own challenges.      One of the key concepts I learned was nondeterminism in multithreaded programs. Even if two threads call the same function, the order in which memory is accessed and modified can change which can lead to different outcomes every time the program runs. This unpredictability can cause bugs that are hard to reproduce and debug.      To address this, we use thread synchronization APIs like locks, or mutexes...
Read more

CST334 Week 6

       This week we continued concurrent programming and synchronization concepts and built on the ideas from last week. One of the first things I learned about was binder buffer coding, which was about how data can be shared and communicated between different parts of a system or between different threads. It's a used when dealing with message passing or structured data flow. Systems with modular or layered designs can make use of this to communicate with other parts of the system.    After  that, I learned about the concept of semaphores. Semaphores are a core component in concurrent programming as they act as signaling mechanisms used to control access to shared resources. The main idea of semaphores are integer variables protected by atomic operations like wait() and signal(). A semaphore can be used to limit the number of threads that access a resource such as a database connection pool or a bounded buffer to ensure that the variables remain safe ...
Read more