Give a recursive algorithm that takes as input a non-negative integer n and retu

Question

Give a recursive algorithm that takes as input a non-negative integer n and returns a set
containing all binary strings of length n.

Please solve Part A and B.

(3) (a) Give a recursive algorithm that takes as input a non-negative integer n and returns a set containing all binary strings of length n Here are the operations on strings and sets you can use: Initialize an empty set S (write as "S B"). o Use any explicit strings, e.g. A, 0, 1, 00110101. Add a string as an element) to a set S ("add to S Concatenate two strings and y ("ry"). Return a set Return S A looping structure that performs an operation on every string in a set S For every in S perform some sequence of steps with string a End-for Bonus points for adding elements to the returned set in order of increasing value (e.g. 000 001, 010, 011, 100, 101, 110, 111). (b) Verify that your algorithm is correct using induction. Depending on your algorithm, you may or may not need strong induction.

Explanation / Answer

Answer: (A)

BinaryStringSet(string s, int L)

Input: s is binary string which is going to be printed initailize by null, L is the length of string

Output: all binary strings of length L

Algorithm:

if L == 0, then return s

else

{

BinaryStringSet(s + '0', L -1)

BinaryStringSet(s + '1', L -1)

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.