# Programming Assignment #1 Solution

\$30.00

Category:

## Description

• 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

my class1.py

my class2.py

my class3.py

problem.py

another problem.py

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

error: Content is protected !!