-

Information and Logic

IST 4
Spring 2018

Challenge Problem

Challenge Problems

course policies (pdf)| reference books (pdf)

  • Problem [due may 24, 2018] The programming challenge is to implement a function that retrieves the minimum number of steps it takes to generate a string using only tandem duplications from one of the following starts strings [0, 1, 01, 10, 101, 010] as listed in problem 1a on homework one. Once you have completed this you will realize that for large strings it takes a lot of time for your program to grow as the search space becomes much larger. The challenge is to think of ways to optimize this generation process and argue why your solution is good. Please in your solution describe your algorithm and approach. Discuss pros and cons and what things you like/dislike about your algorithm. It is mandatory to use Python3 as your programming language. Attached below is the helper code and guidelines that may be useful

  • Programming Challenge

  • Helper Codes