-
Notifications
You must be signed in to change notification settings - Fork 86
Expand file tree
/
Copy pathpythondsProgrammingExercises.ptx
More file actions
executable file
·134 lines (132 loc) · 6.81 KB
/
pythondsProgrammingExercises.ptx
File metadata and controls
executable file
·134 lines (132 loc) · 6.81 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
<section xml:id="recursion_programming-exercises">
<title>Programming Exercises</title>
<p><ol marker="1">
<li>
<p>Write a recursive function to compute the factorial of a number.</p>
</li>
<li>
<p>Write a recursive function to reverse a list.</p>
</li>
<li>
<p>Modify the recursive tree program using one or all of the following
ideas:</p>
<p><ul>
<li>
<p>Modify the thickness of the branches so that as the <c>branchLen</c>
gets smaller, the line gets thinner.</p>
</li>
<li>
<p>Modify the color of the branches so that as the <c>branchLen</c> gets
very short it is colored like a leaf.</p>
</li>
<li>
<p>Modify the angle used in turning the turtle so that at each branch
point the angle is selected at random in some range. For example
choose the angle between 15 and 45 degrees. Play around to see
what looks good.</p>
</li>
<li>
<p>Modify the <c>branchLen</c> recursively so that instead of always
subtracting the same amount you subtract a random amount in some
range.</p>
</li>
</ul></p>
<p>If you implement all of the above ideas you will have a very
realistic looking tree.</p>
</li>
<li>
<p>Find or invent an algorithm for drawing a fractal mountain. Hint: One
approach to this uses triangles again.</p>
</li>
<li>
<p>Write a recursive function to compute the Fibonacci sequence. How
does the performance of the recursive function compare to that of an
iterative version?</p>
</li>
<li>
<p>Implement a solution to the Tower of Hanoi using three stacks to keep
track of the disks.</p>
</li>
<li>
<p>Using the turtle graphics module, write a recursive program to
display a Hilbert curve.</p>
</li>
<li>
<p>Using the turtle graphics module, write a recursive program to
display a Koch snowflake.</p>
</li>
<li>
<p>Write a program to solve the following problem: You have two jugs: a
4-gallon jug and a 3-gallon jug. Neither of the jugs have markings on
them. There is a pump that can be used to fill the jugs with water.
How can you get exactly two gallons of water in the 4-gallon jug?</p>
</li>
<li>
<p>Generalize the problem above so that the parameters to your solution
include the sizes of each jug and the final amount of water to be
left in the larger jug.</p>
</li>
<li>
<p>Write a program that solves the following problem: Three missionaries
and three cannibals come to a river and find a boat that holds two
people. Everyone must get across the river to continue on the
journey. However, if the cannibals ever outnumber the missionaries on
either bank, the missionaries will be eaten. Find a series of
crossings that will get everyone safely to the other side of the
river.</p>
</li>
<li>
<p>Modify the Tower of Hanoi program using turtle graphics to animate
the movement of the disks. Hint: You can make multiple turtles and
have them shaped like rectangles.</p>
</li>
<li>
<p>Pascal's triangle is a number triangle with numbers arranged in
staggered rows such that</p>
<m docname="Recursion/pythondsProgrammingExercises" nowrap="False" number="True" xml:space="preserve">a_{nr} = {n! \over{r! (n-r)!}}
</m>
<p>This equation is the equation for a binomial coefficient. You can
build Pascal's triangle by adding the two numbers that are diagonally
above a number in the triangle. An example of Pascal's triangle is
shown below.</p>
<pre> 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1</pre>
<p>Write a program that prints out Pascal's triangle. Your program
should accept a parameter that tells how many rows of the triangle to
print.</p>
</li>
<li>
<p>Suppose you are a computer scientist/art thief who has broken into a
major art gallery. All you have with you to haul out your stolen art
is your knapsack which only holds <m>W</m> pounds of art, but for
every piece of art you know its value and its weight. Write a dynamic
programming function to help you maximize your profit. Here is a
sample problem for you to use to get started: Suppose your knapsack
can hold a total weight of 20. You have 5 items as follows:</p>
<pre>item weight value
1 2 3
2 3 4
3 4 8
4 5 8
5 9 10</pre>
</li>
<li>
<p>This problem is called the string edit distance problem, and is quite
useful in many areas of research. Suppose that you want to transform
the word <q>algorithm</q> into the word <q>alligator.</q> For each letter you
can either copy the letter from one word to another at a cost of 5,
you can delete a letter at cost of 20, or insert a letter at a cost
of 20. The total cost to transform one word into another is used by
spell check programs to provide suggestions for words that are close
to one another. Use dynamic programming techniques to develop an
algorithm that gives you the smallest edit distance between any two
words.</p>
</li>
</ol></p>
<conclusion><p>
<!-- extra space before the progress bar -->
</p></conclusion>
</section>