CS5800 Homework 1 Solved

Instructions

1. Please review the grading policy outlined in the course information page.
2. You must also write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.
3. Problem numbers (like Exercise 3.1-1) are corresponding to CLRS 3rd edition. While the 2nd edition has similar problems with similar numbers, the actual exercises and their solutions are different, so make sure you are using the 3rd edition.

Problems

1. (20p)Two linked lists (simple link, not double link) heads are given: headA, and headB; it is also given that the two lists intersect, thus after the intersection they have the same elements to the end. Find the first common element, without modifying the lists elements or using additional datastructures.

   a) A linear algorithm is discussed in the lecture: count the lists first, then use the count difference as an offset in the longer list, before traversing the lists together. Write a formal pseudocode (the pseudocode in the lecture is vague), using “next” as a method/pointer to advance to the next element in a list.

   b) Write the actual code in a programming language (C/C++, Java, Python etc) of your choice and run it on a made-up test pair of two lists. A good idea is to use pointers to represent the list linkage.

2. (10p) Exercise 3.1-1
3. (5p) Exercise 3.1-4
4. (15p) Rank the following functions in terms of asymptotic growth. In other words, find an arrangement of the functions f1, f2, . . . such that for all i, fi = Ω(fi+1).

   √n ln n ln ln n2 2ln2 n n! n0.001 22 ln n (ln n)!

5. (40p) Problem 4-1 (page 107)
6. (30p) Problem 4-3 from (a) to (f) (page 108)

   1