Instructor: | Hantao Zhang | TA: Harpreet Singh | |
Email: | hantao-zhang@uiowa.edu | harpreet-singh-1@uiowa.edu | |
Office: | 9:30-10:30am, Tu.W.Th., 201B MLH | 12:30-2:00pm, M.W., 201N MLH | |
Web: | http://www.cs.uiowa.edu/~hzhang/c31/ | http://www.cs.uiowa.edu/~___ |
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 stations. 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