CSE 101 Assignment 1
Due date, July 3, 2003, 9:30 AM.
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant at the beginning of class
on the due date.
There will be a 10% penalty if the homework is turned in at the discussion
session on the due date. Homework turned in later than that will not be
accepted.
-
Work Exercise 2 on
page 60
of your textbook. Just write "true" or "false"
on your paper, rather than an explanation.
-
Work Exercise 3 on
page 60
of your textbook.
Give the proof for (c), but just give the answer for the others.
-
Work Exercise 5 on
page 60
of your textbook. No explanation need be given,
just the ordered list.
-
Work Exercise 10 on
page 61
. This is a "challenge" problem, that is, it
will be a challenge to the top students.
-
Work Exercise 2 on
page 67.
More discussion.
-
Consider the following procedure (it is not written in
any particular programming language). You need to analyze the time complexity
of this procedure, in terms of the parameter n.
-
(a)
What is the asymptotic time complexity
of this procedure, in terms of the parameter n?
Give an argument to support your answer.
-
(b)
Write code for this procedure, in any programming language you wish.
Run the procedure for various values of n, including 10, 100, 1000, and 10000.
Turn in a graph
summarizing the results of your experiment, and compare your results to
your answer in part (a).
-
Use a stack algorithm to translate the infix expression
-xy+x(yz+xy) into postfix, i.e., reverse Polish notation.
Show the output file and the stack at each step.
-
All variables consist of a single letter.
-
The only operations are addition, subtraction, negation, and multiplication.
-
Multiplication has precedence over addition, subtraction, and negation.
-
Negation and subtraction are both written as "-" in infix expressions.
-
Multiplication is indicated by juxtaposition in infix expressions
just as in high school algebra,
i.e., xy is the product of x and y.
-
Negation has precedence over addition and subtraction.
-
Addition and subtraction have equal precedence.
-
If operators have equal precedence, the left-first rule applies.
-
In your postfix expression, use "~" to denote negation, and
"*" to denote multiplication.
Back to
Course Page
