©2000
Ting-Yuan Wang

Due date: next Friday (11/10) before noon

Problems: 

A. Red-Black Tree 

B. Matrix-Chain Multiplication by Dynamic Programming:
    given n matrices, output multiplication results with minimum runtime.

Description:

A. Read-Black Tree:

1.The example input file format is as follows:

    ======================================
    5       <-----total number of elements (= 5 in this case)
    40     <----- the elements could be floating points
    30
    35
    25
    20
    ======================================
    The other input example is here.

2. The output file format for above example is as follows:

======================================
<35>
<25><40>
<20><30><N><N>  <----- <N> is the leaf.
<N><N><N><N><><><><>  <------------ <> is nothing.

======================================
The figure of above expression is shown here.

B. Matrix-Chain Multiplication:

1. The example input file format is as follows:

======================================
6                    <-------- total number of matrices
A1=30*35       <-------- first matrix A1 with the size 30X35
A2=35*15
A3=15*5
A4=5*10
A5=10*20
A6=20*25
======================================

2 The output file format for above example is here.

C. Requirements:

1. Write down about 2 pages of introduction and discussion sections.
2. Write down comments on your codes.
3. Follow the input and output files format.
4. It is very important that your codes can function correctly.
5. Make sure that your programs can be run on the Unix systems, and write down how to run them.

Submission:

    Please submit a paper version( before class )  and electronic version( by e-mail ) to TA.

[ Home ] [ News ] [ Lecture Outline ] [ Lecture Notes ] [ HomeWorks ] [ Project ] [ Quiz ] [ Miscellanea ]

Electrical and Computer Engineering ~ University of Wisconsin-Madison ~ 1415 Engineering Drive Madison, WI 53706-1691 ~ Tel: 608/262-3840 ~ Fax: 608/262-1267
Last modified: 11/06/00 03:02 PM by Ting-Yuan