|
Alan Kaminsky
|
|
•
|
|
Department of Computer Science
|
|
•
|
|
Rochester Institute of Technology
|
|
•
|
|
4486 +
2220 =
6706
|
|
Home Page
|
|
Theory of Computer Algorithms
|
|
4005-800-70
|
|
Winter Quarter 2003
|
|
Course Page
|
4005-800-70
Theory of Computer Algorithms
Module 7 Homework Assignment
Prof. Alan Kaminsky -- Winter Quarter 2003
Rochester Institute of Technology -- Department of Computer Science
Reading
Problems
Submission
Reading
-
Cormen, Leiserson, Rivest, & Stein, Chapter 22.
-
Cormen, Leiserson, Rivest, & Stein, Chapter 23.
Problems
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.1-1, page 530.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.1-2, page 530.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.1-3, page 530.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.2-2, page 538.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.2-3, page 539.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.2-8, page 539.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.3-2, page 547.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.3-9, page 548.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.4-1, page 551.
-
Cormen, Leiserson, Rivest, & Stein, Exercise 22.4-2, page 552.
-
Cormen, Leiserson, Rivest, & Stein, Problem 22-4, page 559.
-
An undirected graph has 12 vertices labeled A through L.
The graph has the following edges
with the following weights:
| Edge | | Weight |
|
Edge | | Weight |
|
Edge | | Weight |
|
Edge | | Weight |
| A-B | | 6 |
|
C-G | | 2 |
|
E-I | | 5 |
|
H-L | | 6 |
| A-E | | 5 |
|
C-H | | 6 |
|
F-G | | 3 |
|
I-J | | 4 |
| B-C | | 5 |
|
D-E | | 4 |
|
F-J | | 6 |
|
J-K | | 7 |
| B-D | | 3 |
|
D-F | | 1 |
|
G-L | | 3 |
|
K-L | | 2 |
Illustrate the operation of Prim's minimum spanning tree algorithm
on this graph, with node A as the root.
At each step, state which vertex and which edge
are added to the tree.
When finished,
give the list of edges
and the total weight of the edges
in the minimum spanning tree.
Submission
Create a PDF file named "<username>.pdf",
replacing <username>
with your Computer Science account user name.
The PDF file must begin with the following information:
Theory of Computer Algorithms
Module 7 Homework Assignment
<Your Name>
<Your C.S. Username>
<Date>
The PDF file must contain your answer for each problem above.
Make sure I can tell where each answer starts
by marking them Problem 1, Problem 2, and so on.
Send me an email message at
ark@cs.rit.edu.
In the text of your email message,
list the same information
that appears at the top of the PDF file.
Include the PDF file itself
as an attachment to your email message.
The Module 7 homework assignment is due
by 6:00pm on Tuesday, 27-Jan-2004.
The date and time at which your PDF file
arrives at my email inbox
determines whether the assignment is on time.
After I receive your email message,
I will send you an email message
confirming that I received your assignment.
(The confirmation process is not automated,
so you may not receive the confirmation message immediately.)
See the Course Policies
for further information on grading the homework assignments,
late homework assignments, and plagiarism.
|
Theory of Computer Algorithms
|
|
4005-800-70
|
|
Winter Quarter 2003
|
|
Course Page
|
|
Alan Kaminsky
|
|
•
|
|
Department of Computer Science
|
|
•
|
|
Rochester Institute of Technology
|
|
•
|
|
4486 +
2220 =
6706
|
|
Home Page
|
Copyright © 2004 Alan Kaminsky.
All rights reserved.
Last updated 21-Jan-2004.
Please send comments to ark@cs.rit.edu.