# 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: Fall 2001 Keywords: UnfortunatelyTotal NumberFollowing ProcedureManipulationRectangularPartial CreditIn Front OfIn Front (of)Data Processing      ## Sample Document Text

Name_________________________ CMSC 420, Fall 2001 - Final Exam 1 Problem 1. Let f(n) and g(n) be any two functions over the set of nonnegative integers. 1a [5 points]. True or false: if f(n) = O(g(n)) then f(n) = O(g(n)/2000). True. 1b [5 points]. True or false: if f(n) = O(g(n)), then g(n) = ?(2000f(n)). True. Problem 2 [5 points]. Professor Prune says, "Here's a computer algorithm, along with an analysis showing that O(n) is a lower bound on the algorithm's running time." What is wrong with Professor Prune's statement? O(n) can be an upper bound, but not a lower bound. For a lower bound, Professor Prune would need to use ? or ?. Problem 3 [5 points]. Professor Prune says, "I have modified the TopologicalSort algorithm to return a list of the nodes in the order that they were visited. To do this, I made TopologicalSort start by creating an empty list L, and I modified WalkForSort(v) so that it appends v to L. Unfortunately, this gave me a worst-case running time of O(n 2 ) ra...

## Related Documents Unfortunately Exam Decomposition Notes