101 Algorithms Questions
You Must Know
by
Amrinder Arora
Department of Computer Science,
The George Washington University
101 Algorithms Questions You Must Know
Copyright 2018, Amrinder Arora
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by an information storage and retrieval system - except by a reviewer who may quote brief passages in a review to be printed in a magazine or newspaper - without permission in writing from the publisher.
Table of Contents
Which Sections to Skip?
Which Ones to Read?
If you are looking for only challenging questions, jump straight to Section 4.
If you need a primer on asymptotic notation, review Section 2.
If you need a primer in basic set theory and series concepts, review Section 1.
If you need to review your data structures knowledge, review Section 3 as well.
Table of Figures
can be used to extend the exist matching {{c,f}, {e,d}}
An Accompaniment to
Analysis and Design of Algorithms
(Third Edition)
Amrinder Arora
Cognella Academic Publisher
ISBN: 978-1-5165-1310-9
Acknowledgments
This book would never have been possible if not for the constant prodding by numerous students who simply wanted to get an official style guide for the answers to the questions in their algorithms textbook! Many answers now officially collected here in this book have been exchanged with the students and have received their critiques and suggestions.
A special thanks is also due to my former classmates and friends Piyush Gupta, Fanchun Jin and Misam Abbas for helpful discussions in shaping this book. Also, thanks to Justo Correas and Jesus Correas, for constantly checking on me about the book, which kept the project going!
Thanks are also due to my humble and patient wife and kids Roman, Jessica and Nayan for their patience in dealing with me while I worked (or at least pretended to work!) on this book.
Section 1: Warm Up Questions
Question 1. Sets Basics
Consider A and B are two sets, such that |A| = 50 , and |A B| = 20 , and |B| = 85 . Find the value of |B A| .
Solution
We observe that elements of a set A can be place into two disjoint categories those that are also in B , and those that are not in B . That is,
A = (AB) (A-B)
Further, since these two categories are disjoint, we also have:
|A| = |AB| + |A-B|
Since we are given that |A| = 50 , and |A B| = 20 , we have that |A B| = 30
Similarly, we can conclude that:
|B| = |B A| + |B A|
Therefore, |B A| = 85 30 = 55.
Question 2. Log Basics
Given that log 2 = 0.3010 and log 3 = 0.4771 , find the value of log .
Solution
We recollect that log (xy) = log x + log y .
Therefore, using log 2 = 0.3010 and log 3 = 0.4771 , we can calculate log 6 = 0.3010 + 0.4771 = 0.7781
Further, we note that log b a log a b = 1 .
Therefore, log 10 = 1/0.7781 = 1.2851 .
Question 3. Recurrence Relation and Induction Basics
Given the series T(n) = T(n-1) + n and T(1) = 1 , find a closed-form expression for T(n) using principle of mathematical induction.
Solution
We can get a closed form expression by using principle of mathematical induction. Our claim is that T(n) = n (n+1) (2n + 1) / 6 .
Base Case
The claim is true for the base case T(1) , as T(1) = 1 = (1 x 2 x 3)/6.
Induction Hypothesis
Let us suppose our induction hypothesis is true for all values of n up to m .
That is, T(n) = n (n+1) (2n + 1)/6 for all values of n m .
Induction Step
From the given series, we have that T(m+1) = T(m) + (m+1)
That is, T(m+1) = m (m+1) (2m + 1)/6 + (m+1)
= (m+1) [ m(2m + 1)/6 + (m+1)]
= (m+1) [ 2m^2 + m + 6m + 6] / 6
= (m+1) [2m^2 + 7m + 6] /6
= (m+1) (m+2) (2m + 3)/6
= (m+1) (m+2) (2(m + 1) + 1)/6
Therefore, by principle of mathematical induction, we conclude that T(n) = n (n+1) (2n + 1)/ 6 for all values of n 1 .
Question 4. Series Sum Basics
Compute the sum of the following series:
i=1 to n i 2 i
Solution
Suppose S = i=1 to n i 2 i
Then S can be written as: 1 2 + 2 2 + 3 2 + + n 2 n
Such summations can often be simplified and solved using term sliding.
S = 1 2 + 2 2 + 3 2 + + n 2 n
That is, 2S = 1 2 + 2 2 + 3 2 + . + (n-1) 2 n + n n+1
Subtract the second equation from the first, and we obtain:
S = 1 2 + 1 2 + 1 2 + ... + 1 2 n n 2 n+1
= 2 + 2 + 2 + ... + 2 n n 2 n+1
= 2(1 + 2 + 2 + ... + 2 n-1 ) n n+1
By using geometric progression, we obtain:
S = 2 (2 n 1) n 2 n+1
Therefore, S = (n-1) 2 n+1 + 2
Question 5. Series Sum Basics II
What is the sum of the following series:
i=1 to n i i
Solution
While we can always use principle of mathematical induction (PMI) to solve these kinds of problems, that requires us to know or guess the solution. If we do not have a good guess, we may need to solve it directly. The good news is that although it is a bit more complicated, like the previous question, this question can also be solved using term sliding.
S = 1 2 + 2 2 + 3 + + n n
=> 2S = 1 + 2 + 3 + . + (n-1 ) 2 n + n n+1
Subtracting the second term from the first one, we obtain that:
S = 1 2 + (2 ) 2 + (3 ) 2 + + (n (n-1) ) 2 n n n+1
Since i (i-1) can be written as 2i-1 , we can now write the previous equation as:
S = i=1 to n (2i-1) 2 i n n+1
= 2 i=1 to n i 2 i i=1 to n i n n+1
From the previous question, we obtained that i=1 to n i 2 i = (n-1) 2 n+1 + 2
By using the result of the previous question and simplifying, we obtain that:
S = n n+1 + 2 n+1 2 (2n-2) 2 n+1
That is,
i=1 to n i22i = (n 2n + 3) 2 n+1
It is always prudent to validate the series for a few different of n . For example, we can confirm that for n=1, both sides evaluate to , and for n=3, both sides evaluate to .
Question 6. Series Sums Basics III
Which of the following two terms is larger:
1 to n i or 1 to n*n i
Solution
Both of these terms can be independently solved and compared.
We can observe that: 1 to n i = n (n+1) (2n+1)/6 , while 1 to n*n i = n (n +1)/2 .
Thus, the second term is significantly larger for larger values of n.
Question 7. Probability Basics Dice, Thrice
What is the probability of rolling three six-sided dice, and getting a different number on each die?
Solution
Many such problems can be solved using counting principles. This specific problem can be restated as follows: when rolling three six-sided dice, what is the total number of combinations, and what is the number of favorable combinations, that is, combinations in which there is a different number on each die.
The total number of combinations is 6 6 6 .
To count the total number of combinations in which there is a different number on each die, we can take the number of combinations for first die (), multiply it by number of combinations on second die (5, excluding the number obtained on the first die), and multiplying it by the number on third die (, excluding the numbers obtained on first and second dies). Therefore, the probability is (6 5 4) / (6 6 6) , that is, 5/9 .
