CST 370 - Design and Analysis of Algorithms - Week 7

-

 


This week in CST-370, I learned about non-comparison based sorting algorithms such as Counting Sort and Radix Sort. Unlike traditional sorting algorithms that rely on comparisons, Counting Sort uses frequency counting and distribution calculations to sort integers efficiently when the range of numbers is relatively small. The time complexity of Counting Sort is O(n + k), where n is the number of elements and k is the range of values. Additionally, I learned about Radix Sort, which processes numbers digit by digit, starting from the least significant digit (LSD) and applying Counting Sort iteratively. Radix Sort is particularly useful for sorting numbers with multiple digits, and its efficiency is O(d * (n + k)), where d represents the number of digits in the largest number. Counting Sort maintains the stability of elements, preserving their relative order in the output.

I also learned more Dynamic Programming (DP) and its applications in optimization problems. The concept of overlapping subproblems and optimal substructure makes DP an effective technique for solving problems like the Fibonacci sequence, the Coin-Collecting Problem, and the Coin-Row Problem. Instead of recomputing the same values recursively, DP uses memoization or iterative tabulation to store intermediate results, significantly reducing redundant calculations. Another important topic covered was Floyd’s Algorithm, which finds the shortest paths between all pairs of vertices in a weighted graph. The algorithm progressively updates the distance matrix by considering each vertex as an intermediate step. Lastly, I was introduced to Greedy algorithms and their applications, such as Prim’s Algorithm for Minimum Spanning Trees (MSTs). The Greedy approach makes locally optimal choices at each step, which sometimes leads to globally optimal solutions.

Comments

Post a Comment

Popular posts from this blog

CST 334 - Operating Systems - Week 6

-
Image
  This week in CST 334, we learned about the concept of semaphores, a fundamental synchronization primitive in operating systems. Semaphores manage access to shared resources using an integer value, which can be incremented or decremented by operations like `sem_post()` and `sem_wait()`. These operations allow semaphores to control resource access, ensuring that threads wait when the resource is unavailable and proceed when it becomes available. A key form of semaphore is the binary semaphore, which functions similarly to a lock by permitting only one thread access at a time, ensuring mutual exclusion.  In addition to basic semaphore usage, we explored various common concurrency problems that semaphores can help solve. For example, in the Producer-Consumer problem, semaphores signal the state of a buffer, preventing data corruption or loss. Similarly, the Reader-Writer problem uses semaphores to manage access, allowing multiple readers or a single writer to use the resource, b...
Read more

CST 363 - Introduction to Database - Week 3

-
Image
  Explain in your words what 3rd normal form is and why it is important. Third normal form, also known as 3NF, is a crucial aspect of database normalization. The third normal form makes sure that the data stored in a relational database is organized to reduce redundancy and improve data integrity. In other words, 3NF is a database schema design approach for relational databases which uses normalizing principles to reduce the duplication of data, avoid data anomalies, ensure referential integrity, and simplify data management. Adhering to 3NF in database design is fundamental for building efficient and reliable database applications. It not only helps maintaining clean data structures but also supports accurate and efficient query responses.  What is an SQL view. How is it similar to a table? In what ways is it different? An SQL view is essentially a virtual table in a database that is not physically stored. Instead, it is defined by a query. A view can contain all rows of a ...
Read more

CST 311 - Intro to Computer Networks - Week 1

-
Image
  This week in CST 311, I learned a lot about the concepts of computer networks, starting with an understanding of the internet's structure and operation. The internet is basically a network of networks, consisting of many connected devices, communication links, and packet switches, all working together with various protocols like TCP, IP, and HTTP. I also learned about the different components of a network, such as the network edge, which includes hosts like clients and servers, and the network core, where packet switching and routing occur. The significance of protocols is so important, as they define the format and order of messages sent and received in the network. Another topic was the concept of delay, loss, and throughput in networks. I learned about the different types of delays such as processing, queuing, transmission, and propagation which affect the overall performance of a network. The introduction to the internet protocol stack is also important, where I learned about...
Read more