Review for Midterm
The exam will be held during class on Monday, Nov. 1. It will be
closed-book. There will be 3 pages of questions and a fourth blank
page for rough work. You are to write directly on the exam pages.
When studying for the exam carefully look over:
(1) Notes you've taken from class (you are only responsible for
those topics that were covered in class)
(2) Textbook (Chapters 1, 2, 3 with emphasis of Chapters 1 and 3)
(3) Homework (Solutions to Assignment 1 are available on TA's homepage)
The following is a list of the major topics you should know for the
Midterm.
Computing Powers
Staightforward algorithm is extremely inefficient for even relatively small
inputs since computing time is exponential when input size measured in terms of the number of digits of n
Egyptian Powers -- efficient algorithm, but assumes n is a power of 2
PowersRec -- efficient for all n, computing time is linear in the number of digits on n. Know recurrence relation on which PowersRec is based.
Euclidean Algorithm
Computing square roots and Newton's method
Evaluating Polynomials
Mathematical Notation and Background
Logarithm function
Arithmetic series
Geometric series
Binomial coefficients and binomial expansion
Taking deratives to obtain new formula
Recursion
Repeated substitution (unwinding) solutions to recurrence relations of
the form
t(n) = at(n-1) + b or t(n) = t(n/2) + b (for n a power
of 2)
Data Structures
Review solutions to Assignment 1 that involve data structures.
Complexity of an Algorithm
Best-case B(n)
Worst-case W(n)
Average A(n)
Design and analysis of the following algorithms:
Linear search
Binary search
Optimal algorithm for computing both maximum and minimum element in a list
Insertionsort
Glimpse of lower bound theory
Problem of finding maximum element in a list
Problem of adjacent-key comparison-based sorting of a list
- permutation
- inversions
- sorted list has no inversions
- adjacent-key comparison-based sort removes at most one inversion with each comparison
- reverse permutation has the most inversions, i.e., C(n,2) = n(n-1)/2 inversions
- n(n-1)/2 is a sharp lower since there exist adjacent-key comparision-based
sorts such as Bubblesort that have worst-case complexity n(n-1)/2.
Asymptotic growth rates of functions
Asymptotic notation (big) Theta, big Oh, (big) Omega
Establishing order relationships:
f(n) and g(n) have the same order
f(n) has smaller order
g(n) has smaller order
Establish using limits and L'Hopital's rule or from the definitions
Order formulas for series suchs as sum of logarithms and harmonic series