CS213

Important Notes

• In if statements; if(k>0) is preferred over if(k) because k>0 returns a bool while k doesn’t, thus depending on the definition of if
• 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 than endl when needing to output a large number of lines. However, use endl 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 is log(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]; where A is the original string. we can define a recursive relation as A[i] = 2*A[i-1] + A[j-1].

---

Lecture on 14th Sept

Lab Solution for previous Thursday

• The Problem is reduced to: \(F(A {\displaystyle \cup} \{n-1\}) = F(A) + F(A {\displaystyle \cup} \{n-1\})\)

• The second part of the RHS is what caused you trouble; but what you didn’t realize was that SHIFTING THE f-Array 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) to F(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 use cin and cout; do std::cin and std::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 idiot
• const1 operator*(const2 permutation perm) const3{}
  • const2:- perm is a constant; i.e.; in a*b, b is a constant.
  • const3:- in a*b, a is a constant. This won’t work for overloading = because in a=b, a must not be a constant.
  • const1:- The returned permutation is a constant.

---

Lecture on 17th Sept

• We mostly use Worst-Case analysis for checking the growth rate of an Algorithm. Average-Case 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 the for loop; but DON’T FORGET endl 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 (say j) quickly, and that will be the limit to which we’d need to search. For k, 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

Previous day’s Quiz