Indiana University Bloomington

School of Informatics and Computing

Homework Page
I101 Home

 

Informatics I101: Introduction to Informatics
  
I101 Informatics Homework 1

Summer 2007, Bloomington

  All Material Copyrighted 2002, M.M. Dalkilic and M.P. Hottell and may not be used in any form without express permission from the authors.

 

Objectives

  • To better understand more formally what is a problem and solution
  • To employ some of the techniques used in identifying the correct problem
  • To explore some new kinds of problems

Tasks

Deliverables

  • Typed answers, pages numbered (and stapled if more than one page)
  • The footer should include your NAME, EMAIL, and date
  • The header should include "Assignment 1 I101 Summer 2007", and "Hottell". 
  • Make sure you spell check!
  • If any of the information above is missing, you have a good chance of not getting credit for the assignment

Due Date and Location

       Due date for the written portion is Monday, May 22nd, by 11:45PM in the Assignment 1 dropbox on Oncourse.

Completion Time

     About 2 hours

Academic Honesty and Intellectual Integrity

       You must work on your assignments by yourself.  You may discuss the questions, but that is all. Here is the academic honesty policy.

Introduction

When solving a problem, the first step is to correctly identify the problem. People generally have an easy time figuring out when something is wrong--but figuring exactly what is wrong is much more difficult.

What exactly do we mean by "problem?" Looking in a good dictionary is always good start--the Oxford pocket English dictionary states that a problem is a "doubtful or difficult matter requiring a solution," and "something hard to understand or difficult to accomplish." This doesn't help us very much. If we think about it a bit, problems have to do with the states of affairs--that is, those things that are true at particular point in time. A problem is when you want to change the state of affairs. A problem is a place you need to be, but aren't.

Definition A  problem is when you want to change the state of affairs.

Suppose a student has a 3.2 GPA, but wants a 3.7 GPA. The problem is then to somehow move from the state of affairs where his GPA is 3.2 to a state of affairs where his GPA is 3.7. Fig. 1 illustrates this point. You see a student and three facts. Each fact is depicted as a balloon with a fact attached to its tail. The current state of affairs has among its facts the condition that the student has a 3.2 GPA. But the student would like to have a higher GPA: a 3.7. This is a possible state of affairs and lies somewhere beyond the current state of affairs.

Figure. 1 States of affairs are things that are true. In this illustration, the student has a little more than $23 in his savings account, his GPA is 3.2, and he's not ready for your next exam. Each balloon tale represent has one of these single facts. But the student would like to have a 3.7 GPA. This lies somewhere outside the current state of affairs--somewhere in the possible states of affairs. This is  the problem.

A problem is a set of conditions that you'd like or need to change. A solution, then, is how to change the state of affairs. A solution is a way to get to the place you want to be.

Definition A solution to a problem is how to change the state of affairs.

Figure 2. A solution to the problem is a change of the state of affairs. Notice the student has "solved" his problem--and now indeed has a 3.7 GPA. Shouldn't the other facts have migrated to the new state of affairs? Since they don't really play a role, their presence, or more appropriately absence, doesn't affect the solution.

In Fig. 2, observe a solution--the student has changed the state of affairs (we're not so much concerned with the particulars of how just yet) to achieve a 3.7 GPA.

If solving problems were that easy--a single path extending from where you are, to where you want to be, problems wouldn't be difficult. But as the dictionary definition painfully reminds us, problems are difficult. Why? Because we have to identify the correct problem. And to say there's a lot to choose from would be an understatement! There's an infinite number of problems. There's also an infinite number of solutions.

Figure 3. What the choice really looks like. The first step is picking out the real problem

Fig. 3 gives you a sense of what solving problems is really like--lots of potential choices of states of affairs to start from and lots of potential choices of states of affairs to change to.

This is a difficult task at best--but we'll provide you with some excellent techniques to help you--both define the problem and discover the best solution. Let's now look at two examples to highlight the point of this section.

When elevators were novel conveyances, people felt the elevators ran too slowly. Since elevators move using weights and pulleys, it's unlikely that engineers would be able to make them significantly faster. Before

Figure 4. People waiting for an elevator believe they are waiting for an inordinate amount of time. The problem, apparently, is to move from slow elevators to fast elevators. Unfortunately, this isn't possible--engineers can't make the elevators travel any faster (the big red `X' means this solution can't happen).

you read any further, take a moment to decide what the problem in this case would be. When you're done, look at Fig.4 to confirm what you think. So, we can't speed up the elevator. But what's remarkable is that the elevator's speed is not the problem. The real problem has to do with waiting. Take a look at Fig. 5. Putting up mirrors solves the problem! This not-so-obvious solution would never had been possible if the right problem hadn't been identified.

Figure 5. The speed of the elevator isn't the problem--it's the perception of slowness. More to the point, people simply have time to think about waiting for the elevator. Whew! Putting in mirrors solves the problem. People forget about thinking about waiting for the elevator. And before they know it, the elevator appears.

The next example, though not real world, does illustrate this point again: you must correctly identify the problem before you can solve it. Informatics I101 has taken a trip to the frosty north--several miles inside the Artic circle. Because of his love for penguins, the Professor wanders some few miles away accompanied by a student who happens to be an amateur ornithologist. They not only didn't see penguins, but ran into a hungry polar bear about 1/2 mile away. The bear gives chase to the two hapless hikers. Suddenly, the student stops and pulls snow shoes out from his backpack and asks the Professor, "Prof. D., did you submit our semester grades yet?"

The bemused Professor replies, "Uh--Yes." And with some trepidation says, "You won't be able to outrun that bear in those snow shoes."

The student smiles and replies, "I only have to outrun you."

Again, what turns out to be the real problem--seeing who can outrun whom (and consequently its solution)--isn't what you'd necessarily expect. Being able to see the real problem and identifying a novel way of solving it in this fashion is called divergent thinking or "thinking outside the box."

1. Definitions, Terms and Concepts

a) We are adding "structure" to problem solving.  How does adding structure help? (hint: verification, re-employ)

b)  A solution is a path between the current state of affairs to a possible state of affairs.  What does this mean? What can you can you say about where the path might lead to? 

c) Define "palliative."  In terms of path, what does palliative mean?

d) What is a truth table? What is a contradiction?

e) What is bias? What are the different types of bias? What type of bias should we use to solve problems?

2 Just Another Problem to Solve

[Adapted from Mathematics and Plausible Reasoning (Vol. I), G. Polya .] From your first week of I101 you've learned that we do a lot to confuse ourselves when faced with problems, e.g., bias .  Suppose you're faced with this information:

1.

AMTUVWY

2.

BCDEK

3.

NSZ

4.

HIOX

5.

FGJLPQR

There are five lines of uppercase letters.  Your job is to place each of the 26 lowercase letters a,b,c,...,z on one of the five lines.  A letter can only be used once.  Next, place the 10 digits 0,1,2,...,9 on one of the five lines (just like the lowercase letters).  After you've completed these two tasks, write a concise paragraph about how you chose to put the letters and digits where you did.  I'm interested in a convincing, novel argument.

 3 Big League Bonanza

The number of people watching professionally sports, e.g., baseball, football,
basketball, has declined dramatically the last decade. For example, the “Subway
Series” that pitted the New York Mets against the New York Yankees received a 12.1
rating. This means that little more than 12 percent of all the television households in
the US watched the game. This is more than a threefold decline from two decades ago.
Assume you’ve been hired by baseball’s commissioner to help solve this problem.
  1. Write a problem statement you believe captures the problem.
  2. Using rephrase, converse/negation, narrowing, broadening, and treasure hunt technique, rewrite the problem state. Give two examples for each technique.

4 Earliest Informatics Device

The figure to the right depicts a portion of an reindeer's antler from ~20K BCE, found in Landes, France. It's probably an early IT tool. In a concise paragraph, give your best account of what it was used for. You can't suggest this item was any kind of decoration--like jewelry.

 

5 Digital vs. Analog

a) Is the temperature of a can of Diet Coke digital or analog?

b) When you write down the temperature, is it digital or analog? 

c) Is "happiness" digital or analog?

d) When you say you're happy, is it digital or analog? 

e) Are propositional statements digital or analog?

6 Weighted Ranking

Here are five vehicles:

           

Vehicle

Price

Type
Toyota Prius $$$  (small car, new)
Honda Civic $ (small car, used)
Ford Explorer $$ (med. SUV, used)
Cadillac Escalade $$$$ (large SUV, new)
Chevy Silverado $$$ (med truck, new)

Using Weighted Ranking, order the vehicles according to the best buy.  You should begin with at least five criteria, then using pairwise comparison, end up with only three.

7 Truth and Nothing But the Truth

  1. Give the truth table for not (A and not B).
  2. Give the truth table for (A and B) or not B.
  3. How do you tell if two propositional statements mean the same thing?
  4. Give the circuit for (A and B) or not B.
  5. Give the propositional statement and the truth table for the circuit in Fig. 1. What is the propositional statement for the equivalent minimized circuit?
    6.                              

    Fig. 1. A circuit.

8 Number Base Fun

  1. Why is it that modern mathematics are performed using Hindu-Arabic numberals and not number systems like the Roman or Egyptian systems?
  2. Perform the following number base conversions:
    1. 101010112 to decimal
    2. 678 to decimal
    3. B916 to decimal
    4. 6310 to hexadecimal
    5. 4710 to binary
    6. 5910 to octal
    7. 343 to binary
    8. 101101112 to hexadecimal
    9. 2F16 to octal