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 rst common element, without modifying the lists elements or using additional datastructures.
a) A linear algorithm is discussed in the lecture: count the lists rst, then use the count di erence as an o set 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, nd an arrangement of the functions f1; f2; : : : such that for all i, fi = (fi+1).
pn 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
