Posts

CST 370 - Design and Analysis of Algorithms - Week 7

-
Image
  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 over...
Post a Comment
Read more

CST 370 - Design and Analysis of Algorithms - Week 6

-
Image
  This week in CST-370, we learned about more advanced data structures such as AVL trees, heaps, and hashing. AVL trees solve the issue of unbalanced binary search trees by maintaining a balance factor between -1 and 1, ensuring logarithmic time complexity for operations like search, insert, and delete. I learned how rotations (left, right, and combinations of both) restore balance when inserting or deleting nodes. The concept of balancing height was interesting because it talks about the trade-offs between complexity and performance. We also learned about heaps, focusing on their role as priority queues. A heap is a complete binary tree where each parent node adheres to a specific order property, either greater than (max-heap) or less than (min-heap) its children. I learned the importance of heapify operations and how heaps support efficient insertion and deletion in logarithmic time. Also, heapsort was introduced as a sorting algorithm that leverages the heap’s structure to achie...
Post a Comment
Read more

CST 370 - Design and Analysis of Algorithms - Week 5

-
Image
  This week in CST-370, I learned more about QuickSort and its importance in algorithm design. QuickSort is a divide and conquer algorithm, which stands out for being efficient and "in place" unlike Merge Sort. I learned how the partitioning step affects its performance, with the best case being a balanced split and the worst case occurring when the partition divides unevenly, such as in already sorted or reverse sorted arrays. Empirical analysis mentions the practical implications of efficient algorithms over brute computational power, which made me prioritize learning effective techniques. Additionally, I learned about binary tree traversals, specifically preorder, inorder, and postorder traversal methods. These techniques consist of visiting each node and I practiced some examples to better understand the order in which nodes are visited. Also, I was introduced to the "Decrease and Conquer" approach, an algorithm design technique that simplifies a problem by solv...
Post a Comment
Read more

CST 370 - Design and Analysis of Algorithms - Week 4

-
Image
  This week in CST-370, we learned about the merge sort algorithm. Merge sort follows the divide and conquer technique to efficiently sort an input array, with a time complexity of Θ(n log n). I found this algorithm relatively easy to understand. The process begins by dividing an unsorted array into two halves, and this division continues recursively until we are left with individual elements. Once the base case is reached, the sorting phase begins, where smaller elements are placed on the left and larger elements on the right. This merging process continues until a fully sorted array is obtained. Besides learning about merge sort, we spent the rest of the week reviewing for the midterm. While we did not cover much new material, I found merge sort to be an interesting and useful algorithm.
Post a Comment
Read more

CST 370 - Design and Analysis of Algorithms - Week 3

-
Image
  This week in CST370, we focused on understanding various brute force and exhaustive search algorithms, such as string matching, depth-first search and breadth-first search. I learned that brute force is a straightforward approach to solving problems by directly applying the problem's definition. For instance, selection sort and bubble sort are classic examples of brute force algorithms where elements are compared and swapped until the array is sorted. The brute force string matching algorithm was particularly insightful, as it involves searching for a pattern in a given text through character by character comparisons. We also learned about its efficiency in terms of best case and worst case scenarios, noting that its average case efficiency is linear, Θ(n). This helped me understand the importance of time complexity when analyzing algorithms and how different cases affect performance. In addition to brute force algorithms, we learned about exhaustive search approaches, such as th...
Post a Comment
Read more

CST 370 - Design and Analysis of Algorithms - Week 2

-
Image
  This week in CST-370, we learned more about algorithm analysis and how to determine the efficiency of algorithms using asymptotic notations such as Big O, Theta, and Omega. These notations help categorize an algorithm's growth rate based on its input size, which is important for understanding its performance under different conditions. We reviewed more about the importance of identifying the basic operation within an algorithm and counting how many times it executes to estimate its time complexity. The professor's explanations helped clarify concepts that were more challenging to understand from the textbook, particularly simplifying time complexity expressions using standard rules. We also focused on learning the differences between analyzing recursive and non-recursive algorithms, with recursive algorithms often requiring recurrence relations and substitution methods for accurate analysis. Additionally, we relearned about the brute force approach, which is a straightforward...
Post a Comment
Read more

CST 370 - Design and Analysis of Algorithms - Week 1

-
Image
  This week in CST 370, I gained a foundational understanding of algorithms and their importance in solving computational problems efficiently. I learned that an algorithm is a sequence of clear and finite instructions designed to solve a problem for any valid input. Euclid's algorithm for calculating the greatest common divisor (GCD) stood out as an excellent example of how simple steps can lead to powerful solutions. Also, I learned about alternative methods for GCD calculation, such as the Consecutive Integer Checking Algorithm and the Middle-School Procedure, which showed different approaches to solving the same problem. These methods helped me understand the complexity of algorithm design and how problem solving can be approached from multiple perspectives. I also learned more about data structures and algorithm analysis, which are crucial for evaluating the efficiency of solutions. Understanding the principles of sorting and searching was important in order to understand algo...
Post a Comment
Read more