ES242. Data Structures and Algorithms I. Quiz 04

ES242. Data Structures and Algorithms I.

Quiz 04

Issued: 24 Jan, 2023

Problem 1. Divide by two

Let \(n\) be a number given in decimal notation. Divide the number by two and push the remainder of each division onto to a cardstack until the number is reduced to 0. Then we pop all elements from the bottom. What is the output?

The representation of \(n\) in binary.
The reverse of the representation of \(n\) in binary.
Meaningless and has nothing to do with \(n\).

Problem 2. Stacks I

You have a sequence \(\ell\) of A’s and B’s. You initialize an empty stack S.

You read the sequence \(\ell\) from left to right. Every time you see an A, you push 0 on to S. Every time you see a B, you pop from S. You never had to pop from an empty stack, and at the end, your stack is empty. Which of the following is true?

The sequence \(\ell\) does NOT have an equal number of A’s and B’s.
The sequence \(\ell\) started with ABBA.
For any \(1 \leq k \leq \ell\), if you read first \(k\) entries of the sequence \(\ell\) the number of A’s is at least the number of B’s.
For any \(1 \leq k \leq \ell\), if you read first \(k\) entries of the sequence \(\ell\) the number of B’s is at least the number of A’s.

Problem 3. Stacks II

You have a sequence \(\ell\) of A’s and B’s. You initialize an empty stack S.

You read the sequence \(\ell\) from left to right. Every time you see an A, you push 0 on to S. Every time you see a B, you pop from S. At some point, you had to stop because you were trying to pop from an empty stack. Which of the following is definitely true?

The sequence \(\ell\) has an equal number of A’s and B’s.
The sequence \(\ell\) started with ABBA.
For some \(1 \leq k \leq \ell\), if you read first \(k\) entries of the sequence \(\ell\) the number of A’s is strictly more than the number of B’s.
For some \(1 \leq k \leq \ell\), if you read first \(k\) entries of the sequence \(\ell\) the number of B’s is strictly more than the number of A’s.

Problem 3. Navigate this apartment

Consider the floor plan shown below of a 5-room apartment.

Can you find a continuous line that pass through each door exactly once? The line does not have to end where it started. Note that there is space to move around the big enclosing rectangle.