Programming Assignment #1 Solution

Instructions



Submit your work through Canvas. You should submit a tar le containing all source les and a README for running your project.




More precisely, submit on Canvas a tar le named lastname.tar (where lastname is your last name) that contains:




All source les. You can choose any language that builds and runs on ix-dev.







A le named README that contains your name and the exact commands for building and running your project on ix-dev. 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 signi cant 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 le that you submit to something like lastname-N.tar. This is totally ne!

The grading for the assignment will be roughly as follows:




Task


Points












Problem 1










pass given sample test case


10






pass small grading test case


5






pass large grading test case


5






print function


5






Problem 2










pass given sample test case


10






pass small grading test case


5






pass large grading test case


5






print function


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 project (not, for example, just hardcoding the given output).






Linear Data Types



Problem 1. Stack




Implement a stack using a linked list. Don't use any builtin utility classes (like a list or vector). You need to implement a linked list and use that to create your stack class.




Following the abstract data type described in the course textbook, your stack data structure must implement the following three methods with speci ed runtime:




push(X): Takes a single argument X (an integer, if it matters), and puts X on the stack. O(1)




pop(): Removes the top element from the stack and returns it. O(1)




is empty(): Returns a boolean indicating whether the stack is empty. O(1)







Write a driver program that takes a single command-line argument, which will be a lename. The input le will contain instructions for stack operations. The rst line of the input le will be an integer 0 N 104 giving the number of instructions. Following will be N lines, each containing an instruction. The possible instructions are:




push X, where 105 X 105 is an integer: For this instruction, push X onto the stack. There is no output.




pop: Pop the top element of the stack. Print the removed element. If the stack is empty, output StackError.




print: Print the contents of the stack separated by a single space, starting with the top (the element which would be removed with a pop). If the stack is empty, output Empty.




The print action should not be implementation dependent. Instead, you should write a print stack func-tion that takes a stack as an argument and accomplishes the print action using only the above three stack methods. You can, of course, also use builtin features of your language (e.g., a copy feature).







All output should be to STDOUT. Each piece of output should be separated by a newline.




Example input le:




7




print




push 1




push 2




print




pop




pop




pop




Example output:




Empty




1



 



1 StackError














Problem 2. Queue




Implement a queue using a linked list. Don't use any builtin utility classes (like a list or vector). You need to implement a linked list and use that to create your queue class.




Following the abstract data type described in the course textbook, your queue data structure must imple-ment the following three methods with speci ed runtime:




enqueue(X): Takes a single argument X (an integer, if it matters), and puts X on the queue. O(1)




dequeue(): Removes the front element from the queue and returns it. O(1)




is empty(): Returns a boolean indicating whether the queue is empty. O(1)







Write a driver program that takes a single command-line argument, which will be a lename. The input le will contain instructions for queue operations. The rst line of the input le will be an integer 0 N 104 giving the number of instructions. Following will be N lines, each containing an instruction. The possible instructions are:




enqueue X, where 105 X 105 is an integer: For this instruction, put X on the queue. There is no output.







dequeue: Remove the front element of the queue. Print the removed element. If the queue is empty, output QueueError.




print: Print the contents of the queue separated by a single space, starting with the front (the element which would be removed with a dequeue). If the queue is empty, output Empty.




The print action should not be implementation dependent. Instead, you should write a print queue func-tion that takes a queue as an argument and accomplishes the print action using only the above three queue methods. You can, of course, also use builtin features of your language (e.g., a copy feature).







All output should be to STDOUT. Each piece of output should be separated by a newline.




Example input le:




7




print




enqueue 1




enqueue 2




print




dequeue




dequeue




dequeue




Example output:




Empty




2



 



2 QueueError


















4