Assignment 4  William Beachley
William Beachley
Assignment 4
1. Name the two most important things/concepts which you
learned from the reading the chapter "The Architecture of
Complexity"
One concept is that in problem solving, it is
important to have
a description or a visualization of the solution first, and then
work at finding a process that arrives
at the solution. The second is the importance of looking for
redundancy and thus simplifying the problem. In other words, look
for ways to transform a complex problem into a simpler problem that
already has a known process for solving it.
1.1. give
a one paragraph explanation why you consider
these concepts important
These concepts are important because as problemsolvers, we don't
want to reinvent the wheel. It seemed like the point of the paper was
to provide a common way of looking at problems regardless of context.
One must build solutions from elementary and known subsystems.
Although systems can in most cases be decomposed infinitely down
to atomic matter, this is often not necessary in every context. It is
important to find a suitable base element for a given context and any
subsystems below that element are irrelevant. I think the author really
wanted to get across that the process of problem solving can be
generalized and applied to any context and this is important for problem
solvers that are working in contexts that may be entirely unfamiliar to them.
1.2. are
the concepts relevant to your work, to your interest?
if yes, why?
These concepts are important to any computer scientist and really any
kind of scientist for that matter. These concepts can be applied to
programming to produce good top down design. These concepts are
the foundation of the "divide and conquer" strategy of computer
programming. They are the foundation of the scientific process. I
would say they are relevant to anyone's work. Even writing an good
paper or essay requires these concepts for good organization of thought.
2) The
Mutilated "8x8" Matrix
The Problem:
The next
page shows you a mutilated "8x8" matrix (the two opposing
corners cut out) and a domino block. One domino block covers
exactly two fields of the 8x8 matrix.
Note: It
is straightforward that one can use 32 domino blocks
to cover a complete "8x8" matrix.
Question:
Can one cover the mutilated 8x8 matrix with 31 domino
blocks?
Remark:
the major objective of this assignment is that you spend some
effort trying to solve this problem and answering the questions below?
It is not so important that you will succeed solving the problem!
Also: engage
in some collaborative efforts solving it
Please
do the following (please structure your answer accordingly):
1. try
to find an answer to this problem! document briefly your
thinking including all the important intermediate steps and
failing attempts (i.e., create a thinkaloud protocol?
At
first I tried to do it by eyesight and found that there was no
obvious solution to the problem. Of course I knew it would not be
that easy, but it is a good place to start when assessing a problem.
Then I broke the matrix up into
four 4X4 matrices with two of them mutilated. I first worked on
the upper left submatrix, a mutilated one and realized that I
could not solve it without pushing half a domino into the lower
left or the upper right submatrix, putting those in the same
boat as the upper left. This of course causes two half dominoes
to be pushed into the lower right submatrix which does not
even things out. I discovered when going down to the 2X2
level that the mutilated squares propagate the halfdomino
throughout the matrix causing a failed attempt every time.
I came to the conclusion that the matrix was not decomposable
into separate solvable subsystems which does not prove the
problem unsolvable, but does prove that the problem's complexity
cannot be reduced.
2. which
resources did you use to solve the problem?
I
used pen and paper attempts and trial and error to attempt
to solve the problem. I also looked at what others had come
up with in order to validate my own conclusions.
3. which
process did you use?
I
used the process of trial and error and the process of divide and
conquer. I tried to look at the problem from different perspectives.
4. which
practice (of you or others) did you use?
I used the practice of pen and paper and trying
the draw the
problem in different ways to make a possible solution clearer.
5. could
computers be useful to solve this problem?
Computers
would be useful in speeding up the process of trial and
error, trying every possibility, but I think a computer would discover
the same conclusion I found.
6. what
have you learned solving the problem: in general
and for our course?
I
learned that what I said above before I started this problem may not
always be valid. We don't always have an end state from which we
must produce a path to that end state. In this case, if we had an end state,
the path to it would be entailed by that end state. I have also learned that
computers are not always the best tool for a given problem. Sometimes
drawing visualizations of a problem by hand is faster and provide more
insight into the problem. With a pen and paper I am focusing on the
problem and not on distracting things like how to write a program to
do it, how to draw a subdivided representation in Photoshop or the like.
Doing this type of thing on a computer adds a lot of frustration whereas by
hand I could enjoy the pure exhilaration of working on the problem.
7. what
have you learned not being able to solve the problem:
in general and for our course?
I
have learned that it is hard to convince myself that there is no solution
without trying every possibility. I have not seen a problem like this before
and could not find any information on the internet about the problem
except for previous class websites for the same course. I have learned
much more in the past about ways in which to attack and solve problems,
but very little about how to NOT solve a problem.
