Exam 1 is Thursday 6 7 30pm You should review material going back to the first week For example Rules for logs calculus sums expected values Constructive induction the Fibonacci examples and proofs Algorithms that you ve seen and now analyzed in more detail such as transitive closure several sorts Techniques to go from code or pseudocode to either summations or recurrences The five asymptotic relationships their quantified definitions how to construct c and then n0 for the ones that start with existential quantifiers the limit based definitions how we can use these relationships to answer specific questions Recurrence trees and how they can be used to get nice Big O and Big Omega bounds We are given some recurrence relation that doesn t fit into the Master Theorem well such as T 1 1 T n T n 4 T 3n 4 1 Things we want to observe Structure of the tree Symmetrical Density Number of levels Work done At full interior levels At leaves Asymptotic relationships Big Omega Big O What is the impact of the f n What if we make a change to only the f n in the previous recurrence T 1 1 T n T n 4 T 3n 4 n
View Full Document
Unlocking...