CS Online Learning Journal

 This was our fourth week in CST 370 - Design and Analysis of Algorithms. Merge Sort This week we discussed Merge Sort. Mergse Sort is a divide-and-conquer algorithm that sorts an array by dividing into two smaller arrays, sorting those two arrays recursively, and recombining (or merging) the arrays back together.       We also briefly discussed the time efficiency of the Merge Sort algorithm: Recurrence Relation: T(n) = 2*T(n/2) + n-1 => 2*T(n/2) +  Θ(n) Using Master Theorem: a = 2, b = 2, d = 1 Case 2: a = b^d = 2 => Θ(n log n) Merge Sort Exercise We also had an exercise to use Merge Sort on an array of numbers:  [5, 3, 1, 9, 8, 2, 4, 7] We first split this array into two halves: [5, 3, 1, 9] [8, 2, 4, 7] We continue splitting the arrays: [5, 3, 1, 9] => [5, 3] [1, 9] => [5] [3] [1] [9] [8, 2, 4, 7] => [8, 2] [4, 7] =>   [8] [2] [4] [7] Then we merge the arrays, sorting as we go:   [5] [3] [1] [9] => [3, 5] [1, 9] ...

  This was our third week in CST 370 - Design and Analysis of Algorithms.  Brute Force String Matching The first algorithm we looked at this week was Brute Force String Matching. In this algorithm we loop through each character of a string. Then for each character we loop again, starting at that character, until we find the pattern we are looking for (in which case we return true) or find a character that does not match the pattern (in which case go back to the first loop. Exhaustive Search The class lecture defines Exhaustive Search (ES) as a Brute-Force approach to solve combinatorial problems. The basic concepts of Exhaustive Search are: Generate all potential solutions (or all possible cases) to the problem. Evaluate each case one by one. Determine the solution among the possible cases. Our class lecture discusses using ES to solve some different problems.  Traveling Salesman Problem (TSP) To solve this problem using ES we compute each permutation of the gra...

 This was our second week in CST 370 - Design and Analysis of Algorithms.  Asymptotic Notations  This week we discussed three different notations for measuring algorithm efficiency. O notation, also called Big Oh, is defined as all functions with the same or lower order of growth as f(n). It is used to measure the upper bound of an algorithm's efficiency. For example, the O notation of a sequential search would be O(n). Θ notation, also called Big  Theta, is defined as all functions with the same order of growth as f(n). It is used to measure the exact efficiency of an algorithm. For example, an algorithm with an order of growth of n would be  Θ(n).  Θ notation cannot be used for an algorithm with a varying order of growth, such as a sequential search. Ω notation, also called Big Omega, is defined as all functions with the same or higher order of growth as f(n). It is used to measure the lower bound of an algorithm's efficiency. For example, the Ω...

This was our first week in CST 370 - Design and Analysis of Algorithms. What is an algorithm? Our textbook, Introduction to the design and analysis of algorithms, defines an algorithm as a sequence of unambigous instructions for solving a problem. It also gives a list of important points for algorithm design (p. 29):  The nonambiguity requirement for each step of an algorithm cannot be compromised.  The range of inputs for which an algorithm works has to be specified carefully.  The same algorithm can be represented in several different ways.  There may exist several algorithms for solving the same problem.  Algorithms for the same problem can be based on very different ideas and can solve the problem with dramatically different speeds.   Another important idea is that algorithms are system agnostic. They can be implemented in any programming language, or even done manually. The textbook presents algorithms using psuedocode. Algorithm Examples  Euclid'...