# CS 330 Algorithms

## Homework 1

• ex. 1.2-2
• ex. 1.2-3
• pr. 1-1
• ex. 2.1-2
• ex. 2.1-3
Grader's comments: Some people forgot to prove or just did not prove. Also, some returned the value not the index.
• ex. 2.1-4 - extra credit
Grader's comments: Need to assume that 0th element is the least significant bit. Need to have a carry. Simple xor will not work. C[i]=A[i] + B[i] will not work.
• ex. 2.2-3
• ex. 2.2-4 extra credit
• ex. 2.3-6
Grader's comments: Some people just did not see the idea. Also, some explained the complexity in terms of data structure choice.

• ex. A.1-1
• ex. B.1-5
• ex. C.1-1
• ex. A.1-7 extra credit
• ex. B.1-4 extra credit
• ex. C.1-3 extra credit

## FAQ:

1. ### For the first two questions, how specific do you want the number > 'n' to be? Is between 1 and 2 good enough an answer? How about other approximations (e.g. between 10000 and 20000)?

The answer must be exact integers (you'd never sort 3.5 integers): e.g. something like this "for n=5 and smaller alg A is faster, for n=6 they are the same but for n=7 and larger alg B is faster" (a better way to write it would be "for n<6 A is faster, for n>6 B is faster, for n=6 they are the same"). Of course you might have some situations/problems when A and B will never run the same.
In general, you would get significant partial credit for good approximations (the better approximation, the more partial credit).

2. ### For questions on Problem 1-1(the chart for solution times in f(n microseconds) ), how specific do you want the answers to ones such as lg n (I'm not terribly familiar with solving for such things except for graphing and finding intersections)?

3. Similarly to the previous question, you can work here with integers (even though microseconds can be fractioned, unlike the input length). Namely, you can round your answers to the nearest millisecond. While it is useful - and actually not very difficult (hint: binary search) - to develop a skill for estimating in your mind the functions like (lg n), sqrt(n), with a good degree of precision, you can use calculators for that.

4. ### My pseudocode is more like C++ straight code than the pseudocode in the book. Will that be accepted for full credit?

Yes, it will be acceptable for the credit, but it may often get in the way for both you and the grader. You should try to develop the style (feel free to use the book's one for example) which will help you prevent the technicalities from obscuring the core of the matter

5. ### How many days are in a month (as far as pr.1-1 is concerned at least)?

It does not matter, as long as you state it explicitely.
In general, whenever you use an assumption, state it explicitely.