| 1.1 | Write an algorithm in English about some procedure you know, such as making a
sandwich, hanging up a poster, or taking care of a pet. Translate the English into
pseduocode. Then, go through the pseudocode a few times and expand ambiguous
statements (statements that require more than one action into multiple statements).
|
| |
| 1.2 | Describe an algorithm to wash and wax a car. You may describe the algorithm in any
way you like (flowchart, written summary, high-level description, formal
description, etc.). Once complete, modify your algorithm so that it can wash
multiple cars.
|
| |
| 1.3 | A greedy algorithm is one that takes the best local choice at every step. For
example, an algorithm for giving change starts with the highest possible
denomination and works its way down to pennies. Translate the flow chart below into
a written representation.(You will have to learn more about greedy algorithms later).
|
| |
| 1.4 | Describe an algorithm that computes the kth power of some number n. You cannot
simply raise n to the kth power, like nk..
|
| |
| 1.5 | A cable company must use cables to connect 15 homes together so that any home is
reachable by every other home through any series of cables. The company has
estimated the costs of different cable routes (see the numbers associated with each
link below). One engineer provides an algorithm that will find the cheapest set of
routes to pick. Does the engineer's algorithm work for this case? Why or why not?
Do you think you can modify the algorithm do that it does correctly find the
cheapest set of routes? If you succeed, you will have found one of the
minimum-spanning tree algorithms!
|
| 1.6 | Below is a flowchart. Perform the steps indicated in the flowchart and describe
what the flowchart is doing.
|
| 1.7 | Often times, a programmer will pretend to be a computer by keeping track of every
step his or her algorithm goes through. This process helps to uncover bugs and to
understand the algorithm. Below is an algorithm. Slowly go through every step, and
write down what the algorithm outputs.
Start
1. Let n=4
2. Let c=20
3. If ( c/2 <n ) is true, go to 4. If false, go to 3a.
3a. Output "c is: "
3b. Output c
3c. c=c-n
3d. n=2*n
3e. Go back to 3.
4. Let x=c*n
5. Let i=0
6. If (x%2=0) is true, go to 6a. If false, go to 7
6a. x=x/2
6b. Increment i by 1 (same as i=i+1)
6c. Go back to 6
7. Output c
8. Output n
9. Output i
|
| 1.8 | Describe an algorithm that computes the sum of numbers from 1 to n and does not use
multiplication. How many steps will your algorithm take for n=100? What about n=1000?
Rework the algorithm to use multiplication. Can you create an algorithm with a
constant number of steps, regardless of n?
|
| |
| 1.9 | A leap year is a year containing an extra day. Every year divisible by 4 is a leap
year. However, if the year is also divisible by 100, it will not be a leap year
unless the year is also divisible by 400. Given a start year and an end year, devise
an algorithm that determines each leap year between the start and end years
(inclusive). Assume the minimum start year is 1000.
|
| |
| 1.10 | Below are 3 mazes. Describe 2 different algorithms for solving a maze. Discuss
advantages and disadvantages of each algorithm. Then, look at the maze and
predict which algorithm will exit first. See if you predictions were correct by
applying your algorithms to the mazes.
|
| 1.11 | Bank checks and postal addresses are just two applications using handwritten
recognition. Describe an algorithm that can interpret the handwritten capital
characters: A, B, C, D and E.
|
| |
| 1.12 | An algorithm is a set of steps used to transform input data into some form of output.
A data structure is a construct to organize information. Why do you think the
discussion of algorithms usually involves data structures?
|
| |
| 1.13 | Suppose you have 4 points, p1, p2, p3 and p4, on an xy coordinate plane. You have
access to the location of the points. For example, to add the x and y coordinates
of p3, you can say "p3.x + p3.y." Write an algorithm that determines if these 4
points form a square.
|
| 1.14 | Advanced calculators have a feature to find the minimum value y for an equation
y=f(x). Below are graphs and an algorithm. Describe how the algorithm can find
the minimum of a function (if it finds it all). Describe any shortcoming of the
algorithm.
|
1. | Get minimum x value from user | |
2. | Get maximum x value from user | |
3. | Calculate middle x value by adding minimum and maximum and dividing by 2. | |
4. | Calculate y value at each point. | |
5. | If y value at minimum x value is less than y value at maximum x value,
make the middle x value the new maximum x value. Otherwise, make the
middle x value the new minimum x value. | |
6. | Repeat steps 1-5 100 times. | |
7. | Compare y values of minimum and maximum x values. The lowest is the
minimum y value.
|
|
| |
| 1.15 | Describe a sequence of steps that determines if a word is a palindrome. A
palindrome is a word that reads the same way forward and backwards like "racecar."
|
| |
| 1.16 | Moving truck company called IMove has 150 locations nationwide. Customer's
rent a truck from the depot closet to their old home, and return their truck to
the closest depot to their new home. How should IMove insure that there are
enough trucks at each depot after every month to meet customer demand? Describe
an algorithm that IMove can use. Describe what information would be needed to
improve your algorithm.
|
| |
| 1.17 | IMove customers are given one truck to fit as much of their belongings in as
possible. Each belonging has a volume and value associated with it. A customer
develops the following algorithm to take belongings to maximize total value yet
stay under the restriction that the sum of the volumes of the belongings cannot
exceed the maximum volume of the truck. Describe if this customer's algorithm
will work in every case.
In this case, the optimal way to pack the truck would be to pack every item except
the item with a volume of 12.
1.For each belonging, create a price/volume ratio
2. Sort the belongings in terms of price/volume, highest price/volume first.
3. Consider the first belonging
a. If volume is available, load the belonging, and consider the next
belonging.
b. If volume was not available, consider then next belonging
c. return to 3a unless there are no belongings left.
|
| 1.18 | Improve the prime number algorithm, using the suggestions in the text and your
own. Make sure to test that it still works by manually going through the steps
for several numbers.
|
| |
| 1.19 | Speciation is a term used to describe how members of a species begin to evolve.
This evolutionary process can be monitored. Suppose one is given monthly reports
of two isolated populations of birds that, at the start of monitoring them, were
the same species. Describe how features like the beak length and wing span from
200 birds (100 from each population) can be used in a computer program that will
determine whether or not speciation, and thus evolution, is occurring. You may
use simple statistics.
|
| |
| 1.20 | Gene sequencing is an intensive process. Once we have gene sequences of two
species, we would like to see just how closely related they are. Describe an
algorithm, given a sequence of 30 base pairs, that determines how closely related
1 sequence is with another. The algorithm should output how many matching
portions and the unmatched portions.
|
| |
| 1.21 | Solar Flares are a threat to astronauts/satellites, disturb radar/radio and
influence the weather. Because they travel at various speeds (some near the speed
of light), the SOHO satellite could only provide warnings of immanent flares hours
to days in advanced. Below is data that the SOHO satellite might work with. The
flux readings are scaled in decibels, so C1.0 is 10 times stronger than B1.0, and
the first and second tick above B1.0 is B2.0 and B3.0. The spikes in the graph
are due to solar flares. The small spikes that occur as flux decreases should be
disregarded. Describe an algorithm that can predict a solar flare. Your
algorithm can only work with data collected up to and including the last flux
observation y. you may call the second to last flux reading x, and the previous
peak or valley p.
|
| 1.22 | Forest fires are a costly natural disaster for some areas in the world. Suppose
there are 10,000 woodland sectors. Each sector has an associated "dryness" index
d that predicts its flammability (higher numbers are more dry), and a value v
index that estimates how costly a fire in that sector would be. A high dryness
index estimates the likelihood that a fire will start in that sector in addition
to the likelihood of catching on fire from an adjacent burning sector. Because we
have limited resources to prevent fires in all sectors, we need to order the "best
sectors" to make safe first. Lastly, every time we visit a sector to make it
safe, we can only reduce the dryness index by half (rounding up). Dryness
indexes less than four are considered inflammible.
a) What does "best sectors" mean to you?
b) Describe an algorithm that orders the "best sectors"
|
| |
| 1.23 | A Mars rover has lost telemetry with its orbiting satellite. A week has gone by
and satellites cannot locate the darn thing. NASA suspects that the rover's
communication device was damaged in a Martian storm. Fortunately, the rover can
repair itself if the satellite, from orbit, drops a replacement communication
device within d meters of the rover. The rover travels x meters each day in any
random direction. If the satellite targets the last known position of the rover,
which was 7 days ago, and drops the communication device there, describe an
algorithm that uses parameters d and x to assess the probability that the rover
will find the communication device as soon as it hits the ground.
You may assume that the rover's probability of being at any position is uniformly
distributed in a circle of radius x, and 0 elsewhere.
| |
|
| 1.25 | Think about the steps of software engineering: gather requirements, draft a
design, develop algorithms and write code. Knowing this, describe how a software
engineer would design and code an instant messaging system for the military.
|
| |
