|Instructor:||Hantao Zhang||TA: Harpreet Singh|
|Office:||9:30-10:30am, Tu.W.Th., 201B MLH||12:30-2:00pm, M.W., 201N MLH|
Syllabus, Announcements, Homeworks, Projects, Exams, Lecture Notes, Sample code, Online Resources
Let's consider a long, quiet country road with houses scattered very
sparsely along it. (We can picture the road as a long line segment, with
an eastern endpoint and a western endpoint, and all houses are the points on the line.)
Further, let's suppose that the residents of all these houses are cell
phone users. You want to place cell phone base stations at certain points
along the road, so that every house is within four miles of one of the base
Give an greedy algorithm that achieves this goal, using as few base
stations as possible. Prove that your algorithm is optimal.
Suppose app(x, y) is the function "append" on strings x and y (i.e., app("abc", "xyz") = "abcxyz")), which is defined recursively: app(x, emptyString) = x and app(x, ya) = app(x, y)a for all strings x and y, and symbol a.
Prove formally that for all strings x, y, z, app(app(x, y), z) = app(x, app(y, z)).
Note: In your proof, if you want to use other property of "app", you have to prove it formally before you use it.
Part 2: 4-8, 4-14, 4-18 on pages 139-141
Part 2: 4-19, 4-23, 4-26 on pages 185-189