Due: Wednesday, May 1

Collaboration: If you collaborated with someone during lab to generate data or a visualization, please acknowledge that person’s contributions clearly. You must work on the Part 1 problems individually.

Submission: Email (combined into one document using images or multiple files) by 5pm on the due date.

A Word document version of this assignment if that is easier to work with: 105-hw9

Part 1: Problems:

1) Using the ideas we have discussed in our search and sorting labs, explain why this story rings true:

The following story is taken verbatim from an email sent by Roger Dannenberg, associate research professor of computer science and professional trumpeter. “I showed up to a big band gig, and the band leader passed out books with maybe 200 unordered charts and a set list with about 40 titles we were supposed to get out and place in order, ready to play. Everyone else started searching through the stack, pulling out charts one-at-a-time. I decided to sort the 200 charts alphabetically O(N log(N)) and then pull the charts O(M log(N)). I was still sorting when other band members were halfway through their charts, and I started to get some funny looks, but in the end, I finished first. That’s computational thinking” (Wing, 2011, p. 22).

Wing, J. M. (2011, Spring). Computational Thinking—What and Why? In The Link: News from the School of Computer Science, (6), 20–23. http://link.cs.cmu.edu/files/11-399_The_Link_Newsletter-3.pdf

 

2) This is an alternate version of one of the operations circuits we discussed in class. Label the input, out, and logic gates by type. What operation does it perform?

Part 2: Lab files

Submit the following:

 

Charts for sorting experiments (insertion sort, merge sort, and permutation sort), titled and with axes labeled.

 

Labeled diagrams of your XOR, half adder, and flip flop circuits.