CS314 HW 1: Imperative programming and

Python

Implement the following in Python. You should not use any libraries that

do all the heavy lifting for you.

1. matmult.py: Matrix multiplication. Two matrices will be provided via

stdin, first with the number of rows and columns, followed by the matrix

values, separated by a single space:

Example input (a 2 × 3 matrix and a 3 × 1 matrix):

2 3

1.2 2.3 3.4

4.5 5.6 6.7

3 1

6.54

5.43

4.32

If the two matrices can be multiplied, print the resulting matrix in the

same format. If they cannot be multiplied, print “invalid input”. You can

assume the input will always be formatted correctly, and no matrix will

have 0 rows or 0 columns.

2. bst.py: Implement a binary search tree class (without balancing). Commands will be given one per line via stdin – i for insert and q for query.

For insert commands, you should not print any output.

For query commands, you should report “not found” if the value was not

found. If it was found, you should report “found: root” if it’s the root

element, or the sequence of left/right edges to follow to reach it otherwise,

e.g., “found: r r l r”.

Example:

i 1

i 2

i 3

q 1 # prints “found: root”

q 2 # prints “found: r”

q 3 # prints “found: r r”

q 4 # prints “not found”

3. rpn.py: Write an interpreter for a reverse Polish notation (RPN) calculator. Each line of the input corresponds to a single operand or operator.

Operands should be pushed onto a stack, and popped as needed when

an operator is encountered (and the result pushed back on the stack).

At each step, you should print the top-most element on the stack. If

an operator requires more elements than are available on the stack, you

should print “invalid operation” and ignore the operator. Operands will

be non-negative integers. You should support these operators:

+ Add two numbers

– Subtract two numbers

* Multiply two numbers

/ Divide two numbers

~ Negate one number

Example:

23 # prints 23

5 # prints 5

+ # pops 23 and 5, pushes and prints 28

Another example:

1 # prints 1

2 # prints 2

+ # pops 1 and 2, pushes and prints 3

5 # prints 5

1 # prints 1

– # pops 5 and 1, pushes and prints 4

+ # pops 3 and 4, pushes and prints 7

4. dfa.py: Write a program that reads a description of a deterministic finite

automaton (DFA) and then classifies input strings as accepted or rejected

by the DFA.

DFAs are characterized by the following 5-tuple: (Q, Σ, δ, q0, F), where Q

denotes the set of states, Σ is the alphabet of possible input symbols, δ is

the set of transition rules, q0 is the start state, and F is the set of final

(accepting) states.

2

Input to the program will be a DFA specification followed by a number

of input strings. For each input string, you should print “accepted” or

“rejected”.

Example DFA:

start q0

q1

q2

q3

a

c

b

b

a

Corresponding input, including input test strings:

states: q0 q1 q2 q3

symbols: a b c

begin_rules

q0 – q1 on a

q1 – q2 on b

q0 – q2 on c

q1 – q1 on a

q0 – q3 on b

end_rules

start: q0

final: q2 q3

ab # prints “accepted”

cba # prints “rejected”

aaa # prints “rejected”

aaab # prints “accepted”

3