Description
0 Instructions
Submit your work through Canvas. You should submit a tar file containing all source files and a README for running your project. Don’t submit other files (e.g., input or output files).
More precisely, submit on Canvas a tar file named lastname.tar (where lastname is your last name) that contains: • All source files. You can choose any language that builds and runs on ix-dev.
• A file named README that contains your name and the exact commands for building and running your project on ix-dev. The README should be able to be read on ix-dev with the cat utility. If the commands you provide don’t work on ix-dev, then your project can’t be graded and you’ll be required to resubmit with a significant penalty.
Here is an example of what to submit:
hampton.tar README my class1.py my class2.py my class3.py problem.py another problem.py …
README Andrew Hampton
Problem 1: python problem1.py input Problem 2: python problem2.py input …
Note that Canvas might change the name of the file that you submit to something like lastname-N.tar. This is totally fine!
1
The grading for the assignment will be roughly as follows:
Task Points Problem 1 10 pass given sample test case 3 pass small grading test case 3 pass large grading test case 4 Problem 2 13 pass given sample test case 3 pass small grading test case 5 pass large grading test case 5 Problem 3 13 pass given sample test case 3 pass small grading test case 5 pass large grading test case 5 Problem 4 14 pass given sample test case 4 pass small grading test case 5 pass large grading test case 5 TOTAL 50
Passing a test case means that the diff utility on ix-dev produces no output. Furthermore, passing the given sample test case requires actually completing the problem (not, for example, just hardcoding the given output).
2
1 Applications
Problem 1. Making a Collage You want to construct a note by cutting out words from a magazine. First, though, you need to write a computer program that takes a list of words in a magazine and a list of the words you want to use in your note and answers whether it’s possible to construct the note from the magazine.
Your program should take a single command-line argument, which will be a filename. The input file will contain exactly three lines. All words will contain only letters. The first line is two integers x y separated by a space, with 1 ≤ x,y ≤ 106. The first integer x denotes how many words are in the magazine. The second integer y denotes how many words are in the note.
The second line contains a space-separated list of the words in the magazine. The third line contains a space-separated list of the words in the note. The lists are case- and repetition-sensitive.
Your program should output (to STDOUT) the word YES if it’s possible to construct the note from the magazine or NO if it’s not possible, followed by a single newline.
The runtime complexity of your solution should be O(x+y). Hint: to achieve this runtime, use a hashtable.
Example input file:
5 2 Hello Cat Dog World Fish Hello World
Example output:
YES
Example input file:
5 2 Hello Cat Dog world Fish Hello World
Example output:
NO
Example input file:
5 3 Hello Cat Dog World Fish Hello Hello World
Example output:
NO
This problem is based on an example from the book Cracking the Coding Interview (McDowell).
3
Problem 2. Brackets Write a program to check whether a string of brackets is well formed. That is, given a string containing only the characters [ ] ( ) { } < >, we call it well formed if and only if it meets the following criteria:
• Each bracket is matched. For every open bracket (, [, {, and < there is a corresponding closing bracket.
• The substring contained within each matched pair is also well formed. For example, <[(])> is not well formed because the substring contained within the [ ] matched pair, which consists of the single character (, is not well formed.
Your program should take a single command-line argument, which will be a filename. The input file will contain strings of brackets. The first line of the input file will be an integer 0 ≤ N ≤ 104 giving the number of strings. Following will be N lines, each containing a string of brackets having 1 ≤ length ≤ 105. For each given string, print YES if it is well formed or NO if it is not well formed.
All output should be to STDOUT. Each piece of output should be separated by a newline.
You should implement a solution that has linear time complexity in the string length.
Hint: use a stack.
Example input file:
4 ()()[]<>{} ([<()>]) ([) ([)]
Example output:
YES YES NO NO
4
Problem 3. Restaurant Cycle You are extremely hungry. Fortunately, you have found a group of N restaurants conveniently arranged in a circle, and you intend to eat all of the food at all of the restaurants.
However, you have to be a little bit careful. The restaurants are numbered 0 through N −1 and, since the restaurants form a circle, you can only travel from restaurant i to restaurant i + 1 (mod N). Since it takes some amount of energy to get from one restaurant to the next, it’s possible that you could get stuck before completing the restaurant cycle! You want to figure out at which restaurant to begin so that you can travel to all of them.
Write a program to solve this problem. The program should take a single command-line argument, which will be a filename. The input file will contain information about the restaurants. The first line of the input file will be an integer 0 ≤ N ≤ 105 giving the number of restaurants in the circle. Following will be N lines, each containing two integers 1 ≤ E, D ≤ 109 separated by a single space. The integer E is how much energy you will receive by eating at that restaurant. The integer D is how much energy is required to travel to the next restaurant.
Wherever you choose to begin, you will start with zero energy. If at any point the energy required to travel to the next restaurant is greater than your current energy, then you cannot complete the cycle.
Output to STDOUT the restaurant number where you will start that allows you to travel to every restaurant in the circle. If there is more than one such restaurant, output the one with the smallest restaurant number. You are guaranteed that in every test case there will be at least one solution.
Note: because you are so hungry, your stomach has infinite capacity for food.
Your solution should have linear time complexity in the number of restaurants. Hint: use a queue to organize the restaurants into a cycle.
Example input file:
4 4 2 1 11 10 3 18 6
Example output:
2
Explanation: There are 4 restaurants in the circle.
If we start at restaurant 0, then we get 4 energy and must spend 2 energy to get to the next restaurant. Then at restaurant 1, we get 1 energy (so we have 3 energy) but must spend 11 to get to the next restaurant. Since the distance is greater than our energy, we cannot continue.
Similarly, we can’t start at restaurant 1.
If we start at restaurant 2, we get 10 energy and must spend 3 energy to travel to the next restaurant. Then at restaurant 3, we get 18 energy (so we have 25 energy) and must spend 6 to get to the next restaurant. Next is restaurant 0 (since the restaurants form a circle), where we get 4 energy (so we have 23 energy) and must spend 2 to get to the next restaurant. Finally, at restaurant 1 we get 1 energy (so we have 22 energy) and must spend 11 to get to the next restaurant. We have enough energy to complete the circle, so
5
beginning at restaurant 2 is a valid solution.
Using similar reasoning, we see that starting at restaurant 3 also produces a valid solution.
Since we want the smallest restaurant number that gives a valid solution, we output 2.
6
2 Implementation
Problem 4. Min Heap Implement a binary heap that maintains the min heap property. Recall that the min heap property means that smaller keys have higher priority. You should build the heap on top of a builtin array, list, or vector type, but don’t use a builtin heap. For example, in Python you’ll probably want to build your heap on top of the list data type, but you’re not allowed to use the heapq or Queue modules.
Your heap data structure must implement the following methods with specified runtime:
insert(X): Takes a single integer argument X and inserts the key X into the heap. O(log n)
remove(): Removes the key with highest priority and returns it. O(log n)
look(): Returns the key with highest priority. Does not alter the heap. O(1)
size(): Returns an integer, the number of keys in the heap. O(1)
is empty(): Returns a boolean indicating whether the heap is empty. O(1)
to string(): Returns a string, a space-separated list of the keys in the heap in order of the underlying array. O(n)
Write a driver program that takes a single command-line argument, which will be a filename. The input file will contain instructions for heap operations. The first line of the input file will be an integer 1 ≤ N ≤ 105 giving the number of instructions. Following will be N lines, each containing an instruction. The possible instructions are: insert X, where −105 ≤ X ≤ 105 is an integer: insert the key X into the heap. There is no output. remove: Remove the key with highest priority. Output the removed element. If the heap is empty, output HeapError.
print: Output the contents of the heap separated by a single space in order of the underlying array. If the heap is empty, output Empty.
size: Output the number of keys in the heap.
best: Output the key with highest priority. Does not alter the heap. If the heap is empty, output HeapError.
All output should be to STDOUT. Each piece of output should be followed by a newline.
Example input file:
12 print best insert 3 insert 2 insert 1 print size best
7
remove remove remove remove
Example output:
Empty HeapError 1 3 2 3 1 1 2 3 HeapError
Explanation:
Instruction Output print Empty best HeapError insert 3 none insert 2 none insert 1 none print 1 3 2 size 3 best 1 remove 1 remove 2 remove 3 remove HeapError