# Week-2 assignment
Do the following questions, this would help you build your logic and provide a base for harder questions.
1.  Print all of the above following patterns in C++, this would help you get comfortable with the syntax and implementation
2. If we are given a recurrence relationship of `T(n)= T(n/2)+1, T(1)=1`, find the time complexity of the relationship. Consider the worst case time complexity
3. Master’s theorem can be applied on which of the following recurrence relation?
(a) T (n) = 2T (n/2) + 2^n
(b) T (n) = 2T (n/3) + sin(n)
(c ) T (n) = T (n-2) + 2n^2 + 1
(d) None of these
(Also answer why, with an explanation)
4. 

5. Given an array of n numbers, your task is to calculate the maximum subarray. (We assume that an empty subarray is allowed, so the maximum subarray sum is always at least 0.)
> P.S: Provide me the O(n^3) solution first then try to optimise it to O(n^2) & then to O(n)
6. For the following questions, try to avoid reading the editorial directly if you are stuck, give the question atleast 30mins of your time & then headover to the editorial. Try to code on your own, as it would be helpful for you only - https://pastebin.com/EfrzfBAD
# Design Add and Search Words Data Structure
Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class:

`WordDictionary() Initializes the object.`
`Void addWord(word) Adds word to the data structure.`
`bool search(word)` Returns `true` if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.


# Group Task
Group-1: Task assigned to (Pratham, Veer): **Image Stagnography**
> Details about the task: Build a simple image stagnograph, which is used to hide audio files in images. You may use libraries like os, string, cv2 etc, for this implementation.The required files along with other references used with proper documentation should be pushed to GitHub.
> Estimated time of the task: 12-14hrs
> https://www.kaspersky.com/resource-center/definitions/what-is-steganography
> https://en.wikipedia.org/wiki/Steganography
> https://arpitbhayani.me/blogs/image-steganography/

Group-2: Task assigned to (Ishit, Aryan & Nitin): **Time Series Analysis using C++/Python**
> Replicate Geometric brownian motion using python/c++, build a simple monte carlo simulator using this concept. You may use stock data/any time series data for the plotting. The required files along with other references used with proper documentation should be pushed to GitHub.
Estimated time of the task: 18-20hrs
> Resources for reference:
> https://www.caciitg.com/resources/tsa/
> https://www.tableau.com/learn/articles/time-series-analysis
> https://www.investopedia.com/terms/t/timeseries.asp

Group-3: Task assigned to (Divyesh, Kavy): **Beauty of Chaos**
> Details about the task: Build a program using C++/Python, capable of generating random patterns/ colliding targets etc. The task is to replicate the beauty in randomness, and to observe the beauty in chaos. The required files along with other references used with proper documentation should be pushed to GitHub.
> Estimated time of the task: 12-14hrs

# Bonus Section
For those who are comforable with these questions - https://pastebin.com/fJZHU8jJ

> 1. Read about other approaches like [sliding window](https://www.geeksforgeeks.org/window-sliding-technique/), [range querie](https://www.geeksforgeeks.org/array-data-structure/array-range-queries/)s, [hashing](https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/), [two pointer](https://www.geeksforgeeks.org/two-pointers-technique/), [binary search on answers](https://cp-algorithms.com/num_methods/binary_search.html). This would come handy, in optimising your code.
> 2. Read about [overflows](https://www.geeksforgeeks.org/how-to-avoid-integer-overflows-and-underflows-in-cpp/), [binary exponentiation](https://cp-algorithms.com/algebra/binary-exp.html), [modular exponentiation](https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/) , [Modular Inverse](https://cp-algorithms.com/algebra/module-inverse.html) and how it's used for raising numbers to large powers.
> 3. Read this resource on [STL](https://noi.ph/training/weekly/week1.pdf), for [number theory](https://noi.ph/training/weekly/week4.pdf)

# Mode of submission
Submit your code/ pastebin.txt / codeforces submission link/ Project Files in a repository under your folder_name in this [repository](https://github.com/beingamanforever/ACM_Assignments_j23).