# Past Exam for CMSC 420 - Data Structures at Maryland (UMD)

## Exam Information

 Material Type: Final Professor: Staff Class: CMSC 420 - Data Structures Subject: Computer Science University: University of Maryland Term: Fall 1996 Keywords: Either...orCircumstancesActual CodeExplanationOrganizationManipulationDiscriminantFollowing StepsReturn ResultLoad Factor

## Sample Document Text

Problem 1. Let f(n) and g(n) be any two functions over the set of nonnegative integers. 1a [5]. True or false: either f(n) = O(g(n)) or g(n) = O(f(n)). ANSWER: false. One counterexample is the case where f(n)=sin(?n) and g(n)=cos(?n). 1b [5]. True or false: if f(n) = ?(g(n)), then there are positive numbers c, d, and n 0 such that for every n ? n 0 , cg(n) ? f(n) ? dg(n) and cf(n) ? g(n) ? df(n). ANSWER: true. Explanation: we know there are positive numbers c 1 , d 1 , and n 1 such that for every n ? n 1 , c 1 g(n) ? f(n) ? d 1 g(n); and positive numbers c 2 , d 2 , and n 2 such that for every n ? n 2 c 2 f(n) ? g(n) ? d 2 f(n). Just let c = min(c 1 ,c 2 ); d = max(d 1 ,d 2 ); and n 0 = max(n 1 ,n 2 ). Problem 2 [10]. Suppose you are using linked lists to represent an n × n sparse matrix, as illustrated in Figure 5.5 of the book. In the worst case, how much time will it take to compute the sum of the elements along the main diag...

## Related Documents

Either...or Exam
Either...or Exam
Particularly Exam
Either...or Notes
Particularly Notes