Chapter 3: Upper Bounds, Lower Bounds, Tight Bounds

Exam Study guide

Chapters

·  Chapter 2: Analyzing Algorithms

·  Chapter 3: upper bounds, lower bounds, tight bounds

·  Chapter 4: Master theorem

o  Exercises 4.3-1, 4.3-2, 4.3-3

·  Chapters 6, 7, 8: Sorts (see sample problem 3 below)

·  Chapter 12:

o  Exercise 12.2-1

·  Chapter 15: LCS, Optimal Binary search trees

o  Exercise 15.4-1, 15.5-1

·  Chapter 17: Amortized Analysis of binary counter

o  Exercise 17.1-2

·  Chapter 21: Sections 1 - 3

o  Exercises 21.2-2, 21.3-1

·  Chapter 22 : Graphs

o  Exercises 22.1-1, 22.1-2, 22.2-1, 22.2-2, 22.3-1, 22.3-2, 22.3-3, 22.3-4

o  Terms: cross edges, back edges, forward edges, strongly connected components, bridge, articulation point

·  Chapter 23: MST – Kruskal’s and Prim’s algorithms

o  Exercises 23.1-4

o  Figures 23.4, 23.5

·  Chapter 24: Single Source

o  Exercises: 24.1-1, 24.2-1, 24.3-1, 24.4-1, 24.4-2

·  Chapter 25: All Pairs - Floyd Warshall

o  Exercise 25.2-1

·  Chapter 34

o  Exercises 34.3-1, show that x is/ is not a possible solution for example NP problem

o  Prove P != NP

Sample problems

1.  Analyze the algorithm given below and provide the worst case running time of the algorithm. Show your work – You should provide a polynomial function and then arrive at a conclusion.

2.  Using the master theorem from Chapter 4.5, determine the order of magnitude of this recurrence

3.  For each of the sorts listed below, provide the worst case running time, a description of how the sort works, what the worst case data would look like, and your advice of when to use the particular sort.

4.  Provide an O(n2) algorithm for the x problem. Make sure you convince me it is O(n2)