Information and Logic

IST 4
Spring 2017

Challenge Problems

Challenge Problems

course policies (pdf)| reference books (pdf)

  • Challenge Problems Policy and Motivation (pptx)

  • Challenge Problems Modified Policy (pptx) [may 16, 2017]

  • Problem 1: [may 26, 2017] The first coding 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.

  • Problem 2: [may 29, 2017] In homework 3, you found a circuit for computing parity of 2 and 3 variables with 4 and 8 m-boxes respectively. By using the same idea, you can compute parity of 4 variables with 12 m-boxes. Is 12 is the smallest size of a circuit of m-boxes for computing the parity of 4 variables? What is the smallest circuit for parity of 4 variables? You can use a formal proof or an algorithm/code to check all possible circuit configurations.