COSC 350: Data Structures
Feb. 6, 2009

Today we began by going over the homework.

Next we moved on to the Union-Find Algorithm. (Do not obsess over this set of algorithm. While you should certainly understand how the first couple of version work, it was really included to introduce you to some of the general concepts and approaches used in this course, things like alternative algorithms, tradeoffs, and how structuring a solution affects efficiency. These are all ideas we will return to again and again.)

Union-Find determines if different nodes in a graph are connected. This is a yes/no question. We aren't asking for the path, number of path, etc.---just does it exist?

Informally introduced terms: graph, node, edge, path, connectivity

Basic idea:
Union() builds sets of connected nodes (or separates nodes into sets where all the nodes in a set are connected.
Find() takes two nodes and determines if they are in the same set.

Translating Code

Next, we discussed the algorithm in detail looking at examples and we translated code from C++ into Python. Here is one version of the code from your text.

Program 1.1
Program 1.2
Program 1.3

(These may be superficially different from the code created in class.)

Three points about C/C++:

1. C/C++ uses arrays which requires a declaration. Pythons nearest equivalent is a list which can change dynamically.

2. for (<init>; <test>; <change>) { <body> }

This is like a while loop where <init> is done before the while, <test> is done each pass, and <body> and <change> are the operations within the while.

3. while (<statement>) {<body>}

This construct allows C/C++ to do an assignment within the while test. You'll need to separate these actions in Python.

Recap or (Iterative) Steps In a Solution

1. Understand Problem
2. Simple solution
3. Refine solution
4. Abstract data type
5. Performance analysis

Homework

Your text only gives the Union portion of the code for Union-Find. For homework, give the code for Find() for programs 1.1 and 1.2.

This page was created by Joe Sloan.
It was last modified around: 6 February 2009
Send mail to: sloanjd@wofford.edu

COSC 350: Data Structures Feb. 6, 2009

Translating Code

Recap or (Iterative) Steps In a Solution

Homework

COSC 350: Data Structures
Feb. 6, 2009