# python辅导 | CS 602 Algorithm Design and Implementation

python算法设计与实现

CS 602

Algorithm Design and Implementation

Assignment 2

[Question 1] Metal Melter

A metal recycling company often needs to melt metal blocks of the same type but possibly

different sizes together. Every step, a machine, called metal melter, takes two blocks of the same

type from a pool and puts the melted block back to the pool. The melting processes cost energy,

which is equal to the sum of the weight of the two blocks in the unit of kilojoule. Given a pool of

metal blocks, the machine operator can choose any sequence to melt the blocks and put the

melted block back to the pool, until there is only one block left for each type in the pool. For

example, if a pool of steel blocks of weight 1kg, 2kg and 4kg is given, the operator can choose to

melt 1kg and 2kg first, or to melt 1kg and 4kg first, or to melt 2kg and 4kg first. If he melts 1kg

and 2kg first, 3 kilojoules are spent to produce a 3kg block, and then melts 3kg and 4kg together,

which costs 7 kilojoules. A total of 3 + 7 = 10 kilojoules is spent on this whole process. If he

starts with melting 2kg and 4kg first, the machine spends 6 kilojoules in the first step, and 7

kilojoules in the second step, which gives 13 kilojoules in total. The company would like to

minimize the energy spent in the melting process, the first option is thus chosen. However, they

do not know how to decide on the melting sequence and need your help.

Implement an algorithm with appropriate data structure for the function metal_melter.

Please also state and justify the time complexity of your algorithm as comments in your code.

Test inputs begin with the number of lines. Each line contains a list of integer pairs, the types and

weights of metal blocks separated by ‘:’. The length of each list is between 2 and 5000, weights

are at most 400, and the type indicator of the blocks is between 1 and 50. For each list, output

one single integer indicating the minimum possible amount of energy to spend in kilojoules. You

may import Python libraries which are commonly used, but you are not supposed to ask what the

right library is, as this question tests you on choosing the appropriate data structure.

Sample Input

2

1:2 1:4 1:1

2:6 2:5 1:2 1:4 2:4 2:7

Sample Output

10

50

[Question 2] Mirror a Binary Tree into a Binary Search Tree

In this question, you are asked to convert a binary tree to a binary search tree with the mirrored

structure. A mirrored binary tree of a binary tree is defined as follow: (1) the mirrored binary tree

of the empty tree is the empty tree; (2) the left subtree from its root in a mirrored binary tree is a

mirrored binary tree of its right subtree in the original tree and its right subtree in a mirrored

binary tree is a mirrored binary tree of its left subtree in the original tree. The mirrored binary

search tree of binary tree t is a mirrored binary tree of t and it is a binary search tree.

Please implement the conversion from a binary tree to the mirrored binary search tree. Test

inputs begin with the number of lines below. Each line describes a binary tree by a list of tree

nodes with values at itself, its left child and its right child, separated by ‘:’. Letter x represents a

null node, so a tree node with two x is a leaf node. The sequence of tree nodes is arbitrary. For

example, ‘0:x:x -1:1:-2 -2:0:x 1:x:x’ represents a 4-nodes binary tree rooted at -1, the left child is

1 and the right child is -2, where node 1 is a leaf node. For each binary tree, output the mirrored

binary search tree in pre-order traversal separated by space, ‘0 -2 -1 1’ for the above example.

Sample code is provided in the file A2Q1.py. You need to modify the function mirror_BST.

The maximum of tree height is 100 and the maximum number of nodes in a binary tree is

1,000,000. Values in the tree nodes are integers between -2

31 and 231

-1, and they are distinct.

Please state and justify the time complexity of your algorithm in comments.

Sample Input

Please refer to the file A2Q2.in .

Sample Output

Please refer to the file A2Q2.out .

Running python skeleton with sample input:

1. Open “Anaconda Prompt”

2. Go to the directory where you put the file A2Q1.py and A2Q1.in, using command cd

3. Run command python A2Q1.py < A2Q1.in

4. You may want to create a test input called my_own_test.in to design a test case for your

own program, the command would then be python A2Q1.py < my_own_test.in

5. Same applies to Question 2, so you may run python A2Q2.py < A2Q2.in