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 -231 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