DOC PREVIEW
WSU CPTS 223 - Homework

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Homework 6 (Cpt S 223)Due Date:December 5, 2012Total points: 33Feel free to use the empty space provided in this homework for filling up your answers insubmitting this homework.1. (18 points)We are given two programs A and B that use two different implementations of the un ion-finddata structure. Program A applies path compression when it p er forms each f ind() operation;whereas Program B does not ap ply path compression for its find()s.Both programs start off with the same initial u nion-find data structure shown below1:kad g bcf hyxAnd both programs perform the same s equence of f ind() operations (in the specified order):f ind(y), f ind(x), find(k), find(y), find(x), f ind(h)Calculate the number of steps each of the above find() operations takes to climb from theelement being searched to the root node. For example, the number of such steps if one wereto perform a f ind(d) on the above shown initial tree will be 1 (under both programs). Giveyour answer by filling the number of steps for each f ind() operation in th e table below :1Note that this union-find data structure contains only one tree in its forest and element a is its root. Also, notethat I have assigned character labels for each element which is okay as long as you work with the tree representation(and not the vector implementation) for this example.1Program A (w/ path compression) Program B (w/o path compression)1. find(y)2. find(x)3. find(k)4. find(y)5. find(x)6. find(h)TotalAlso in the empty space provided below, s how the final trees resulting from both programs,after the last find operation (i.e., 6. find(h)).Program A’s output union-find tree:Program B’s output union-find tree:22. (15 points)Starting with the union-find data structure shown below, show the sequence of union-finddata structures that result from applying the following operations (in that order):union(1, 2), union(3, 4), union(4, 5), union(6, 8), union(5, 8), union(1, 6), union(7, 9), union(10, 11),union(11, 9), union(1, 11).111 2 3 4 5 6789 10Answer this question for each of the three following parts separately:a) The unions are performed by height (same as union-by-rank) and finds are simple;b) The unions are performed by size and finds are sim ple;c) The unions are performed by height and finds use path compression.Note: There could be more than one correct answer sequence for each part. You j ust need togive


View Full Document

WSU CPTS 223 - Homework

Download Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?