CST370 - Week 5

  This was our fifth week in CST 370 - Design and Analysis of Algorithms.

Quick Sort

This week we discussed Quick Sort, a array sorting algorithm that uses the divide-and-conquer technique. In Quick Sort we pick a pivot (the first, last, or a random value of the array), and put all elements that are less than the pivot on the left, and all elements that are greater than the pivot on the right. Then we split the array into two halves, solving each half recursively using the same steps.

The steps of Quick Sort:

  1. We pick a pivot. This can be the first, last, or a random element of the array.
  2. We initialize i as the first element of the array and j as the second element of the array.
  3. We increment i until we find an element that is greater than the pivot.
  4. Then we decrement j until we find an element that is less than the pivot.
  5. Then we swap i and j.
  6. We repeat steps 3-5 until i and j are the same.
  7. Then we decrement j until we find an element that is less than the pivot.
  8. Then we swap j and the pivot.
  9. Finally, we split the array into two halves and solve each half.

Pseudocode and Example from Textbook

 

 

Exercise

Perform Quick sort with the following array, using '4' as a pivot.

  • 4, 3, 9, 6, 2, 5, 8, 7
We start with i = 3 and j = 7. 
   i                  j 
4,3,9,6,2,5,8,7
 
We see that i is less than the pivot. 
   i                  j 
4,3,9,6,2,5,8,7
 
We increment i and see that it is greater than the pivot.
      i               j 
4,3,9,6,2,5,8,7
 
Now we begin to check and decrement j. We see that it is greater than the pivot.
      i               j 
4,3,9,6,2,5,8,7
 
We decrement j. Again, it is greater than the pivot.
      i            j 
4,3,9,6,2,5,8,7
 
We decrement j. Again, it is greater than the pivot.
      i         j 
4,3,9,6,2,5,8,7
 
We decrement j. Now it is smaller than the pivot.
      i      j 
4,3,9,6,2,5,8,7
 
We swap the values of i and j.
      i      j 
4,3,2,6,9,5,8,7
 
We continue to increment i. We see that it is larger than the pivot.
         i  j
4,3,2,6,9,5,8,7
 
We increment i. We see that it is larger than the pivot.
            i 
            j
4,3,2,6,9,5,8,7
 
Now that i and j are the same, we start to increment j. We see that j is larger than the pivot.
         j  i
4,3,2,6,9,5,8,7
 
We decrement j. We see that j is smaller than the pivot.
      j     i
4,3,2,6,9,5,8,7

We swap j with the pivot.
      j     i
2,3,4,6,9,5,8,7
 
Now we would partition the array into two halves (lower than and greater than the pivot) and sort them in the same way.

Time Efficiency

Best Case:

  • Θ(n*logn)
  • The partition splits the array evenly. 

Worst Case:

  • Θ(n^2)
  • The input is already sorted or is reverse sorted.
  • The partition is around the min or max element.
  • One side of partition always has no elements. 

Median of Three Partitioning

While the average and best-case performance of Quick Sort is very efficient, its worst-case performance is very slow. Median of Three Partitioning attempts to fix that.

We take the values of the first, middle, and last elements of the array and sort them. Then we swap the middle element with the second element of the array, set it as the pivot, and proceed with Quick Sort (with i = 3rd element and j = n-1 element).

Example of Median of Three Partitioning:

39, 80, 16, 47, 65, 88, 95, 31, 10, 24, 73

39, 80, 16, 47, 65, 73, 95, 31, 10, 24, 88

39, 73, 16, 47, 65, 80, 95, 31, 10, 24, 88

i j 
39, 73, 16, 47, 65, 80, 95, 31, 10, 24, 88

Binary Tree

This week we discussed binary trees, which our lecture defined as divide-and-conquer ready data structures.

 

Traversal 

We also discussed three methods of traversing a binary tree: preorder, inorder, and postorder.

  • Preorder: Starting at the root node we visit the left node, followed by the right node. 
    • Root -> Left -> Right
  • Inorder: We first visit the left node, then the root, then the right node.
    • Left -> Root -> Right 
  • Postorder:  We first visit the left node, then the right node, then the root.
    • Left -> Right -> Root

 

Height

Our lecture defines the height of a binary tree as the length of the longest path from the root to the leaf node in the tree.

 

The height of a binary tree with only one node is 0, and the height of an empty binary tree is -1.

To get the height of a binary tree we get the maximum height between the right and left nodes, then add 1 to it.

Decrease and Conquer

An algorithm design technique built on the idea that problems with smaller sizes are often easier to solve:

  • Reduce a problem's instance to a smaller instance of the same problem.
  • Solve the smaller instance.
  • Extend the solution of the smaller instance to obtain the solution to the original instance.

There are three approaches in decrease-and-conquer:

  • Decrease by a constant
    • We may reduce the size of a problem by one.
    • Example: Topological Sorting 
  • Decrease by a constant factor
    • We may reduce the size of a problem by half.
    • Example: Binary Search 
  • Variable size decrease 
    • The size of the reduction varies.
    • Example: Search and Insertion in a binary search tree.

Binary Search

Binary Seach is an example of decrease-by-a-constant-factor. For a given key we compare the middle element of a list of elements. Based on whether the element is larger or smaller than the key, we can ignore eliminate half of the remaining list, then compare the key with the new middle element. 

DAG and Topological Sorting

Directed Acyclic Graph (DAG): a directed graph with no (directed) cycles.

We discussed two algorithms for topological sorting: DFS and Source Removal. For these algorithms, we consider a source node to be a node that no other node leads into.

  •  DFS: We add the source node(s) to the sort, then add each node to the sort following the DFS algorithm.
  • Source Removal: We find the source node, add it to the topological sort, and remove it. We repeat this until the graph is empty (the topological sort is complete) or until there is no source node (meaning there is a cycle, the graph is NOT a DAG).

Kahn's Algorithm

Kahn's Algorithm is another algorithm used for topological sorting. In addition to the graph it uses two data structures: a queue and an array with an element representing each vertex called 'in-degree'. In-degree measures the number of edges that are going into any given vertex.

  1. Calculate the 'in-degree' of each vertex.
  2. Put the vertices with an in-degree of zero on the queue.
  3. Remove the next vertex from the queue and reduce the in-degree of its neighboring vertices by 1. 
  4. Repeat steps 2 & 3 until the queue is empty.
  5. Our topology is the order in which the vertices were placed on the queue. 

Transform and Conquer

Our class lecture introduced the transform-and-conquer technique. This technique alters a problem instance, such as its input, before solving it. There are three major variations of transform-and-conquer:

  • Instance Simplification: Transformation to a simpler or more convenient instance of the same
    problem.
  • Representation Change: Transformation to a different representation of the same instance.
  • Problem Reduction: Transformation to an instance of a different problem for which an algorithm
    is already available.

Pre-Sorting

Our class lecture briefly discussed one application of transform-and-conquer: Pre-sorting. With pre-sorting we sort an array before moving to solve a problem using it. In many cases, the overhead and the improved performance of the sorted array will outperform the performance of the unsorted array. We can use pre-sorting as a more efficient alternative to brute force solutions. 

Comments

Post a Comment

Popular posts from this blog

Week 11

CST-338 Week 3  This week was the third week of CST-338. In this week we continued to learn more design and Java concepts. Black Box & White Box Testing This week we learned about two methodologies used for testing programs, black box and white box testing. Black box tests only focuses on the input, output, and functionality of a program, and not the internal code, logic, or structure of a program. One of the advantages of black box tests is that they are simple and easy to run. White box tests focus on the code, logic, and structure of a program. One of the advantages of white box tests is that can find logical errors, security vulnerabilities, or inefficiencies in code. Coupling & Cohesion This week we learned about coupling and cohesion in objects and methods. Coupling refers to how much different classes rely on each other. If two classes have tight coupling then they are more dependent, and changes in one are more likely to affect the other. If two classes have loose c...
Read more

Week 12

CST 338 - Week 4 This week was the fourth week is CST 338, also known as Software Engineering. In this week we began to learn about android development. Project 1 Review This week we finished a large project in CST 338. We have been asked to work with one or more classmates, and answer some questions about the project. With whom did you work? I worked with Nasser. What was your strategy for solving the assignments? My strategy was to read all of the method descriptions before I wrote any code. As I read them I created method stubs, and detailed TODO comments for each method. Afterwards, I started writing the methods from top to bottom in the assignment prompt. If a method called another method that I had not written yet, I would go ahead and write that method first so I better understood how they interacted. What was their strategy for solving the assignments? Their strategy was to follow the instructions closely as is, by following the UML diagrams and prompt as closely as possible. ...
Read more

Week 19

Image
 CST-363: Week 3 This is the third week of CST-363, also known as Intro. to Databases. Questions What is an SQL view.  How is it similar to a table? In what ways is it different? An SQL View stores a SELECT statement for later use, allowing the statement to be easily accessed in the future. A View functions similarly to a table, because SELECT statements return tables. However, the values that a View shows aren't being stored in the View, but the actual tables. This means that when one of those tables is updated, the View has to be as well. This also means that one needs to be very careful with updating or deleting rows using the View. Take a minute to think about how SQL compares to other programming languages like Java. What features are similar, and which are present in one language but not the other? The first and most clear difference is the syntax. SQL syntax is very different from that of Java and other programming languages. I think this makes basic SQL commands easy t...
Read more