Koofers

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

Exam Information

Material Type:Final
Professor:Nau
Class:CMSC 420 - Data Structures
Subject:Computer Science
University:University of Maryland
Term:--
Keywords:
  • Either...or
  • Circumstances
  • Actual Code
  • Explanation
  • Organization
  • Manipulation
  • Discriminant
  • Following Steps
  • Return Result
  • Load Factor
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4

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
Traditional Typeface Exam
155, "/var/app/current/tmp/"