Session 204: 9:00 AM - 9:45 AM: UTC 3.104
What is Computational Thinking?
Computational Thinking is a set of problem solving skills that allow you to create algorithms. At the heart of Computer Science is the building of algorithms - the step-by-step solutions to problems with or without computers. These are four key components of Computational Thinking:
We will do a set of puzzles to improve our Computational Thinking.
1. A farmer is on a riverbank with a wolf, a goat, and a head of cabbage. He wants to transport all three to the other side of the river in a boat. However, the boat has room for the farmer and just one other item (the wolf, or goat, or the cabbage). How can he safely carry all three without the wolf eating the goat or the goat eating the cabbage?
2. Four people have to cross a foot bridge at night. It is dark and they have one flashlight. A maximum of two people can cross the bridge. Any party that crosses the bridge must have the flashlight with them. The flashlight has to be carried and cannot be thrown. Person 1 takes 1 minute to cross the bridge. Person 2 takes 2 minutes to cross the bridge. Person 3 takes 5 minutes to cross the brige. Person 4 takes 10 minutes to cross the bridge. What is the minimum amount of time it will take for the four people to cross the bridge?
3. A student in elementary school is counting from 1 to 1000 using the fingers of her left hand as follows. She starts by calling her thumb 1, the first finger 2, middle finger 3, ring finger 4, and little finger 5. Then she reverses direction, calling the ring finger 6, middle finger 7, the first finger 8, and her thumb 9, after which she calls her first finger 10, and so on. If she continues to count in this manner on which finger will she stop?
4. There are eight identical looking coins; one of these coins is fake and is lighter than the others. What is the minimum number of weighings needed to identify the fake coin with a two-pan balance scale without weights? What if there are nine coins and one of them is fake. But you do not know if the fake coin is lighter or heavier. What is the minimum number of weighings?
5. Pages of a book are numbered sequentially starting with 1. If the total number of decimal digits used is equal to 1578, how many pages are there in the book? Without a calculator find the total sum of the digits in all integers from 1 to a million inclusive.
6. A magic square of order 3 is a 3x3 table filled with nine distinct integers from 1 to 9 so that the sum of the numbers in each row, column, and two corner-to-corner diagonals is the same. Find magic squares of order 3, 5, and 7.
7. A stick 100 units long needs to be cut into 100 unit pieces. What is the minimum number of cuts required if you are allowed to cut several stick pieces at the same time? Now generalize an algorithm that performs this task with the minimum number of cuts for a stick that is n units long.
8. You have 20 black balls and 10 white balls in a bag. You repeat the following operation until a single ball is left in the bag. You remove two balls at a time. If they are the same color, you add a black ball to the bag; if they are of different colors, you add a white ball to the bag. What is the color of the last ball in the bag? What if there are 20 black balls and 15 white balls to start with?
9. There ae n lockers in a hallway, numbered sequentially from 1 to n. All locker doors are closed to start with. You make n passes by the lockers, each time starting with locker #1. On the ith pass, i = 1, 2, ..., n, you toggle the door of every ith locker: if the door is closed, you open it; if it is open you close it. After the last pass, which locker doors are open and which are closed? How many of them are open?