## Exam Information

Login / Sign Up to View Document

## 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

© Copyright 2020 , Koofers, Inc. All rights reserved.

The information provided on this site is protected by U.S. and International copyright law, and other applicable intellectual property laws, including laws covering data access and data compilations. This information is provided exclusively for the personal and academic use of students, instructors and other university personnel. Use of this information for any commercial purpose, or by any commercial entity, is expressly prohibited. This information may not, under any circumstances, be copied, modified, reused, or incorporated into any derivative works or compilations, without the prior written approval of Koofers, Inc.