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

Exam Information

Material Type:Final
Class:CMSC 420 - Data Structures
Subject:Computer Science
University:University of Maryland
Term:Fall 2001
  • Unfortunately
  • Total Number
  • Following Procedure
  • Manipulation
  • Rectangular
  • Partial Credit
  • In Front Of
  • In Front (of)
  • Data Processing
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

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