Algorithms Part 1 - Coursera MOOC

[anitsh]

Notes from: https://www.coursera.org/learn/algorithms-part1

[anitsh]

Part I focuses on elementary data structures, sorting, and searching. Topics include union−find, binary search, stacks, queues, bags, insertion sort, selection sort, shellsort, quicksort, 3-way quicksort, mergesort, heapsort, binary heaps, binary search trees, red−black trees, separate-chaining and linear-probing hash tables, Graham scan, and kd-trees.

Part II focuses on graph and string-processing algorithms. Topics include depth-first search, breadth-first search, topological sort, Kosaraju−Sharir, Kruskal, Prim, Dijkistra, Bellman−Ford, Ford−Fulkerson, LSD radix sort, MSD radix sort, 3-way radix quicksort, multiway tries, ternary search tries, Knuth−Morris−Pratt, Boyer−Moore, Rabin–Karp, regular expression matching, run-length coding, Huffman coding, LZW compression and Burrows−Wheeler transform. Part II also introduces reductions and intractability, including the P = NP problem.

Steps to developing a usable algorithm. ・ Model the problem. ・ Find an algorithm to solve it. ・ Fast enough? Fits in memory? ・ If not, figure out why. ・ Find a way to address the problem. ・ Iterate until satisfied. How? The scientific method. Mathematical analysis.

UNION FIND Problem

Used to solve dynamic connectivity problems. Quick Find( eager approach ) and Quick Union ( lazy approach ) algorithms are the two classical algorithms to solve this problem. The Weighted quick-union with path compression

Problem: Given a set of N objects, perform

• Union command: connect two objects.
• Find/connected query: is there a path connecting the two objects?

Solution: Create data structure and implement client

Implementing the operations:

• Find query. Check if two objects are in the same component.
• Union command. Replace components containing two objects with their union.

Union-find data type (API) Goal. Design efficient data structure for union-find. ・ Number of objects N can be huge. ・ Number of operations M can be huge. ・ Find queries and union commands may be intermixed.

Dynamic-connectivity client Goal. Connect the unconnected objects

• Read in number of objects N from standard input.
• Repeat:
  • read in pair of integers from standard input
  • if they are not yet connected, connect them and print out pair

Improvement of the algorithms is shown below

Algorithm	Worst Case Time
quick-find	M N
quick-union	M N
weighted	QU N + M log N
QU + path compression	N + M log N
weighted QU + path compression	N + M lg* N

[anitsh]

Algorithm Analysis

Bottom line. Need linear or linearithmic alg to keep pace with Moore's law.

Reasons to analyze algorithms:

• Predict performance.
• Compare algorithms.
• Provide guarantees.

Scientific method. ・ Observe some feature of the natural world. ・ Hypothesize a model that is consistent with the observations. ・ Predict events using the hypothesis. ・ Verify the predictions by making further observations. ・ Validate by repeating until the hypothesis and observations agree.

Principles.

• Experiments must be reproducible.
• Hypotheses must be falsifiable.
• Understand theoretical basis.

Empirical analysis. ・ Execute program to perform experiments. ・ Assume power law and formulate a hypothesis for running time. ・ Model enables us to make predictions.

Mathematical analysis. ・ Analyze algorithm to count frequency of operations. ・ Use tilde notation to simplify analysis. ・ Model enables us to explain behavior.

Scientific method. ・ Mathematical model is independent of a particular system; applies to machines not yet built. ・ Empirical analysis is necessary to validate mathematical models and to make predictions.

[anitsh]

Sorting

Elementary Sorts

• Selection Sort
• Insertion sort : small subarrays, <10 elements
• Shellsort is enhanced Insertion sort.
• Shuffle is a good example for algorithm.

Mergesort Java sort for objects, when memory is not of problem.

Quicksort Java sort for primitive types, when memory is to be considered.

Java System Sorts

Arrays.sort()

• Has different method for each primitive type.
• Has a method for data types that implement Comparable .- Has a method that uses a Comparator .
• Uses tuned Quicksort for primitive types; tuned Mergesort for objects.

Q. Why use different algorithms for primitive and reference types? Basically depends on the space availability, and a choice that the programmer has to make.

System sort: Which algorithm to use?

Many sorting algorithms to choose from: Internal sorts. ・ Insertion sort, selection sort, bubblesort, shaker sort. ・ Quicksort, mergesort, heapsort, samplesort, shellsort. ・ Solitaire sort, red-black sort, splaysort, Yaroslavskiy sort, psort, ...

External sorts. Poly-phase mergesort, cascade-merge, oscillating sort.

String/radix sorts. Distribution, MSD, LSD, 3-way string quicksort.

Parallel sorts. ・ Bitonic sort, Batcher even-odd sort. ・ Smooth sort, cube sort, column sort. ・ GPUsort.

Reasons

Applications have diverse attributes. ・ Stable? ・ Parallel? ・ Deterministic? ・ Keys all distinct? ・ Multiple key types? ・ Linked list or arrays? ・ Large or small items? ・ Is your array randomly ordered? ・ Need guaranteed performance?

Binary Search Tree Algorithm Usage