Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

ES242. Data Structures and Algorithms I. Quiz 04

ES242. Data Structures and Algorithms I.

Quiz 04

Issued: 24 Jan, 2023

Back to course page

Problem 1. Divide by two

Let nnn 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 nnn in binary.
  • The reverse of the representation of nnn in binary.
  • Meaningless and has nothing to do with nnn.
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≤k≤ℓ1 \leq k \leq \ell1≤k≤ℓ, if you read first kkk entries of the sequence ℓ\ellℓ the number of A’s is at least the number of B’s.
  • For any 1≤k≤ℓ1 \leq k \leq \ell1≤k≤ℓ, if you read first kkk 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≤k≤ℓ1 \leq k \leq \ell1≤k≤ℓ, if you read first kkk entries of the sequence ℓ\ellℓ the number of A’s is strictly more than the number of B’s.
  • For some 1≤k≤ℓ1 \leq k \leq \ell1≤k≤ℓ, if you read first kkk 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.

A floor plan

  • Yes
  • No

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×