Implementation of standard data structures

This repository contains all of the lab work done in CCE 3rd Sem Data Structure Lab. The DS lab was a pretty intense lab but it was worth it. We had alternative week evaluations. I learnt to implement the standard data structures without using any sort of libraries. It helped to internalise the concepts. (You are allowed to use libraries outside the lab so don't worry)

Feel free to make changes and maybe suggest better codes.

What you can find here

You can find the following codes here

• Basic Searching and Sorting Methods
• Stack implementation using array, linkedlists and applications of stack like prefix,infix,postfix evaluation
• Single, Double, and circular LinkedLists programs
• Binary Trees
• Binary Search Tree and expression tree implementation.
• Some thoughts and reflections I would like to share to help you guys become better coders xD.

If you are a junior reading this, keep following points in mind

You people are going to enter/entered the world of Computer Science, Development and programming in general. It's really vast and there is a lot of cool and fun stuff to explore. Algorithms and Data structures is one such area. In general, you might be starting with this or some other field/track. You will realise that you are a newbie in lots of areas (and that is fine) and you will have to work your way up by practice and showing up daily (even if you are really passionate about it or not). There is no other shortcut and that is also good. The journey is the important thing.

• This repository is for your (and my reference). So, use it when really required. But, do try your best and follow your teacher. Ideally, you should try to think and try enough till you are getting ideas (or if you have time). That way, even if you are not able to get it right, when you see the solution, you will understand it quicker and it will stick for longer.

• Try implementing all the programs and additional exercises yourself. Try to play around a bit and learn to deal with segmentation faults. Use cin and input some variable in between to debug hint:infinite loop or segmentation fault (Thanks to Veena Ma'am xD)

• Try not to copy. You can see somebody else's implementation for reference though, then try to write on your own. You will find yourself going back and forth but that is okay. (Active learning - study something new and then try to reproduce it - the key ideas, concepts)

• You can check out standard code implementations available across Github. The algorithms repository maintained by the open source community.

Why even learn DS, huh?

• You will find DS and Algorithms everywhere in CS (and in the world). These concepts will help a lot in interview prep/machine coding rounds and in general also, they will make you a better programmer.

• Data structures and Algorithms(not in this course still) are very important. You can get better only by implementing, studying, understanding, practicing.

  Further, this is mostly the implementation part. There are tonnes of DS related and algorithmic problems which you may come across later depending on whether you do interview/coding prep or you go one level beyond and do CP(do like seriously, CP is much more vast and logical)

• Learn about the time complexities involved.

• Try doing some related problems on GFG practice, LeetCode or InterviewBit (if time available). (These are the most used websites for coding round/interview prep. You will be using them when the time comes or when you decide) It's not necessary but I feel I could have practiced some problems. Also, for understanding concepts in these sites or YouTube is there. Youtube Channels like mycodeschool, Algorithms with Attitude, Back to Back SWE, Abdul Bari etc. Check out MOOCs on Coursera also if interested.

  • Learn to google the crap out of internet for learning. Youtube and Google have almost everything as of 2020 October.

  • MOOCs are good but take them when really needed or you have a lot of interest or time.

  • Data structures University of Illinois - I have not tried this but heard from topper kind of your batch guy that these courses are good. This is more relevant to your DS course. Although, you can just follow college Data structures course. That is enough.

  • UC San Diego Specialization - (Not that much relevant to your DS course)I have done first course. It was challenging. I am somewhere in between in the second and third course. Currently, I don't need the content much so will complete later. But this specialization is tough and probably one of the best in terms of depth and breadth of topics.

Disclaimer

• Below this point, I am talking about CP more. It's more like advice I would give to myself. I am a low rated (< 1300 on Codeforces, ~1690 on Codechef) coder so maybe, if you are a ratist(xD), you can stop reading now( If you think that opinion of a low rated coder is not useful which is a fair argument)

• If you know about CP and not really interested, it's ok. No need to do under peer pressure. There are a lots of areas and lots of ways to get into companies that pay really good salaries or whatever is your aim. for ex: you can be really good at developing stuff (apps, web development) or say something like deep learning (helps in masters but I would not recommend if you wanna do placement, kind of hard to get internships)

Many ways to get into good companies or universities are there.

Remember that if you say yes to one thing, you are saying no to something else.

Becoming good at CP requires a lot of discipline and focus*(kind of universal law) but (yes, probably more than development stuff atleast at the college level). I am working on the above two. I would argue that it will take a hell lot of time as compared to learning basic-intermediate web development/app dev etc. especially you are not that good at thinking skills/maths. (trust me, give a CF round and you will realise.)

So, if you do for sometime and feel like you like it or getting addicted or if you have other strong reasons continue otherwise you can go to explore other stuff.(Or just keep solving problems not so seriously.)

Learn webd or appd and do internships. Do hackathons(I am a hypocrite), kaggle competitions and stuff like that. Masters people know what to do.

UPDATE : WebDev/AppDev/ML/DL whatever you do, do internships preferably atleast 1 industrial. Basically, work experience matters a lot. Internship = working on something which will probably used by several users

Case study: I have a couple of friends who got MSFT internship offers who did stuff like hackathons, SysAdmin work and didn't do CP but they were good at DSA.

Some thoughts - CP related

• DS will also act as foundation if you want to do competitive programming. CP and interview prep are different. Try reading about that difference or rather experiencing that. Participate in a couple of Codeforces contests and LeetCode contest (or just solve some LeetCode/GFG problems) and you will get to know the difference.

  The type of questions in coding rounds are similar to what you do in labs. They are going to be more fun and logical (and difficult). CP is more mathematical and algorithm/implementation based. The topics also vary. You can get a better idea by ofcourse doing a bit both of them or by reading.

Tackling some misconceptions and tips

DSA/InterviewPrep is a subset of CP. CP is a universe.

Really good means like 1600+ on CF. 1800+ on Codechef.(maybe)

You don't need to do (or be really good at) Competitive programming to clear coding rounds/interviews but those who are good at CP or even have some experience find it easier to prepare for coding interviews and before getting a coding interview, one has to clear Online Test Round or Coding Rounds(These rounds have less standard and more like easy CP problems. They can be standard problems also. Depends on the company .

But for coding interviews, you practice those questions that are more relevant there.... Google, Microsoft only care about you clearing their interview. Before coding interviews, if you are from a good college like MIT(comparing something good with the best does not make good bad - Sankalp xD), you will have to give some kind of online assessment/coding round.

Just start solving problems!! Learn required DS and algo on the go. Mostly, it's about raw thinking in the initial stage. You will find a lot of problems where you don't need to know any algorithm or specific data structure. Occasionally exploring resources is fine but don't go in the search of the perfect all in one resource. (I used to do this quite a few times). I believe it is a subtle form of procrastination.

SideNote Updated Oct 2020: Even if you don't have serious goals in Competitive programming, I would still suggest practicing DSA* problems(yeah, finally on Youtube, some people like Pepcoding channel, takeUForward have given really good instructions) and giving short contests and then upsolving if you are interested in placements or getting a PPO(You will need to do this stuff in 1st and 2nd year and be ready before 5th sem). I had messed up this part in the last one month before the Internship rounds (and I don't have any offers till(I gave for the 4-5 high paying companies only) ).

This is for the reason that even if you solve all those DSA problems(like you have built the foundation), still most of us need practice under pressure. Contests help in pressure handling, improving speed and accuracy(getting AC in minimum possible attempts).

While solving problems, make sure that you spend enough time and try to think genuinely. Work with pen and paper. Try to get AC in 1 go.(It's hard)

Some short contests platforms : LeetCode, BinarySearch.com More CP oriented: Codeforces, AtCoder(Atcoder beginner contest), Codechef(Lunchtime, Cookoff). Even if you are not that much interested in CP, for practice sake try to solve like 3 probs(Hell, I can't still solve 3 questions in codeforces contest consistently)

*DSA problems - the standard problems based on data structures and algorithms. The ones which are asked in coding rounds(some companies) and mostly asked in coding interviews. E.g Find the median of the array.

Approach to CP in a nutshell

This is the collective wisdom and information that I have understood by reading on platforms and the internet in my journey till now. (I am sort of advanced beginner in CP and certainly not good at it currently). But, you can trust the information given because i am just trying to articulate the ideas that the better programmers have conveyed (and I myself have experienced in whatever amount I have practiced. ) As you begin solving problems, these things keep getting clearer and you can adjust. That's the case with almost every field probably. (skills in one field do help in others though)

For CP, practice questions on Codeforces and Codechef. HackerRank problem solving section is good for starting. (I don't want to make this a CP blog so I won't write much here about resources. You will find on them on your own. Youtube has a lot of resources. For ex. Aman Dhattarwal is making a CP course which might be released completely by 2021)

• Take Part in contests.

• Focus more on practicing problems on Codeforces and upsolving. If your rating is x, then solve problems [ x, x + 200 ] (could increase even more). Only deliberate practice can make you better.

• Do not learn all the algo and ds stuff first. Things don't work like that. You learn on the go by practicing and studying what is required. This is called the project based learning approach sometimes in Dev world or Minimum viable knowledge. Learning in Breadth first search way more and dfs sometimes is helpful in programming and CS. Optimal way in the beginning would be to study concepts but spend more time practicing.

• There are a lot of resources about guidance on Quora and Codeforces (Google baba is there).You can check them out. Competitive programming is different from normal data structures and algorithms that you implement in lab. You need to know these concepts but you get good at CP by doing CP.

  Check out the concept of deliberate practice. In general and CP related Here You can get good at CP only by deliberate practice. Peter Norvig's (Google AI head) Teach yourself programming in 10 years

  You need to be consistent and know the fact that it is going to be ridiculously hard (if you want to be good like Expert, Master on CF, 5 star on Codechef etc.). At the time of writing this, I am myself not good at CP. But it's fun and one of the best ways to build problem solving, thinking, programming and debugging skills. (There are many other benefits). You also become a fast learner in the process.

  • Errichto's Guide Errichto is a red coder on Codeforces and he has a youtube channel with quality content.
  • Errichto's How to Become Red Coder
  • What CP is all about An answer which beautifully describes what CP is all about.
  • How to get start with CP - by Sameer Gulati Check his other videos as well.
  • Ashish Gupta's great answer Check his other answers as well.
  • Rough Roadmap to get idea about CP
  • How do I strengthen my problem solving skills? For more articles, refer bottom most section of My Competitive Programming Repo's resources section - I store some stuff here. It will be more active in future. Apart from that, refer Awesome CP

• I would like to write a blog on CP (to save time for others) when I get good obviously xD. Currently, I am busy with other programming related work.

Note

There is some non-DS lab material in the repository.