Study Guide- cs 372 for quiz 1
1. Understand how queues and stacks work and how you store them.
2. Understand the significance of using sorted lists and unsorted lists and representing them as arrays, circular arrays, and linked lists.
3. Be able to go from a graph to an adjacency list.
4. When is a graph connected?
5. How do you determine the cycles of a graph.
6. What is a tree.
7. What is a heap.? How do you use a heap to sort numbers?
8. What does it mean to be 0 ( log 2 n ) , 0 (n), 0(n2 ) , 0(n3 ), 0 ( n log 2 n ), 0(n!) 0( 2n ).
similarly with omega and theta
If n is changed by 8, how do these change?
9If the time of the computation is 3 seconds for n = 128 and 24 seconds for n=256, what is the order of the computation?
If the time of the computation is 21 seconds for n =128 and 24 seconds for n = 256, what is the order of the computation?
10 Given examples like
(a)for i= 1 to n
for j = i+1 to n
2 multiplications
(b) for i = 1 to n
for j= i+1 to n
for k = i+1 to n
4 multiplications
c) for i = 1 to n
for j= i+1 to n
for k = i+1 to j
4 multiplications
(d) for i = 1 to n
j=i
while (j< n)
2 comparisons (just order)
j = 2*j;
(e) func(n)
if n==1
return 1
else
do n multiplications;
func(n-1)
(f) func(n,i)
if n==1
1 comparison
else
n comparisons
func(n/2)
what is the order of the computation? What is the coefficient of the order of computation?
11. Show how you would determine which is eventually faster.
a. 2n^3 + 3 n^2 or 16n^2.
b. 20 n^(3/2) or 5n log n.
12 Solve recurrence relations like
a. x(n) = x(n-1) +2, x(1)= 0
b. x(n) = 2x(n-1) + 2, x(1)=1
c. x(n)= x(n-1) + n*n
d. x(n) =x(n/2) + 1;
Solving second order linear difference equations.
a y(n) + by(n-1) + cy(n-2) =0.