# Difference: ExamTwoStudyGuide (1 vs. 6)

#### Revision 62019-04-19 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="Math391F2016"

# Algorithm Analysis and Design

### Exam 2 Study Guide

The questions will largely be similar to the exercises in the text and homework. Study the following sections carefully, and be able to solve any of the problems in the exersise or problems set sections refered to below.

>
>

### Recursion Relations

>
>
Solve with expansion or Master Theorm

##### Chapter 4 - Divide-and-Conquer
• Use of recursion for this method
• Recursive analysis using :

#### Revision 52016-11-14 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="Math391F2016"

# Algorithm Analysis and Design

### Exam 2 Study Guide

Line: 23 to 23

##### Chapter 11 - Hash Tables
• Review hash table and direct lookup operation, and exercises.
##### Chapter 15 Dynamic Programming
>
>
• The cut-rod problem and it solution, analysis, and sections exercises.
• Elements of dynamic programming (15.3).
• What is an optimal substructor? How is it used?
• How does it differ from greedy solutions?
• What is memoization?
• Exercises for 15.3
• Be able to create a dynamic algorithm for an appropriate problem.
\ No newline at end of file

#### Revision 42016-11-13 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="Math391F2016"

# Algorithm Analysis and Design

### Exam 2 Study Guide

Line: 20 to 20

• Understand the operation and analysis of a counting sort
• Review the exercises in 8.2 on 196-197.
• Review and understand radix sort, exercises on 199-200.
>
>
##### Chapter 11 - Hash Tables
• Review hash table and direct lookup operation, and exercises.

##### Chapter 15 Dynamic Programming
\ No newline at end of file

#### Revision 32016-11-13 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="Math391F2016"

# Algorithm Analysis and Design

### Exam 2 Study Guide

Line: 16 to 16
You may bring a one page "cheat-sheet" with the rules of the master's theorem on it.
##### Chapter 8 - Sorting in Linear Time
Changed:
<
<
>
>
• Review the exercises in 8.1 on 193-194.
• Understand the operation and analysis of a counting sort
• Review the exercises in 8.2 on 196-197.
• Review and understand radix sort, exercises on 199-200.

#### Revision 22016-11-12 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="Math391F2016"

# Algorithm Analysis and Design

### Exam 2 Study Guide

Line: 12 to 12

• The recursion-tree method
• The master method
>
>
Specifically be able to solve problems like 4-1 and 4-3 on pages 107-108

You may bring a one page "cheat-sheet" with the rules of the master's theorem on it.

#### Revision 12016-11-12 - JimSkon

Line: 1 to 1
>
>
 META TOPICPARENT name="Math391F2016"

# Algorithm Analysis and Design

### Exam 2 Study Guide

The questions will largely be similar to the exercises in the text and homework. Study the following sections carefully, and be able to solve any of the problems in the exersise or problems set sections refered to below.

##### Chapter 4 - Divide-and-Conquer
• Use of recursion for this method
• Recursive analysis using :
• substitution method
• The recursion-tree method
• The master method

##### Chapter 15 Dynamic Programming

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback