homework & practice 6 1

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

6th grade (Illustrative Mathematics)

Unit 1: area and surface area, unit 2: introducing ratios, unit 3: unit rates and percentages, unit 4: dividing fractions, unit 5: arithmetic in base ten, unit 6: expressions and equations, unit 7: rational numbers, unit 8: data sets and distribution.

Please ensure that your password is at least 8 characters and contains each of the following:

• a special character: @$#!%*?&

• 888-309-8227
• 732-384-0146

New User Registration

Forgot Password

enVision MATH Common Core 6, Grade: 6 Publisher: Scott Foresman Addison Wesley

Envision math common core 6, title : envision math common core 6, publisher : scott foresman addison wesley, isbn : 328672645, isbn-13 : 9780328672646, use the table below to find videos, mobile apps, worksheets and lessons that supplement envision math common core 6., textbook resources.

• Call us toll-free
• FAQs – Frequently Asked Questions
• Contact Lumos Learning – Proven Study Programs by Expert Teachers

Follow us: Lumos Learning -->

• 2024 © Lumos Learning
• Privacy Policy - Terms of Service - Disclaimers

PARCC® is a registered trademark of PARCC, Inc. Lumos Learning, is not owned by or affiliated in any fashion with PARCC, Inc... Read More

PARCC® is a registered trademark of PARCC, Inc. Lumos Learning, is not owned by or affiliated in any fashion with PARCC, Inc., the Partnership for the Assessment of Readiness for College and Careers, nor any state of the Union. Neither PARCC, Inc., nor The Partnership for the Assessment of Readiness for College and Careers, nor any member state has endorsed this product. No portion of any fees or charges paid for any products or services Lumos Learning offers will be paid or inure to the benefit of PARCC, Inc., or any state of the Union

SBAC is a copyright of The Regents of the University of California – Smarter Balanced Assessment Consortium, which is not aff... Read More

SBAC is a copyright of The Regents of the University of California – Smarter Balanced Assessment Consortium, which is not affiliated to Lumos Learning. The Regents of the University of California – Smarter Balanced Assessment Consortium, was not involved in the production of, and does not endorse these products or this site.

ACT® Aspire™ is a registered trademark of ACT Aspire LLC., which is not affiliated to Lumos Learning. ACT Aspire LLC, was not... Read More

ACT® Aspire™ is a registered trademark of ACT Aspire LLC., which is not affiliated to Lumos Learning. ACT Aspire LLC,was not involved in the production of, and does not endorse these products or this site.

Florida Department of Education is not affiliated to Lumos Learning. Florida department of education, was not involved in the... Read More

Florida Department of Education is not affiliated to Lumos Learning. Florida department of education, was not involved in the production of, and does not endorse these products or this site.

Indiana Department of Education is not affiliated to Lumos Learning. Indiana department of education, was not involved in the... Read More

Indiana Department of Education is not affiliated to Lumos Learning. Indiana department of education, was not involved in the production of, and does not endorse these products or this site.

Mississippi Department of Education is not affiliated to Lumos Learning. Mississippi department of education, was not involved... Read More

Mississippi Department of Education is not affiliated to Lumos Learning. Mississippi department of education, was not involved in the production of, and does not endorse these products or this site.

Ohio Department of Education is not affiliated to Lumos Learning. Ohio department of education, was not involved in the prod... Read More

Ohio Department of Education is not affiliated to Lumos Learning. Ohio department of education, was not involved in the production of, and does not endorse these products or this site.

Tennessee Department of Education is not affiliated to Lumos Learning. Tennessee department of education, was not involved... Read More

Tennessee Department of Education is not affiliated to Lumos Learning. Tennessee department of education, was not involved in the production of, and does not endorse these products or this site.

Georgia Department of Education is not affiliated to Lumos Learning. Georgia department of education, was not involved... Read More

Georgia Department of Education is not affiliated to Lumos Learning. Georgia department of education, was not involved in the production of, and does not endorse these products or this site.

Missouri Department of Education is not affiliated to Lumos Learning. Missouri department of education, was not involved... Read More

Missouri Department of Education is not affiliated to Lumos Learning. Missouri department of education, was not involved in the production of, and does not endorse these products or this site.

Louisiana Department of Education is not affiliated to Lumos Learning. Louisiana department of education, was not involved... Read More

Louisiana Department of Education is not affiliated to Lumos Learning. Louisiana department of education, was not involved in the production of, and does not endorse these products or this site.

• Skip to main content
• Skip to primary sidebar
• Skip to footer

Additional menu

Khan Academy Blog

Free Math Worksheets — Over 100k free practice problems on Khan Academy

Looking for free math worksheets.

You’ve found something even better!

That’s because Khan Academy has over 100,000 free practice questions. And they’re even better than traditional math worksheets – more instantaneous, more interactive, and more fun!

Just choose your grade level or topic to get access to 100% free practice questions:

Kindergarten, basic geometry, pre-algebra, algebra basics, high school geometry.

• Trigonometry

Statistics and probability

High school statistics, ap®︎/college statistics, precalculus, differential calculus, integral calculus, ap®︎/college calculus ab, ap®︎/college calculus bc, multivariable calculus, differential equations, linear algebra.

• Addition and subtraction
• Place value (tens and hundreds)
• Addition and subtraction within 20
• Addition and subtraction within 100
• Addition and subtraction within 1000
• Measurement and data
• Counting and place value
• Measurement and geometry
• Place value
• Measurement, data, and geometry
• Add and subtract within 20
• Add and subtract within 100
• Add and subtract within 1,000
• Money and time
• Measurement
• Intro to multiplication
• 1-digit multiplication
• Addition, subtraction, and estimation
• Intro to division
• Understand fractions
• Equivalent fractions and comparing fractions
• More with multiplication and division
• Arithmetic patterns and problem solving
• Quadrilaterals
• Represent and interpret data
• Multiply by 1-digit numbers
• Multiply by 2-digit numbers
• Factors, multiples and patterns
• Add and subtract fractions
• Multiply fractions
• Understand decimals
• Plane figures
• Measuring angles
• Area and perimeter
• Units of measurement
• Decimal place value
• Add decimals
• Subtract decimals
• Multi-digit multiplication and division
• Divide fractions
• Multiply decimals
• Divide decimals
• Powers of ten
• Coordinate plane
• Algebraic thinking
• Converting units of measure
• Properties of shapes
• Ratios, rates, & percentages
• Arithmetic operations
• Negative numbers
• Properties of numbers
• Variables & expressions
• Equations & inequalities introduction
• Data and statistics
• Negative numbers: addition and subtraction
• Negative numbers: multiplication and division
• Fractions, decimals, & percentages
• Rates & proportional relationships
• Expressions, equations, & inequalities
• Numbers and operations
• Solving equations with one unknown
• Linear equations and functions
• Systems of equations
• Geometric transformations
• Data and modeling
• Volume and surface area
• Pythagorean theorem
• Transformations, congruence, and similarity
• Arithmetic properties
• Factors and multiples
• Reading and interpreting data
• Negative numbers and coordinate plane
• Ratios, rates, proportions
• Equations, expressions, and inequalities
• Exponents, radicals, and scientific notation
• Foundations
• Algebraic expressions
• Linear equations and inequalities
• Graphing lines and slope
• Expressions with exponents
• Quadratics and polynomials
• Equations and geometry
• Algebra foundations
• Solving equations & inequalities
• Working with units
• Linear equations & graphs
• Forms of linear equations
• Inequalities (systems & graphs)
• Absolute value & piecewise functions
• Exponents & radicals
• Exponential growth & decay
• Quadratics: Multiplying & factoring
• Quadratic functions & equations
• Irrational numbers
• Performing transformations
• Transformation properties and proofs
• Right triangles & trigonometry
• Non-right triangles & trigonometry (Advanced)
• Analytic geometry
• Conic sections
• Solid geometry
• Polynomial arithmetic
• Complex numbers
• Polynomial factorization
• Polynomial division
• Polynomial graphs
• Rational exponents and radicals
• Exponential models
• Transformations of functions
• Rational functions
• Trigonometric functions
• Non-right triangles & trigonometry
• Trigonometric equations and identities
• Analyzing categorical data
• Displaying and comparing quantitative data
• Summarizing quantitative data
• Modeling data distributions
• Exploring bivariate numerical data
• Study design
• Probability
• Counting, permutations, and combinations
• Random variables
• Sampling distributions
• Confidence intervals
• Significance tests (hypothesis testing)
• Two-sample inference for the difference between groups
• Inference for categorical data (chi-square tests)
• Advanced regression (inference and transforming)
• Analysis of variance (ANOVA)
• Scatterplots
• Data distributions
• Two-way tables
• Binomial probability
• Normal distributions
• Displaying and describing quantitative data
• Inference comparing two groups or populations
• Chi-square tests for categorical data
• More on regression
• Prepare for the 2020 AP®︎ Statistics Exam
• AP®︎ Statistics Standards mappings
• Polynomials
• Composite functions
• Probability and combinatorics
• Limits and continuity
• Derivatives: definition and basic rules
• Derivatives: chain rule and other advanced topics
• Applications of derivatives
• Analyzing functions
• Parametric equations, polar coordinates, and vector-valued functions
• Applications of integrals
• Differentiation: definition and basic derivative rules
• Differentiation: composite, implicit, and inverse functions
• Contextual applications of differentiation
• Applying derivatives to analyze functions
• Integration and accumulation of change
• Applications of integration
• AP Calculus AB solved free response questions from past exams
• AP®︎ Calculus AB Standards mappings
• Infinite sequences and series
• AP Calculus BC solved exams
• AP®︎ Calculus BC Standards mappings
• Integrals review
• Integration techniques
• Thinking about multivariable functions
• Derivatives of multivariable functions
• Applications of multivariable derivatives
• Integrating multivariable functions
• Green’s, Stokes’, and the divergence theorems
• First order differential equations
• Second order linear equations
• Laplace transform
• Vectors and spaces
• Matrix transformations
• Alternate coordinate systems (bases)

Frequently Asked Questions about Khan Academy and Math Worksheets

Why is khan academy even better than traditional math worksheets.

Khan Academy’s 100,000+ free practice questions give instant feedback, don’t need to be graded, and don’t require a printer.

What do Khan Academy’s interactive math worksheets look like?

Here’s an example:

What are teachers saying about Khan Academy’s interactive math worksheets?

“My students love Khan Academy because they can immediately learn from their mistakes, unlike traditional worksheets.”

Is Khan Academy free?

Khan Academy’s practice questions are 100% free—with no ads or subscriptions.

What do Khan Academy’s interactive math worksheets cover?

Our 100,000+ practice questions cover every math topic from arithmetic to calculus, as well as ELA, Science, Social Studies, and more.

Is Khan Academy a company?

Khan Academy is a nonprofit with a mission to provide a free, world-class education to anyone, anywhere.

Want to get even more out of Khan Academy?

Then be sure to check out our teacher tools . They’ll help you assign the perfect practice for each student from our full math curriculum and track your students’ progress across the year. Plus, they’re also 100% free — with no subscriptions and no ads.

Get Khanmigo

The best way to learn and teach with AI is here. Ace the school year with our AI-powered guide, Khanmigo. 

For learners     For teachers     For parents

Homework 1 - Spring 2024

This homework covers the material from lectures 1 to 6.

Due date: May 21st, 10pm Waterloo time.

PDF version of Homework 1 .

LaTeX template , in case you want to write it in LaTeX.

Required Exercises

Problem 1 - amortized analysis (10 points).

Design a data structure to support the following two operations for a dynamic multiset $S$ of integers, which allows duplicate values:

• INSERT($S, x$) inserts $x$ into $S$
• DELETE-LARGER-HALF($S$) deletes the largest $\lceil |S|/2 \rceil$ elements from $S$

Show how to implement this data structure so that any sequence of $m$ INSERT and DELETE-LARGER-HALF operations runs in $O(m)$ time. Your implementation should also include a way to output the elements of $S$ in $O(|S|)$ time.

Hint: to delete larger half, need to find the median. You can use the result that there is a linear time algorithm for finding the median in an unordered array (if you don’t know this result, you should learn about it - it is pretty cool).

Problem 2 - Amortized Analysis (10 points)

An ordered stack is a data structure that stores a sequence of items and supports the following operations:

• OrderedPush($x$) removes all items smaller than $x$ from the beginning of the sequence and then adds $x$ to the beginning of the sequence.
• Pop() deletes and returns the first item in the sequence, or NULL if the sequence is empty.

Suppose we implement an ordered stack with a simple linked list, using the obvious OrderedPush and Pop algorithms. Prove that if we start with an empty data structure, the amortized cost of each OrderedPush or Pop operation is $O(1)$.

Problem 3 - Concentration Inequalities (15 points)

The simplest model for a random graph consists of $n$ vertices, and tossing a fair coin for each pair $\{i, j\}$ to decide whether this edge should be present in the graph. Call this model $G(n, 1/2)$. A triangle is a set of $3$ vertices with an edge between each pair.

• What is the expected number of triangles?
• What is the variance?
• Show that the number of triangles is concentrated around the expectation and give an expression for the bound in the decay of probability.

Problem 4 - Concentration Inequalities (15 points)

In this problem, we are in the setting where given a set $S$ (which is not known to us - and this set does not have repeated elements), we only have access to $S$ by querying a random element from $S$ uniformly at random. Thus, if we want to sample $s$ elements from $S$, we will obtain a sequence of elements $a_1, \ldots, a_s \in S$ where each $a_k$ was drawn from $S$ uniformly at random. Thus it could be the case where $a_i = a_j$ for some $i \neq j$.

Part 1 (5 points)

Show that given a set $S$ of $n$ numbers in $[0, 1]$ it is impossible to estimate the value of the median within $1.1$ multiplicative approximation factor with $o(n)$ samples.

Hint: to show an impossibility result you show two different sets of $n$ numbers that have very different medians but which generate, with high probability, identical samples of size $o(n)$.

Part 2 (10 points)

Given a set $S$ of $n$ numbers as in part 1, now calculate the number of samples needed (as a function of $t$) so that the following is true: with high probability, the median of the sample has at least $n/2 - t$ numbers from $S$ less than it and at least $n/2 - t$ numbers of $S$ more than it.

Problem 5 - Balls and Bins (10 points)

Consider again the experiment in which we toss $m$ labeled balls at random into $n$ labeled bins, and let the random variable $X$ be the number of empty bins. We have seen that $\mathbb{E}[X] = n \cdot \left( 1 - \frac{1}{n} \right)^m$.

By writing $X = \sum_i X_i$ for suitable random variables $X_i$, show how to derive the following exact formula for the variance of $X$: $$ Var[ X ] = n \cdot \left( 1 - \frac{1}{n} \right)^m + n(n-1) \cdot \left( 1 - \frac{2}{n} \right)^m - n^2 \cdot \left( 1 - \frac{1}{n} \right)^{2m} $$

What is the asymptotic value (as $n \rightarrow \infty$) of $Var[ X ]$ in the cases $m = n$ and $m = n \ln(n)$?

Hint: you may use the approximations $(1 - x/n)^n \sim e^{-x} \cdot (1 - x^2/2n)$ and $(1 - 1/n)^{xn} \sim e^{-x} \cdot (1 - x/2n)$

• When throwing $n$ balls into $n$ bins, what is the expected number of bins with exactly one ball? Compute an exact formula and its asymptotic approximation.

Problem 6 - Coupon Collector (10 points)

Let us consider the coupon collector problem: we toss $m = n \log n + cn$ balls into $n$ bins, where $c$ is a constant, and we are interested in the probability that there is no empty bin. We saw in class that $$ Pr[ \text{some bin is empty} ] \leq n \cdot \left( 1 - \frac{1}{n} \right)^m \sim n \cdot \dfrac{1}{e^{m/n}} = \dfrac{1}{e^c}. $$

Prove that $$ Pr[ \text{some bin is empty} ] = \Omega\left( \dfrac{1}{e^c} - \dfrac{1}{2e^{2c}} \right). $$

Hint: Inclusion-Exclusion.

Part 2 (5 points)

Consider the following variation of the coupon collector’s problem. Each box of cereal contains one of $2n$ different coupons. The coupons are organized into $n$ pairs, so that coupons 1 and 2 are a pair, coupons 3 and 4 are a pair, and so on. Once you obtain one coupon from every pair, you can obtain a prize. Assuming that each coupon in each box is chosen independently and uniformly at random from the $2n$ possibilities, what is the expected number of boxes you must buy before you can claim the prize?

Problem 7 - More hash functions (15 points)

Consider the following examples of hash families. For each one, prove that it is 2-universal or give a counterexample. The universe for the hash functions is $U = \mathbb{F}_p$ and the image is $\{0, \ldots, n-1 \}$.

Let $p$ be a prime number and $n \leq p$ be an integer. Let $$\mathcal{H} := \{ h_a(x) = (ax \bmod p) \bmod n \ \mid \ a \in \{ 1, \ldots, p-1 \} \} $$

Let $m$ be an integer multiple of $n$, where $m \geq n$ and the universe is $\{0,\ldots, m-1\}$. Let $$\mathcal{H} := \{ h_{a, b}(x) = (ax + b \bmod m) \bmod n \ \mid \ a \in \{ 1, \ldots, m-1 \}, b \in \{ 0, 1, \ldots, m-1 \} \} $$

Part 3 (5 points)

Let $p$ be a prime number and $n \leq p$ be an integer. Let $$\mathcal{H} := \{ h_{a, b}(x) = (ax + b \bmod p) \bmod n \ \mid \ a, b \in \{ 0,1, \ldots, p-1 \}, a \neq 0 \} $$

Problem 8 - Karger strikes back (15 points)

To improve the probability of success of the randomized min-cut algorithm, it can be run multiple times.

Consider running the algorithm twice. Determine the number of edge contractions and bound the probability of finding a min-cut.

Consider the following variation. Starting with a graph with $n$ vertices, first contract the graph down to $k$ vertices using the randomized min-cut algorithm. Make $\ell$ copies of the graph with $k$ vertices, and now run the randomized algorithm on these reduced graphs independently. Determine the number of edge contractions and bound the probability of finding a min-cut.

Find optimal (or at least near-optimal) values of $k$ and $\ell$ for the variation in the previous part that maximizes the probability of finding a min-cut while using the same number of edge contractions as running the original algorithm twice.

Practice Problems

You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)

Problem 1 - Amortized Analysis - from CLRS chapter 17

A stack $S$ is a data structure that supports the following operations:

• PUSH($S, x$) pushes object $x$ on the top of stack $S$
• POP($S$) pops the top of the stack $S$ and returns the popped object. If one calls POP on an empty stack it returns an error.

We will now modify the stack structure to support the following operation:

• MULTIPOP($S, k$) removes the $k$ top objects of stack $S$, popping the entire stack if the number of elements in $S$ is less than $k$.

First Question: what is the worst case performance per operation of a sequence of $n$ operations above? Here we want you to give an upper bound on the complexity of the operations PUSH, POP and MULTIPOP.

Second Question: what is the amortized cost of $n$ operations? Use the three methods of amortized analysis to obtain the same bound.

Problem 2 - Amortized Analysis - from Jeff Erickson’s book

Suppose we can insert or delete an element into a hash table in $O(1)$ time, and that we can construct a hash table of size $n$ in $Cn$ time, where $C > 0$ is some absolute constant. In order to ensure that our hash table is always big enough, without wasting a lot of memory, we will use the following global rebuilding rules:

• After an insertion, if the table is more than $3/4$ full, we allocate a new table twice as big as our current table, insert everything into the new table, and then free the old table.
• After a deletion, if the table is less than $1/4$ full, we allocate a new table half as big as our current table, insert everything into the new table, and then free the old table.

Show that, starting from an empty hash table, for any sequence of insertions and deletions, the amortized time per operation is still $O(1)$.

Problem 3 - Splay Trees

In this problem we will work out some splaying counterexamples;

Single rotations don’t work for splay trees. To show this, consider a degenerate $n$-node linked-list shaped binary tree where each node’s right child is empty. Suppose that the (only) leaf is splayed to the root by single rotations. Show the structure of the tree after this splay. Generalize this to argue that there is a sequence of $n/2$ splays (each splay using only single rotations) that each take at least $n/2$ work.

Now from the same starting tree, show the final structure after splaying the leaf with (zig-zig) double rotations. Explain how this splay has made much more progress than single rotations in “improving” the tree.

Given the theorem about access time in splay trees, it is tempting to conjecture that splaying does not create trees in which it would take a long time to find an item. Show this conjecture is false by showing that for large enough $n$, it is possible to restructure any binary tree on $n$ nodes into any other binary tree on $n$ nodes by a sequence of splay requests. Conclude that it is possible to make a sequence of requests that cause the splay tree to achieve any desired shape.

Hint: start by showing how you can use splay operations to make a specified node into a leaf, then recurse.

Problem 4 - Probability - from MU'05 chapter 1

Consider the set $\{ 1, \ldots, n \}$. We generate a subset $X$ of this set as follows: a fair coin is flipped independently for each element of the set; if the coin lands heads then the element is added to $X$, and otherwise it is not. Argue that the resulting set $X$ is equally likely to be any one of the $2^n$ possible subsets.

Suppose that two sets $X$ and $Y$ are chosen independently and uniformly at random from all the $2^n$ subsets of $\{ 1, \ldots, n \}$. Determine $Pr[X \subseteq Y]$ and $Pr[X \cup Y = \{1, \ldots, n \}]$.

Hint: use part 1 of the problem.

Problem 5 - Probability

• Consider the following probabilistic process:
• start with $ctr = 0$
• Repeat $n$ times: toss a fair coin, and if it comes up heads, make $ctr += 1$. Otherwise, make $ctr -= 1$.

If $X$ is the random variable defined as the value of our counter $ctr$ at the end of the process above:

• Compute $\mathbb{E}[ X ]$
• For even $n$, show that $\Pr[X = 0] \sim \sqrt{2/(\pi n)}$. What happens for odd $n$?

Problem 6 - Covariance and Variance of Correlated Random Variables

In this question we will explore how to use covariance to compute the variance of correlated random variables

• Let $X_1, \ldots, X_n$ be random variables such that $X_i = X_j$ and $$X_1 = \begin{cases} 1, \text{ with probability } 1/2 \\ 0, \text{ otherwise} \end{cases}$$ thus, we are in the case where the random variables are the same random variable.

Let $X = x_1 + X_2 + \cdots + X_n$. Compute $Var[ X ]$.

• Let $X_1, \ldots, X_n$ be random variables such that $$X_1 = \begin{cases} 1, \text{ with probability } 1/2 \\ 0, \text{ otherwise} \end{cases}$$ and for $2 \leq i \leq n$ we have $$X_i = \begin{cases} X_1, \text{ with probability } 1/(2i) \\ 1 - X_1, \text{ otherwise} \end{cases}$$

Let $X = X_1 + X_2 + \cdots X_n$. Compute $Var [ X ]$.

Problem 7 - Martingales

Consider a fair game in a casino: on each play, you may stake any amount $S$ of money. You win or lose with probability $1/2$ each time (and all instances of the game are independent). If you win you get back your stake plus $S$, and if you lose you lose your stake.

What is the expected number of plays until you first win?

The following gambling strategy, known as the “martingale,” was popular in European casinos in the 18th century: on the first play, stake $1$; on the second play stake $2$; on the $k^{th}$ play, stake $2^{k-1}$. Stop playing and leave the casino when you first win!

Show that if you follow the martingale strategy, you will leave the casino $1$ unit of money richer with probability 1! (this is probably a reason why this strategy is banned in most casinos. Also, this course is not providing any gambling advice)

• Let us know discuss the catch in the strategy above: let $X$ be the random variable that measures your maximum loss before winning. Show that $\mathbb{E}[ X ] = \infty$. What does this imply about your ability to play the matringale strategy in practice?

Problem 8 - Generating random strings

Alice and Bob have a fair coin and they are trying to generate a random sequence of 2n coin tosses containing exactly $n$ heads and $n$ tails.

Alice suggests to flip the coin $2n$ times. If we get exactly $n$ heads, output the sequence; otherwise, try again. How many tosses do you expect Alice will have to make under this scheme?

Bob claims that he has a much more efficient scheme: flip the coin until you have either $n$ heads or $n$ tails. Output this sequence, padded at the end with tails or heads respectively to make the total length $2n$. Clearly this scheme requires at most $2n$ tosses. Is this a good scheme? Justify your answer with a proof.

Suggest a simple scheme for solving this problem that is better than the previous two schemes. How many tosses does your scheme require in expectation?

Problem 9 - Concentration Inequalities

Questions from lecture 3:

Is Markov’s inequality tight? If it is, give examples of random variables for which it is tight.

Give examples of discrete probability distributions which do not have a $k^{th}$ moment. Also give examples of discrete probability distributions which do not have a $k^{th}$ central moment.

Can you generalize Chebyshev’s inequality for higher order moments?

Work out the proof of the lower tail bound for Chernoff’s bound.

Work out the proof of Hoeffding’s generalization of Chernoff’s inequality.

Problem 10 - Reservoir Sampling - from Mu'05 chapter 2

Suppose we have a sequence of items passing by one at a time. We want to maintain a sample of one item with the property that it is uniformly distributed over all the items that we have seen at each step. Moreover, we want to accomplish this without knowing the total number of items in advance or storing all of the items that we see.

• Consider the following algorithm, which stores just one item in memory at all times. When the first item appears, it is stored in memory. When the $k^{th}$ item appears, it replaces the item in memory with probability $1/k$. Show why this algorithm solves the problem.

Note: the above algorithm is called reservoir sampling.

• Suppose that we modify the reservoir sampling algorithm from the previous part so that, when the $k^{th}$ item appears, it replaces the item in memory with probability $1/2$. Describe the distribution of the item in memory.

Problem 11 - Exploring Chernoff

In this question, we will think about the following: when are Chernoff bounds actually giving us any non-trivial information?

Let $p \in (0,1/10)$ and $X$ be the random variable which takes value $1/p$ with probability $p$, and takes the value $0$ with probability $1-p$. Let $\varepsilon = 1/2$.

• what is the expectation of $X$?
• why can we use Chernoff here, since $X$ as defined is not Poisson Trial? What do we have to do to use Chernoff here?
• what does Chernoff say about $\Pr[|X - \mathbb{E}[ X ]| \geq \varepsilon \cdot \mathbb{E}[ X ] ]$?

One may be tempted to think in the example above that the reason why Chernoff didn’t give any non-trivial information was because the expectation is small compared to $\varepsilon^2$. However, consider the following random variable: $Y = \alpha \cdot X$, where $X$ is the random variable of part 1 and $\alpha$ can be any positive real number. Prove that even though the expectation can now be large compared to $\varepsilon^2$, Chernoff still does not say anything non-trivial.

Hint: for Chernoff we need Poisson trials.

• What is the minimum number of independent copies $X_i$ of $X$ needed if we want Chernoff to say anything meaningful for $\Pr[|Z - \mathbb{E}[Z]| \geq \varepsilon \cdot \mathbb{E}[Z] ]$, where $Z = \sum_{i=1}^t X_i$?

Problem 12 - Bashing

Perfect hashing is nice, but does have the drawback that the perfect hash function has a lengthy description (since you have to describe the second-level hash function for each bucket). Consider the following alternative approach to producing a perfect hash function with a small description. Define bi-bucket hashing , or bashing , as follows. Given $n$ items, allocate two arrays of size $n^{3/2}$. When inserting an item, map it to one bucket in each array, and place it in the emptier of the two buckets.

• Suppose a random function (i.e., all function values are uniformly random and mutually independent) is used to map each item to buckets. Give a good upper bound on the expected number of collisions (i.e., the number of pairs of items that are placed in the same bucket).

Hint: what is the probablility that the $k^{th}$ inserted item collides with some previously inserted item?

Argue that bashing can be implemented efficiently, with the same expected outcome, using the ideas from 2-universal hashing.

Conclude an algorithm with linear expected time (ignoring array initialization) for identifying a perfect bash function for a set of $n$ items. How large is the description of the resulting function?

Problem 13 - Karger’s algorithm: the cut menace

Another problem about Karger’s randomized algorithm for minimum cut:

• Suppose Karger’s algorithm is applied to a tree. Show that it finds a minimum cut in the tree with probability 1.
• Consider the following modification of Karger’s algorithm: instead of choosing an edge uniformly at random and merging the endpoints, the algorithm chooses any two distinct vertices uniformly at random and merges them. Show that for any $n$ there is a graph $G_n$ with $n$ vertices such that when the modified algorithm is run on $G_n$, the probability that it finds a minimum cut is exponentially small in $n$.
• How many times would you have to repeat the modified algorithm of the previous part to have a reasonable chance of finding a minimum cut? What does this tell us about the practicality of the modified algorithm?
• Show that for any $n \geq 3$ there is a connected graph $G_n$ with $n$ vertices that has $n(n-1)/2$ distinct minimum cuts.

Last updated on May 5, 2023

Edit this page