Algorithms - Assignments

Homework 16 (due date is Monday, July 26, before the class)
old book: *, 17.2-4, 17.3-2.
new book: 16.1-2, 16.2-4, 16.3-2

solutions: 16.1-2, 16.2-4, 16.3-2

hints:
16.1-2: this approach is absolutely simmetrical to the one, presented in the Chapter. Consider a dual problem to original - replace every activity (s,f) with the activity (-f, -s) (we swap start and finish time and make them negative)
16.2-4: Professor should drive till the last gas station that he can reach without refueling the car, refuel on that station and againg drive as much as possible and so on.

* (16.1-2):
Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

for reading: Chapter 17 (old book) or Chapter 16 (new book)
Homework 15 (due date is Monday, July 26, before the class)
old book: 16.1-1, *, 16.1-4, 16.3-1 (present the illustration for it as the one given on the Figure 16.3),
new book: 15.2-1 (compose tables m and s also), 15.2-3, 15.2-5, 15.4-1 (present the illustration for it as the one given on the Figure 15.6),

solutions: 15.2-1: page 1, page 2, 15.2-3, 15.2-5, 15.4-1

* - means that there is no analogue of 15.2-3 (from new book) in old book, here is the formulation of this problem:
Use the substitution method to show that the solution to the recurrence
(given in the 'Counting the number of parenthesizations' section of 16.1 P(n) = ... ) is \Omega(2ⁿ)

hints:
15.2-5: use the induction on the number of matrices

for reading: Chapter 16 (old book)- intro, 16.1, 16.2 - till Recursive-Matrix-Chain, 16.3;
or Chapter 15 (new book) - intro, 15.2, 15.3 till Recursive-Matrix-Chain, 15.4- Dinamic programming
Programming assignment N3 (the last one, due date is Monday, July 26)
I'm posting the third and the last programming assignment for our course:
Implement the Huffman algorithm.
The input for the program (at the run time, taken from standard input):
first user inputs number of letters,
then a letter, say a, then frequency of this letter (some number),
then another letter, say c, and its frequency (some number),
and so on.
The output (standard output): letter, say a, and its codeword
then another letter, say c and its codewords, and so on.
Homework 14 (due date is Thursday, July 22, before the class)
old book: *, 27.1-6, 27.2-1
new book: 26.1-1, 26.1-6, 26.2-1

solutions: 26.1-1, 26.1-6, 26.2-1

the formulation of * problem (26.1-1 in new book):
Using the definition of a flow, prove that if (u,v) doesn't belong to set E, and (v,u) doesn't belong to set E then f(u,v) = f(v,u) = 0.
for reading:Chapter 26 (new book) or Chapter 27 (old book)

for practice: in order to understand the operation of Ford-Fulkerson algorithm look at the illustration on Figure 26.5, page 659 (new book) or on Figure 27.6, page 595 (old book)
Homework 13 (due date is Thursday, July 22, before the class)
old book: 25.3-1, 25.3-4 ,25.4-1, 25.2-1, *
new book: 24.1-1, 24.1-4, 24.2-1, 24.3-1, 24.3-5 (answer only the first question and explain your answer)

solutions: 24.1-1: part 1, part 2, 24.2-1, 24.3-1: part 1, part 2, 24.1-4, 24.3-5

the formulation of * problem:
Let G=(V,E) be a weighted, directed graph with weight function w: E->{1,2,...,W} for some positive integer W, and assume than no two vertices have the same shortest-path weights from source vertex s. Now suppose that we define an unweighted directed graph G'=(V "v" V',E') ("v" is a union symbol) by replacing each edge (u,v) from E with w(u,v) unit-weight edges in series. How many vertices does G' have?

for reading: Chapter 24 (new book) or Chapter 25 (old book)
Homework 12 (due date is Thursday, July 15, before the class)
old book: 24.1-3, 24.2-2
new book: 23.1-3, 23.2-2

solutions: 23.1-3, 23.2-2

hints:
23.1-3 : what will be if you remove that edge (u,v) from your MST? - it gives you a ....
23.2-2 : in case of adjacency-matrix representation of the graph G=(V,E) algorithm should be changed in line 8 - instead of examining an adjacency list (of some vertex) we'll be exploring a corresponding whole row in the adjacency matrix

for reading: Chapter 24 (old book) or Chapter 23 (new book).
Homework 11 (due date is Thursday, July 15, before the class)
old book: 23.3-2 (plus show the parenthesis structure of the DFS for this graph), 23.3-8, 23.4-1 (under the assumption of Exercise 23.3-2), 23.5-2
new book: 22.3-2 (plus show the parenthesis structure of the DFS for this graph), 22.3-10, 22.4-1, 22.5-2

solutions: 22.3-2, 22.3-10, 22.4-1, 22.5-2

for reading: the same chapters as for HW10.
Homework 10 (due date is Monday, July 12, before the class)
old book: 23.1-1, 23.1-2, 23.2-2 (plus using figure 23.3 illustrate the operation of BFS)
new book: 22.1-1, 22.1-2, 22.2-2 (plus using figure 22.3 illustrate the operation of BFS)

solutions: 22.1-1, 22.1-2, 22.2-2

for reading: Chapter 23 (old book) or Chapter 22 (new book)
Homework 9 (due date is Thursday, July 8, before the class)
old book: 14.1-1, 14.1-2
new book: 13.1-1, 13.1-3

solutions: 13.1-1, 13.1-3

for reading: Chapter 14 (old book) - 14.1 and only the beginning (first page) of 14.2 or Chapter 13 (new book) - 13.1 and only the beginning of 14.2 (first page).

notices: in new book there are five red-black properties. In old book - four. The one property which is "missing" in old book is: 2. the root is black. In new book a relaxed red-black tree is defined as a binary search tree that satisfies red-black properties 1,3,4,5 - it corresponds to the definition of a red-black tree in old book.
Homework 8 (due date is Thursday, July 8, before the class)
programming assignment: Implement Randomized Quicksort in C/C++.
Input: an array A and the number n of elements in the array. The elements of the array and number n should be taken from the standard input (stdin)
Output: the array B of sorted elements from A. The elements of the array should be printed into the standard output (stdout).

problem 1:
Suppose that we have numbers between 1 and 500 in a binary search tree and want to search for the number 231. Which of the following sequences could not be the sequence of nodes examined:
1. 312, 119, 255, 116, 210, 256, 231
2. 3, 400, 320, 210, 312, 214, 220, 231
3. 201, 500, 175, 346, 187, 415, 231
old book: 13.1-1, 13.2-2, *, **
new book: 12.1-1, 12.2-4, 12.2-3, 12.2-5
*: there is no problem 12.2-3 (number from neww book) in the old book.
Here is the formulation of that problem:
Write the Tree-Predecessor procedure.

solutions: problem 1, 12.1-1, 12.2-4, 12.2-3, 12.2-5

**: Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.

for reading: Chapter 13 (old book) or Chapter 12 (new book) - everything in the Chapter except the 'Randomly built binary search trees' paragraph.

Homework 7 (due date is Thursday, July 1, before the class)
programming assignment (due Monday, July 5 - send it via e-mail):
write a program in C/C++ that will do the counting sort.
Input: an array A and the number n of elements in the array. The elements of the array and number n should be taken from the standard input (stdin)
Output: the array B of sorted elements from A. The elements of the array should be printed into the standard output (stdout).

old book: 9.1-1, 9.2-2, 9.3-1, 9.3-2 (do only the first part of the problem, skip second and third)
new book: 8.1-1, 8.2-2, 8.3-1, 8.3-2 (do only the first part of the problem, skip second and third)

solutions: 8.1-1, 8.2-2, 8.3-2: pdf

for reading: Chapter 9 (old book) or Chapter 8 (new book)

Homework 6 (due date is Thursday, June 24, before the class)
old book: 8.1-1, 8.1-2, 8.2-2
new book: 7.1-1, 7.1-2 (don't do the second part of the exercise), 7.2-3

solutions: 7.1-1, 7.1-2, 7.2-3

for reading: Chapter 8 (old book), or Chapter 7 (new book)

comments: the partition algorithm is wrong in the new book, so use the one from the old book.
Homework 5 (due date is Thursday, June 24, before the class)
old book: 7.1-3, 7.1-6, 7.2-1, 7.2-2, 7.3-2, 7.4-2
new book: 6.1-3, 6.1-6, 6.2-1, 6.2-3, 6.3-2, 6.4-3

solutions: 6.1-3: part 1, part 2, 6.1-6, 6.2-1, 6.2-3, 6.3-2, 6.4-3

for reading: Chapter 7 (old book), Chapter 6 (new book)

comments: Heapify (old book) and Max-heapify (new book) are the identical,
Build-heap (old book) and Build-max-heap (new book) are identical.
Notion of heap (old book) and max-heap (new book) are identical.
Homework 4 (due date is Thursday, June 24, before the class)
old book: 4.1-1, 4.1-2, 4.2-1 (+ use a substitution method to verify your answer), 4.2-3, 5.2-2, 5.2-3, 5.2-5, 5.5-1
new book: 4.1-1, 4.1-2, 4.2-1, 4.2-3 (take c=1 in this exercise and don't verify your answer), B.2-2, B.2-3, B.2-5, B.5-1

solutions: 4.1-1, 4.1-2, 4.2-1: part 1, part. 2, 4.2-3, B.2-2, the rest will be posted later (since you don't need it for Midterm)

Hints: B.2-2 (5.2-2): show that "equivalent modulo n" is reflexive, symmetric and transitive relation, for example, a = a(mod n) - obvious => reflexive (aRa). So you'll also need to show that aRb => bRa (symmetry) and aRb and bRc => aRc (transitivity)
. And for equivalence classes give me [1]={?}, [2]={?}, [3]={?} - that will be enough.

for reading: Chapters 4 (except the master theorem, proof of the master theorem), 5 (old book) or Appendix B, Chapters 4 (new book)

Homework 3 (due date is Thursday, June 17, before the class)
old book: 3.1-1, ***, 3.1-7, 3.2-1, 3.2-3, 3.2-4, 3-1 (a)
new book: A.1-1, A.1-3, A.1-7, A.2-1, A.2-3, A.2-4, A-1 (a)
***: the old book doesn't have exersise A.1-3 (new book), so here is the formulation of this exersise:
show that _k=0^infinity k² x^k=x(1+x)/(1-x)³ for 0<|x|<1

solutions: A.1-1 - A.1-3, A.1-7, A.2-1, A.2-3, A.2-4, A-1 (a)

for reading: Chapters 3,4 (old book) or Appendix A and Chapter 4 (new book)
also read Chapter 2.2 (old book) or Chapter 3.2 (new book) to refresh mathematical background

Hints to the exercises:
A.1-3 - use the formular we received on the lecture, take derivatives of left and right parts and ...
A.1-7 (3.1-7) - take lg of product
A-1 (3.3-1) - show that the given summation is "big omega of ..." and then show that it is also a "big oh of ..."
Homework 2 (due date is Thursday, June 17, before the class)
Problem 1: illustrate the operation of Bubblesort on the array A={1,46,10,5,8,22,31}
exercises in old book: 2.1-3, 2.1-4, 2.1-5 (page 31)
exercises in new book: 3.1-3, 3.1-4, 3.1-5 (page 50)

solutions: 3.1-3 - 3.1-5 (2.1-3 - 2.1-5)

for reading: Chapter 2 (old book) or Chapter 3(new book), the pseudocode of Bubblesort can be found on page 38 in the new book (unfortunately there is no Bubblesort algorithm in old book, so you will have to use your lecture notes)
Homework 1 (due date is Thursday, June 17, before the class)
exercises in old book: 1.1-1, 1.1-2 pp. 5-6;
1.3-1, 1.3-5 p.15
exercises in new book: 2.1-1, 2.1-2 pp. 20-21;
2.3-1, 2.3-5 pp. 36-37

solutions: 2.3-5 (1.3-5)

for reading: Introduction (Chapter 1, old book; Chapters 1,2 -new book)

For those who don't have the book yet the formulations of problems:
1.1-1 (or 2.1-1)
Using the picture presented at the lecture (or a corresponding figure in the book - Figure 1.2 in the old book, Figure 2.2 in the new book) as a model, illustrate the operation of Insertion-Sort on the array A={31,41,59,26,41,58}

1.1-2 (or 2.1-2)
Rewrite the Insertion-Sort procedure to sort into nonincreasing instead of nondecreasing order.

1.3-1 (or 2.3-1)
Using a picture presented at the lecture (or a corresponding figure in the book - Figure 1.3 in the old book, Figure 2.4 in the new book) as a model, illustrate the operation of merge sort on the array A={3,41,52,26,38,57,9,49}

1.3-5 (or 2.3-5)
Referring back to the searching problem (see exercise 1.1-3 (or 2.1-3)), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is "Theta"(lg n).

Notes:
1. for the last problem you'll need the formulation of the exercise 1.1-3 (or 2.1-3)

searching problem

Input:

Output:

linear search