Homework

Homework 1

Given a sorted array, how can we get rid of duplicates "in-situ", i.e. without using additional (temporary) memory ?

To turn in on Wednesday 9/13 before 3:00 p.m.:: your code; a printout of the file generated by the UNIX utility "script" showing several executions of your algorithm; your Big Oh analysis and a short explanation "why your algorithm works correctly".

You will be graded on:

correctness: (6 points): correct algorithm and results (incl. thorough testing); robustness (e.g. no division by zero); following the specification (e.g. output specification)
style: (2 points): use of comments; indentation (use TAB key in emacs); meaningful variable and function naming; simplicity, modularity etc.
analysis: (2 points): Big Oh complexity; why?

Homework 2

Exercises 3.5, 3.7 and 3.9 from the handout. Due Friday 9/22 before 3:00 p.m.

Homework 3, due Monday 10/2 3:00

Write a program to solve the "file mapping" problem (see handout).
You will be graded on:

correctness: (6 points): correct algorithm and results (incl. thorough testing); robustness (e.g. no division by zero); following the specification (e.g. output specification)
style: (2 points): use of comments; indentation (use TAB key in emacs); meaningful variable and function naming; simplicity, modularity etc.
analysis: (2 points): Big Oh complexity; why?

Homework 4, due Monday 10/9 3:00

Find a formula for the following sum and prove your claim:
a₁+a₂+...+a_n, where a_n=c₁*n+c₂, and c₁, c₂ are constants.
Find a formula for the following sum and prove your claim:
1*2 + 2*3 + ... + n*(n+1)

Homework 5, due Monday 10/16 3:00

Design a divide-and-conquer algorithm for polynomial evaluation.

For 9 out of 10 points, assume n=1,3,7,15... and come up with a O(n log n) algorithm.

For 10 out of 10 points, your O(n log n) algorithm should work for all n.

For one extra credit point, assume n=1,3,7,15... and come up with a O(n) algorithm.

For two extra credit points, your O(n) algorithm should work for all n.

Code your algorithm and verify results by also coding one of the algorithms we discussed in class.

Hand-in a script file with input n=3, a[3]=1, a[2]=2, a[1]=3, a[0]=4, x=2.

Explain the complexity of your algorithm and why it works for some/ all n.

Homework 6, due Monday 10/30 3:00

You are given a binary tree T. T is called an AVL tree if the balance factor of all its nodes are 0, 1, or -1. (The balance factor of a node is defined as the difference between the height of the node's left subtree and the height of the node's right subtree.) Assume that the nodes do not have enough space to store the balance factor. Design an efficient algorithm to solve the following decision problem: Given a tree T, the algorithm should determine whether or not T is an AVL tree. (The answer should be only yes or no.)

Write a program and run it on the following two trees:
*ABCDE*FG**H**I*
*ABCD*EF*******G

Homework 7, due Monday 11/7 3:00

First, implement the dynamic programming algorithm from the handout.
Then, use the belong flag to print out which items are in.
What is the complexity of each algorithm?
Use the following input:
K=16, n=4, S[]={2,3,5,6}
K=14, n=5, S[]={4,5,2,6,3}