gistfile1.md

Algorithms, Part 1

Introduction

• Intermediate level
• Problem solving
  • Algorithms
  • Data Structures

Topics

Data Types

• stack
• queue
• bag
• union find
• priority queue

Sorting

• quicksort
• mergesort
• heapsort
• radix sorts

Searching

• BST
• red-black BST
• hash table

Graphs

• BFS
• DFS
• Orun
• Kruskal
• Dijkstra

Strings

• KMP
• regular expressions
• TST
• Huffman
• LZW

Advanced

• B-tree
• suffix array
• maxflow

Why Study Algorithms

• Intellectual stimulation
• Solve problems
• Fun and profit
• etc

Prerequisites

• Know some programming
• Knowledge of Java
• High school math

Dynamic Connectivity

Steps to solve

• Model the problem
• Find and algo to solve it
• Fast enough? Fits in mem?
• If not, figure out why
• Find a way to address the problem
• Iterate until satisfied

Problem

Given a set of N objects

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

Applications

• Pixels
• Networking
• Social network
• etc

Modelling the relation

We assume 'is connected to' is an equivalence relation

• Reflexive: p is connected to p
• Symmetric: if p is connected to q, then q is connected to p
• Transistive: if p is connected to q and q is connected to r, then p is connected to r

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

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

input.txt

10
4 3
3 8
6 5
9 4
2 1
8 9
5 0
7 2
6 1
1 0
6 7

reader.java

public static void main(Stringp[] args)
{
	int N = StdIn.readInt();
	UF uf = new UF(N);
	while(!StdIn.isEmpty())
	{
		int p = StdIn.readInt();
		int q = StdIn.readInt();
		if(!uf.connected(p, q))
		{
			uf.union(p, q);
			StdOut.println(p + ' ' + q);
		}
	}
}

Question

How many connected components result after perfoming the following sequence:

1-2  3-4  5-6  7-8  7-9  2-8  0-5  1-9

Answer: 3