CST-370 Week 4

 This week, I learned about the merge sort algorithm, an algorithm that uses the divide-and-conquer technique for sorting.

Basic Idea

    1. Split the input array into two halves

    2. Sort the first half of the input array recursively

    3. Sort the second half of the input array recursively

    4. Merge the two sorted halves together

Merge of the two sorted array B and C:

1) Compare the first element in arrays B and C

2) The smaller element is added to array A

3) The index of the array with the smaller element is increased by one (pointing to the next element)

4) Repeat until all elements from B and C are copied into A (sorted)

Example:



Time Analysis Of Merge Sort

Algo: Mergesort(A[0, ... n-1])

if n > 1

    copy A[0..[n/2]] to B[0..[n/2]-1]

    copy A[n/2.. n-1] to C[0.. [n/2] - 1]

    Mergesort(B[0..[n/2]-1]

    Mergesort(C[0..[n/2]-1])

    Merge(B, C, A)

Recurrence relation: 

T(n) = aT(n/b) + f(n) where f(n) is an element of Big Theta(n^d), d >= 0

A is 2 since we are making two recursive calls. B is 2 since we are dividing the input size by two.

T(n) = 2*T(n/2) + n-1

-> 2*T(n/2) + O(n^1) <-- Big theta

a = 2, b = 2, d = 1

Case 2: a = b^d => 2 = 2^1 => 2 = 2

Big Theta(nlogn)

Comments

Post a Comment

Popular posts from this blog

Week 4

Part 1 Educational Goals. My main educational goal is to achieve my bachelor's degree in computer science in 2 years. Another educational goal of mine is to do well in my upper division classes so I can be prepared for a career in software development. I would also like to strengthen my collaboration skills through the use of group projects.  Part 2 Career Goals. One of my main career goals is to become a professional software developer after graduation. I hope to leverage my current internship as an Android developer to find a new internship next summer, so I can explore different fields in software development. Part 3 Guess ETS percentile. If I had to guess, I think I would be in the 70th percentile. I feel pretty comfortable with programming, but I think I would struggle more with the theory-based questions and would have to review my notes from discrete/data structures beforehand.  Part 4 Learning Journal.  Writing material:  For my Ethics essay, I will need to c...
Read more

CST-363 Week 1

  Relational database tables and spreadsheets look similar with both having rows and columns.  What are some important differences between the two? One of the biggest differences is that relational databases can be restored on failures. Relational databases also use SQL to retrieve and insert data. Installing and configuration a database and learning how to use it is more complicated that just reading and writing data to a file.  What are some important reasons that makes a database a useful investment of time?  Databases force data integrity and ensure it is consistent across programs. Databases can also restrict data to a program based on security rules. Databases can reduce redundancy and inconsistency.  What do you want to learn in this course that you think will be useful in your future career?  I think I would like to learn how to translate English into valid SQL queries/maybe accessing databases asynchronously as practically every company will have a...
Read more

Week 9

 Codingbat questions Did you plan it out or throw code at it?  I gave it a few seconds of thought before throwing code at it What worked? Java methods were pretty easy to understand coming from C++ and Kotlin. What DID NOT work? Some of the methods involving indexes through me off sometimes, as it is easier to visualize by writing down your steps to the solution than it is trying to do it in your head. (same with some of the problems involving edge cases) How many tries did it take?  Most only took 1-3 tries.
Read more