Assignment One (Due day: Jan 31, 2013)

1. Question 0.2 in chapter 0 of the textbook.

2. Design an efficient algorithm to compute the square root of an non-negative integer. We define that non-negative integer y is the square root of x iff y*y <= x and (y+1)*(y+1) > x. Write pseudocode of the function sqrt(x). Analyze the time complexity of your method. [Hint: use a binary search method to find the result].

3. Write a function to remove the duplicated elements from a sorted array, your function should use only O(1) extra space, i.e., you have to compute the result in place.

4. Compute the difference set A-B. We define C=A-B if C contains all the elements in A but not in B. For example, A = {1,2,3,4}, B = {2,5}, the A-B={1,3,4}. We assume that A and B contain integer numbers. Construct an efficient algorithm to find A-B in pseudocode. Analyze the time and space complexity of your algorithm.

5. Assume that we have a board of size 2^n by 2^n, each cell of the board is a square. We have many L shaped tiles, each of which can cover 3 cells on the board. Prove that we can always cover the board except one cell using these L shape tiles. For example, it is easy to verify that we can use one L shape tile to cover a 2x2 board and leave one cell empty, no matter where the empty one is. Use an induction method to do the proof. We already have a base case for the 2x2 boards. We just need to show that if we can cover any 2^k by 2^k boards with one piece missing, we can cover any 2^(k+1) by 2^(k+1) boards with one piece missing. Based on your proof, write a recursive function to solve the problem.

Solutions for assignment one


Assignment Two (due day: Feb 7, 2013)

1. Write an efficient algorithm to compute x^y (the power function), where x and y are positive integers. Analyze the complexity of your code.

2. Design a polynomial-time algorithm for computing a^(b^c) mod p, where x^y is the power function and p is a prime. Analyze the complexity.

3. Write a polynomial algorithm to compute the minimum common multiples (MCM) of two numbers. For example, the MCM of 15 and 9 is 45.

4. Given an integer array A[0..N-1], N>=3. We know that A[0]>A[1] and A[N-1]>A[N-2]. There must be a local minimum in [0,N-1] so that A[i] <= A[i+1] and A[i] <= A[i-1]. Use a binary search method to find a local minimum. Write Pseudocode.

5. Here is a modification of the binary search problem. We want to find the range of a number in a sorted array. For example, in the sequence [1,5,6,8,8,8,9,20]. If the query is 8, your code should return [3,5] and if the query is 7 the return should be [-1,-1]. Design an efficient method to complete the search.

6. Design a divide and conquer method to find a subarray that has the max sum. For instance we have an array [1,2,-2,6,8,-1], the largest sum sub-sequence is [1,2,-2,6,8]. [Hints: if we partition the array into two halves, can we solve each of them and combine the results to obtain something useful?]

Assignment Two Solutions


Assignment Three (due day: Feb 19, 2013)

Question 2.14, 2.19, 2.22, 2.23, 3.9 and 3.10 in the textbook

Assignment Three Solutions


Assignment Four (due day: March 21, 2013)

Write a Java or C++ program to implement the Dijkstra's shortest path algorithm. You should implement a simple graph data structure yourself. You can use the container classes in Java or C++ to simplify your code. Test your code on simple graphs. You need to email your source code to me with your email titled as CS383 Assignment 4 Submission before the due day.

Sample Code in C++


Assignment Five (due day: April 4, 2013)

Question 4.18, 4.19, 4.21, 6.1 and 6.2 in the textbook.

Assignment Five Solutions


Assignment Six (due day: April 25, 2013)

Question 5.7, 5.31 in the textbook at http://www.cs.berkeley.edu/~vazirani/algorithms/chap5.pdf. Write pseudo-code using greedy method and PROVE the correctness of your algorithm.

Assignment Six Solutions


Assignment 7 (due day: May 2, 2013)

Question 7.17, 7.18 and 7.22 in the textbook at http://www.cs.berkeley.edu/~vazirani/algorithms/chap7.pdf.