CS213
Important Notes
 In
if
statements;if(k>0)
is preferred overif(k)
becausek>0
returns abool
whilek
doesn’t, thus depending on the definition ofif
 Passing Big Vectors or Arrays as parameters of a function would cause a lot of time loss, because copying the huge data takes place; Especially during Recursion. Using Global Arrays is better!
 In creating header files, don’t do
using namespace std
; because the person using the header may or may not want to use that namespace \n
is faster thanendl
when needing to output a large number of lines. However, useendl
at the end of the output to flush the output and refresh the buffer.
C++ Libraries
Vectors  Some Functions to be known
Running Lecture Notes
Lecture on 10th Sept

Addition is not a Basic Operation! Addition requires changing all the bits in worst case scenario; making it
O(logn)
on average. This can be made even faster by using parallel computing by predicting the carry of the bit, while simultaneously adding.(How did we compute runtime as
O(logn)
here – Number of bits islog(n)
where n is the input)
Given string S
find all s1
and s2
such that interweaving both gives S
Break this down to first finding the number of distinct subsequences for s1
and s2
.

If there is no repetition; we can write
num_dist_subseq = 2^n
. 
For a case with rep, define
N[i] = number of distinct sub seq from A[0] to A[i]
; whereA
is the original string. we can define a recursive relation asA[i] = 2*A[i1] + A[j1]
.
Lecture on 14th Sept
Lab Solution for previous Thursday

The Problem is reduced to: \(F(A {\displaystyle \cup} \{n1\}) = F(A) + F(A {\displaystyle \cup} \{n1\})\)

The second part of the RHS is what caused you trouble; but what you didn’t realize was that SHIFTING THE fArray by (2^n) unites to the left! Therefore, you solve this problem in a Divide and Conquer method.

What you were trying to do was overly complicated; you were trying to go from
F(0)
toF(A)
by using Dynamic Programming and stuff. 
Part 2; suppose all the values given were
F
. Reverse the steps done above, meaning you would do: \(f(A_i) = F(A_i)  F(A  A_i)\) And Dynamic programming can be implemented here to make the code even more faster.
Lecture on 15th Sept
213 Assignment Discussion
 Avoid
using namespace std;
because the user who includes your header file may not want that namespace. To usecin
andcout
; dostd::cin
andstd::cout
. to_array()
must NOT return a pointer to the internal Array. You must make a deep copy of the Array, and return a pointer to that array. This is what you did u idiotconst1 operator*(const2 permutation perm) const3{}
const2
:perm
is a constant; i.e.; ina*b
,b
is a constant.const3
: ina*b
,a
is a constant. This won’t work for overloading=
because ina=b
,a
must not be a constant.const1
: The returned permutation is a constant.
Lecture on 17th Sept
 We mostly use WorstCase analysis for checking the growth rate of an Algorithm. AverageCase makes sense in some cases, like the QuickSort Algo. These algorithms usually have a Randomization incorporated, such as the
Pivot
in the QuickSort.  For a Randomized Algo, the Running time is a Random Variable. We therefore, represent the runtime of the algorithm for a given input size
n
, as the Expected Value of the Random Variable. This is usually misleading, because the real runtime might vary and be more than the expected value, but usually it performs near the Expected Runtime.  Hindsight, you didn’t check the algo in today’s lab and submitted the
O(n^2)
algorithm
Lecture on 21st Sept
Previous Lab Solution
endl
flushed the output a single value at a time. Therefore, use\n
when needed to print output on different lines, in thefor
loop; but DON’T FORGETendl
at the end to flush the output completely! Read abt it here. For the second part, we’re gonna be building
f_i
from prev known. We can find the greatest to the left (sayj
) quickly, and that will be the limit to which we’d need to search. Fork
,j<k<=i
to be a starting point; it must be the smallest among that proper subset.  What we do here is, we build a vector. (Write this logic down in OneNote, its really good.)
Lecture on 22nd Sept
Interweaving of Strings
 try something… Didn’t pay attention here