22C:031:002 Algorithms, Spring 2014
8-9:15AM, Room 27 MH
1/20: Welcome to the class! This web site is the place where you will see annoucements, homework assignments, etc.
1/21: The first two chapters are
provided temporarily, plus a chapter on Greedy Algorithms from a different textbook.
3/14: We will have the midterm exam on 3/27.
Here is the test problem from last year.
3/25: The midterm will be closed book and notes, except one sheet of notes.
The matierals will include all those in the lecture notes from ch01 to ch04.
3/27: The final exam will be replaced by the second midterm (the same
weight in the total scores) which will take place on 5/8/2014. Again,
it's closed book and notes, except two sheets of notes. The matierals
will include all those in the lecture notes after the first midterm.
4/23: Project 4 is due on 5/6/14. Please plan time to do it.
- Homework 1 is due on 1/30/14 before or in class.
1-5, 1-6, 1-28 on pages 27-30; and solve the following problem using the greedy technique.
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.
- Homework 2 is due on 2/6/14 before or in class.
2-1, 2-19, 2-21, 2-31, 2-47 on pages 59-63; and solve the following problem:
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.
- Homework 3 is due on 2/13/14 before or in class.
3-1, 3-3, 3-10, 3-13 on pages 98-100
- Homework 4 is due on 2/20/14 before or in class.
3-7, 3-8, 3-11 on pages 98-100
- Homework 5 is due on 2/27/14 before or in class.
Part 1: We will insert the following elements (in the given order) into an
empty Red-Black tree: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. Please draw the
Red-Black trees after each insertion.
Part 2: 4-8, 4-14, 4-18 on pages 139-141
- Homework 6 is due on 3/6/14 before or in class.
Part 1: Initially, the content of array A is [0,5,4,3,1,6,2]. Please
show the contents of A whenever it is changed during sorting using (a)
heap sort and (b) quick sort. The java code of these sorting algorithms can be found
4-19, 4-23, 4-26 on pages 185-189
- Homework 7 is due on 4/1/14 before or in class.
5-6, 5-7, 5-13, 5-15, 5-16, 5-19 on pages 185-189
- Homework 8 is due on 4/10/14 before or in class.
6-6, 6-8, 6-9, 6-18, 6-19, 6-22 on pages 226-228
- Homework 9 is due on 4/22/14 before or in class.
6-10, 6-17, 6-21, 6-24 on pages 226-228.
7-2 (no duplicates in the output), 7-14 on pages 270-272
- Homework 10 is due on 4/29/14 before or in class.
8-2, 8-4, 8-5, 8-6, 8-10 on pages 310-312.
- First Midterm Exam is on 3/27/14 in class, 75 minutes (20% of the final grade).
A sample test questions
- Second Midterm Exam is on 5/8/14 in class, 75 minutes (36% of the final grade).
- No Final Exam