Scott on Writing

Musings on technical writing...

An Extensive Examination of Data Structures: Part 6 Available

Part 6 of my extensive examination of data structures is now available.  Part 6 provides a look at sets.  Sets are a construct used to represent an unordered collection of items, and are common in mathematics for describing properties of numbers.  Interestingly, programming languages like Pascal (and its derivatives, Oberon and Modula) provided a set construct in the language.  In fact, there is even a programming language called SETL that offers sets as first-class citizens in the language, just like strings, integers, and Booleans in C# or VB.NET.

Following a discussion of sets, along with examining how to create a Pascal-like set data structure, the article turns to a more common need - efficiently maintaining a collection of disjoint sets.  A collection of sets are said to be disjoint if there are no similar members between the sets.  There are many real-world situations where you might need to maintain disjoint sets.  For example, consider that someone gave you a list of people in a town, where each townsperson provided their father's name (assume no two people share the same name).  You are then tasked with determining who in the town is related to one another.  That is, you should be able to efficiently answer the question, “Is Tim related to Ed?”  The approach to take here is to group the townspeople into disjoint sets, where each disjoint set represents a family tree.  You can then determine if any two individuals are related by determining if they are members in the same set.  This article discusses two data structures that can be used to represent disjoint sets, and how their structure affects the efficiency of those operations being performed upon the sets.

posted on Wednesday, April 07, 2004 7:07 PM

Feedback

No comments posted yet
Title:  
Name:  
Url:
Protected by Clearscreen.SharpHIPEnter the code you see:
Comments   

Add To Your Reader

My Links

Archives

Post Categories

 

I am a Microsoft MVP for ASP.NET.
I am an ASPInsider.
<May 2008>
SMTWTFS
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

Comment Stats

DayTotal% of Total
Sunday 1866.8%
Monday 37913.9%
Tuesday 45316.7%
Wednesday 50418.5%
Thursday 53519.7%
Friday 49418.2%
Saturday 1666.1%
Total 2717100.0%

Hour1Total% of Total
12:00 AM 652.4%
1:00 AM 682.5%
2:00 AM 622.3%
3:00 AM 742.7%
4:00 AM 572.1%
5:00 AM 1033.8%
6:00 AM 1084.0%
7:00 AM 1585.8%
8:00 AM 1716.3%
9:00 AM 1475.4%
10:00 AM 1716.3%
11:00 AM 1816.7%
12:00 PM 1886.9%
1:00 PM 1696.2%
2:00 PM 1605.9%
3:00 PM 1324.9%
4:00 PM 1073.9%
5:00 PM 923.4%
6:00 PM 913.3%
7:00 PM 963.5%
8:00 PM 833.1%
9:00 PM 782.9%
10:00 PM 792.9%
11:00 PM 772.8%
Total 2717100.0%

Comments by Blog Entry Date/Time

Day Entry MadeAvg.Total
Sunday 5.54144
Monday 5.22339
Tuesday 4.28419
Wednesday 7.67637
Thursday 6.90607
Friday 5.48411
Saturday 5.33160
Total 5.842717

Hour1 Entry MadeAvg.Total
12:00 AM 5.0035
1:00 AM 1.002
5:00 AM 0.000
7:00 AM 7.0035
8:00 AM 5.35107
9:00 AM 6.32278
10:00 AM 6.47246
11:00 AM 4.41181
12:00 PM 6.88330
1:00 PM 3.00111
2:00 PM 5.41222
3:00 PM 8.64285
4:00 PM 4.0589
5:00 PM 5.92154
6:00 PM 4.52113
7:00 PM 9.67174
8:00 PM 9.80147
9:00 PM 5.05111
10:00 PM 5.4265
11:00 PM 4.5732
Total 5.842717

Learn More About Comment Stats
1 - All times GMT -8...


Blog Stats

Favorite Web Sites

My Books

My MSDN Articles