CST 370 Week 4

WELCOME TO WEEK 4

Learning Journal - CST 370

This week, we learned about Merge Sort, which uses the divide and conquer technique. It splits an array A into two halves recursively until each subarray contains only one element. After that, the algorithm begins merging and comparing elements in order to place them in sorted order, combining them back into the original array. This process is done recursively.

The merge operation works by comparing the first elements of two subarrays, B and C. The smaller element is added to A, and the index (or pointer) of the corresponding subarray is incremented to move to the next element. This process continues until all elements from B and C have been merged into A, resulting in a fully sorted array. 

The time efficiency of Merge Sort is determined using the Master Theorem. It falls under case 2, not case 3, meaning its time complexity is Θ(n log n). This makes Merge Sort an efficient algorithm, especially for large datasets, as it consistently performs better than quadratic sorting algorithms like Bubble Sort or Insertion Sort.

Overall, this was a really interesting algorithm to learn. There wasn’t a lot of material to cover this week since we had a midterm on Saturday, which gave me enough time to study and focus on creating my four study sheets. I had to carefully decide what to include, but I think I added really useful information because they were extremely helpful during the exam. There were a few things I left out, but I’ll know better for next time. I still don’t know my grade, but I’m hoping I did well on the midterm. Attending the Zoom meeting for the midterm review was really helpful. My classmates did a great job explaining the material and helping others understand the concepts better, which made reviewing much easier.

Comments

Post a Comment

Popular posts from this blog

CST 370 Week 3

Image
  WELCOME TO WEEK 3 Learning Journal - CST 370  This week, we learned a lot. We started with Brute-Force String Matching , an algorithm that aligns the pattern against the first characters of the text and begins to match pairs of characters from left to right. It continues this process until there is either a match or, in the worst case, the pattern is not found in the text at all. The best case occurs when the first characters in the text immediately match the pattern. Next, we learned about Exhaustive Search and its application to three important problems. Exhaustive Search is simply a brute-force approach to combinatorial problems such as permutations, combinations, and subsets of a given set. The first problem we covered was the Traveling Salesman Problem , which involves finding the shortest path through a set of cities (visiting each city exactly once) and returning to the starting city. It is also described as the problem of finding the shortest Hamiltonian cycle. The...
Read more

CST 311 Week 1

Image
  WELCOME TO WEEK 1 Learning Journal This week has been really good so far. I learned a lot of new things that I found very interesting. To begin with, this week's chapter started with an introduction to what the internet is and how it is viewed. It is first described as the "nuts and bolts," where it talks about all the hardware and software that is involved. For example, there are billions of computing devices such as hosts (or end systems) running network applications. Hosts can be a PC, server, laptop, smartphone, etc. In order to carry signals across from one end system to another, there are communication links such as wired or wireless links. There are also intermediate devices called packet switches, which forward packets. There are also protocols that control the sending and receiving of messages sent from one end system to another. Some examples of these protocols are TCP and IP. Protocols are used to define the format and order of the messages that are being sen...
Read more

CST 370 Week 2

Image
  WELCOME TO WEEK 2 Learning Journal - CST 370  This week, I learned about the Analysis of Algorithms . First, we reviewed the topic of time efficiency notations , focusing on three key types: Big O Notation , Big-Theta Notation , and Big-Omega Notation . Big O Notation represents the upper bound, meaning it describes all functions with the same or lower order of growth as f(n). Big-Theta Notation represents the exact bound, meaning it includes all functions with the same order of growth as f(n). Big-Omega Notation represents the lower bound, meaning it captures all functions with the same or higher order of growth as f(n).      We also revisited the orders of growth , which, to be honest, I had forgotten about. Luckily, we reviewed them this week to help us better analyze algorithms and identify their time complexity or order of growth. The eight most common categories we covered were: 1, log n, n, n log n, n², n³, 2ⁿ, and n!. To figure out the order of gro...
Read more