CSC 344
Homework 1

Assigned 20 Jan, due 3 Feb

Problems from chapter 1 of the textbook

• Problem 1.1.8b (Euclid's game. Note: it seems to me that whether you want to move first or second depends on the numbers; tell me how it depends on the numbers, or convince me that it doesn't.)
• Problem 1.2.9, MinDistance
• Problem 1.3.6 (specifying and modeling a graph problem)
• Problem 1.4.4 (matrix and list representations of graphs)
• Problem 1.4.10 (anagrams) Note that you are not required to write a compilable program, only pseudocode, but you should still "test" your program by hand-tracing through it on some well-chosen test cases.

Another pseudocode problem:

Write an algorithm in pseudocode which takes in a list (or array or whatever) of n numbers, and determines whether or not there is a number that appears more than once in the list. For example, dups(3,8,5,1,6) would return false, but dups(3,8,5,3,6) would return true.

Analyze your algorithm's running time as a function of n. Hint: the problem can be solved in time proportional to n*log(n); for full credit, give an algorithm of this efficiency or better.

Programming:

Write an algorithm in pseudocode which takes in two binary numbers (represented as lists or arrays of booleans) and adds them, producing the result as another list or array of booleans.

Implement, test, and debug your binary-addition algorithm in your favorite programming language -- C, C++, Java, Scheme, Prolog, perl, Pascal, etc.