Processing math: 100%

CS3 Data Structures & Algorithms - BC and Slides -

Chapter 17 CS3Slides

Show Source | | About « 17.13. Lists :: Contents :: 17.15. Memory Cues and Resumption Strategies »

17.14. Math Background¶

17.14.1. Math Background¶

17.14.1.1. Topics¶

Set concepts and notation

Logarithms

To store codes for $n$ objects required $\log n$ bits. $n$ bits can represent $2^n$ objects

You can cut $n$ objects in half $\log n$ times

$n = 2^{\log_2 n}$

Recursion

Induction Proofs

Summations

Recurrence Relations

Estimation

17.14.1.2. Estimation Techniques¶

Known as “back of the envelope” or “back of the napkin” calculation

1. Determine the major parameters that affect the problem.

2. Define an equation that relates the parameters to the problem.

3. Select values for the parameters, and apply the equation to yield an estimated solution.

17.14.1.3. Estimation Example¶

How many library bookcases does it take to store books totaling one million pages?

Estimate

- Pages/inch

- Feet/shelf

- Shelves/bookcase

Contact Us || Privacy | | License « 17.13. Lists :: Contents :: 17.15. Memory Cues and Resumption Strategies »