CST-370 Week 5

 This week, I learned to apply the "Divide-and-conquer" technique in a sorting algorithm, known as "Quick-sort." I also learned about "Decrease-and-conquer", which is a similar technique to divide-and-conquer and is used in sorting algorithms, such as "Insertion sort" and Khan's algorithm. A third technique I learned is the "Transform-and-Conquer" technique, which is used in "Pre-sorting."

I also began to understand the efficiency of the algorithms used for Binary Tree traversal and height calculation.

Quicksort

Uses the Divide-and-conquer technique. It is "in place", like insertion sort, but not like merge sort (does not take up extra space)

Quicksort of an n-element array:

1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray < x < elements in upper subarray

2. Conquer: Recursively sort the two subarrays.

3. Combine

Example of Partitioning

Worst case: O(n^2) <- theta

Best case O(nlogn) <- theta

Binary Tree Traversal

A binary tree is a divide-and-conquer ready data structure.

3 binary tree traversals: In-order, pre-order, and post-order

Examples:

Binary Tree Height

Defined as: The length of the longest path from the root to the leaf node in the tree. Can indicate the worst-case scenario for searching. Height of empty tree = -1. Height of binary tree with one node = 0

How to calculate: Calculate the height of the left subtree and right subtree and then take the max. The height of the binary tree is one longer than the maximum height of T_l and T_r

Decrease-and-Conquer

Idea: 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

Three approaches:

    1. Decrease by a constant (e.g topological sorting)

    2. Decrease by a constant factor (e.g. binary search)

    3. Variable size decrease (e.g. Search and Insertion in a binary search tree)

Binary Search

Uses the decrease-and-conquer technique. (Size of the problem is reduced by 50%)

Example:

Search problem: Search a list of elements with a given key

Prerequisite: The list of elements must be sorted.

Basic operations:

    1. Compare the middle element with the key

    2. Reduce the size in half if further comparisons are needed.

Time efficiency: O(logn)

DAG and Topological Sorting

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

Topological sort: Ordered list with dependency. (Not just ordering values, but also maintaining dependency)

DFS Based Algo for Topological Sorting

1. Perform DFS traversal, noting the order in which vertices are popped off the traversal stack

2. Reverse order solves the topological sorting problem

3. Back edges encountered? -> Not a DAG

Example: Course pre-requisites

Topological Sorting - Khan's Algorithm

Kahn's Algorithm: Finds a topological order using the source removal approach. It repeatedly identifies and removes a vertex with no incoming edges. (Uses decrease-and-conquer technique)

Basic operations:

    1. Calculate the "in-degree" of each vertex. (The number of incoming edges)

    2. Push the vertices with "in-degree" zero into a queue.

    3. Remove a vertex from the queue.

        a) Decrease "in-degree" by 1 for it neighboring vertices.

        b) If the "in-degree" of a neighboring vertex is reduced to zero, add the vertex to the queue.

    4. Repeat the above step until the queue is empty.

Presorting

Solving the Element Uniqueness Problem.

Brute force algo: Using brute force to compare all pairs of elements requires O(n^2)

Presorting-based algorithm

    1. Sort by an efficient sorting algo (e.g. merge sort)

    2. Scan array to check pairs of adjacent elements

Efficiency: O(nlogn) + O(n) = O(nlogn)

Searching with presorting (Searching for a given K in A[0..n-1]

    1. Sort by an efficient sorting algorithm

    2. Apply binary search

Efficiency: O(nlogn) + O(logn) = O(nlogn)