Algorithm Analysis Homework Assignment - Computer Science 101

This document provides solutions to a homework assignment on algorithm analysis. The assignment covers fundamental concepts such as Big O notation, time complexity, and the analysis of algorithms. It includes questions on determining the asymptotic behavior of functions and code snippets. Data structures like stacks, queues, and linked lists are also covered, with questions on their properties and operations. The solutions provide detailed explanations of each concept, including identifying the correct answers for multiple-choice questions. The assignment aims to test the student's understanding of algorithm efficiency, data structure implementation, and related concepts in computer science.

1. The asymptotic behavior of this function f( n ) = 3n + 161 is
a. 3n
b. 3n
c. 161
d. 161n
2. In general a single loop over n items yields f( n ) =___.
a. n*n
b. unknown
c. 2n
d. n
3. A loop within a loop within a loop yields f( n ) = ___.
a. 4+n
b. 3n
c. n3
d. infinity
4. Look at this program
int i;
for ( i = 0; i < n; ++i ) {
f(n);
}
What the number of instructions of the whole program is asymptotically if f(n) has exactly n
instructions?
a. n2
b. i
c. 1
d. 0
5. This algorithm is a ____ algorithm.
j = a[0] + a[1]
a. Linear
b. Cubic
c. Logryhthmic
d. Constant time
6. In a sequence of loops, which one determines the asymptotic behavior of the program?
a. Their combined number of steps
b. The fastest

c. Depends on the coding language
d. The slowest
7. Why do people figure out the O complexity of an algorithm?
a. It's more accurate than the theta complexity.
b. It gives a better value than the theta complexity.
c. It helps determine the value of n.
d. It's easier to figure out than the theta complexity.
8. The algorithm is Ω( something ) means
a. A number is > something
b. A number is < something
c. A number is = something
d. A number is ≥ something
9. 4n + 7 ∈
a. Θ( n )
b. Θ( 4n )
c. Θ(4)
d. Θ( n + 7)
10. Which of the following statements is false?
a. A Θ( n2 ) algorithm is O( n4 ).
b. A Θ( n3 ) algorithm is O( n3 ).
c. A Θ( n ) algorithm is O( n2 ).
d. A Θ( n ) algorithm is O( 1 ).
11. Stacks are containers that operate in a _____ manner.
a. LIFO
b. FILO
c. LILO (Last in Last Out)
d. FIFO (First in First Out)
12. Which container class in this list meets the requirements of a stack?
a. Long_queue
b. Flex_list
c. Vector
d. Random
13. The back member function of the queue class returns:
a. The name of the queue
b. The oldest element
c. The largest element
d. The newest element
14. The empty member function of the queue class:
a. Fills any empty slots

b. Will remove all data from the queue
c. Lets you know how many slots are empty
d. Lets you know if the queue is empty or not
15. What is the main difference between single and doubly linked lists?
a. Doubly linked lists are more efficient
b. Doubly link lists have twice as big.
c. Single-linked lists are twice as big as doubly-linked lists
d. Single-linked lists can only be iterated forwards.