Computer Science Foundation Exam
December 19, 2008
Computer Science
Section 1B
Name: Solution and Grading Criteria
SSN:
Max Type Passing Student
Pts Threshold Score
Q1 10 ANL 7
Q2 10 DSN 7
Q3 10 ANL 7
Q4 10 DSN 7
Q5 10 ANL 7
Total 50 35
You must do all 5 problems in this section of the exam.
Partial credit cannot be given unless all work is shown and is readable.
Be complete, yet concise, and above all be neat. Do your rough work on
the last page.
1
, 1) (10 points) Order Notation
Indicate the time complexity in terms of Big-O and the appropriate variables for each of
the following operations:
a) Using mergesort to sort n integers. O(nlgn)
b) Pushing n items on to an initially empty stack. O(n)
c) Searching for an element in a sorted array of n elements O(lgn)
using a binary search (worst case)
d) Searching for an element in a sorted array of n elements O(1)
using a binary search (best case)
e) Searching for an element in a sorted array of n elements O(n)
using a linear search (worst case)
f) Converting an infix expression with n symbols to a postfix O(n)
expression using the standard algorithm
g) Inserting n elements into an initially empty AVL tree O(nlgn)
(worst case)
h) Inserting n elements into an initially empty BST that does O(n2)
not enforce balance properties (worst case)
i) Adding two n digit numbers together using the standard O(n)
addition algorithm you were taught in elementary school
j) Performing a postfix traversal of a binary tree containing n O(n)
elements
Grading: 1 pt each, all or nothing. Accept answers that are correct within a constant
factor.
2
December 19, 2008
Computer Science
Section 1B
Name: Solution and Grading Criteria
SSN:
Max Type Passing Student
Pts Threshold Score
Q1 10 ANL 7
Q2 10 DSN 7
Q3 10 ANL 7
Q4 10 DSN 7
Q5 10 ANL 7
Total 50 35
You must do all 5 problems in this section of the exam.
Partial credit cannot be given unless all work is shown and is readable.
Be complete, yet concise, and above all be neat. Do your rough work on
the last page.
1
, 1) (10 points) Order Notation
Indicate the time complexity in terms of Big-O and the appropriate variables for each of
the following operations:
a) Using mergesort to sort n integers. O(nlgn)
b) Pushing n items on to an initially empty stack. O(n)
c) Searching for an element in a sorted array of n elements O(lgn)
using a binary search (worst case)
d) Searching for an element in a sorted array of n elements O(1)
using a binary search (best case)
e) Searching for an element in a sorted array of n elements O(n)
using a linear search (worst case)
f) Converting an infix expression with n symbols to a postfix O(n)
expression using the standard algorithm
g) Inserting n elements into an initially empty AVL tree O(nlgn)
(worst case)
h) Inserting n elements into an initially empty BST that does O(n2)
not enforce balance properties (worst case)
i) Adding two n digit numbers together using the standard O(n)
addition algorithm you were taught in elementary school
j) Performing a postfix traversal of a binary tree containing n O(n)
elements
Grading: 1 pt each, all or nothing. Accept answers that are correct within a constant
factor.
2
