DEV Community: Hiesenberg

Recap the use of some Algorithms

Hiesenberg — Tue, 04 Jan 2022 18:07:22 +0000

Binary Search Algorithm


- Efficient algorithm for finding an item from a **sorted list**
 of items

- The time complexity of the binary search algorithm is O(log n)

Breadth First Search (BFS) Algorithm

- Breadth–first search (BFS) is an algorithm for traversing or searching tree or graph data structures.
- It uses a queue.
- The time complexity of BFS traversal is O(V + E), where V and E are the total number of vertices and edges in the graph.

Depth First Search (DFS) Algorithm

- Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
- It uses a stack.
- The time complexity of DFS traversal is O(V + E), where V and E are the total number of vertices and edges in the graph.

Merge Sort Algorithm

- Merge sort is an efficient sorting algorithm that produces a stable sort, which means that if two elements have the same value, they hold the same relative position in the sorted sequence as they did in the input
- Merge sort is a Divide and Conquer algorithm
- The worst case time complexity of merge sort is O(n log(n))

Quicksort Algorithm


- Quicksort is an efficient in-place sorting algorithm, which usually performs about two to three times faster than merge sort and heapsort when implemented well.
- Time complexity of Quicksort is O(n log(n)).

Kruskal’s Algorithm


- Kruskal’s Minimum Spanning Tree algorithm, a greedy algorithm to find a minimum spanning tree for a connected weighted graph.
- Kruskal's algorithm's time complexity is O(E log V), V being the number of vertices

Single-Source Shortest Path VS

All-Pairs Shortest Path


- The Single-Source Shortest Path (SSSP) problem consists of finding the shortest paths between a given vertex v and all other vertices in the graph.
- The All-Pairs Shortest Path(APSP) problem is the determination of the shortest graph distances between every pair of vertices in a given graph

Floyd Warshall Algorithm


- The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.
- The Floyd-Warshall all-pairs shortest path runs in O(n^3) time.

Dijkstra’s Algorithm


- Dijkstra's algorithm is the iterative algorithmic process to provide us with the shortest path from one specific starting node to all other nodes of a graph

- Time Complexity of Dijkstra's Algorithm is O(V^2)

Kadane’s Algorithm


- Simply putting for writing a logic to find the sum of contiguous subarray  within a one-dimensional array of numbers that has the largest sum, we use Kadane’s Algorithm.

Lee Algorithm


- The Lee algorithm is one possible solution for maze routing problems based on breadth-first search.

- It always gives an optimal solution, if one exists, but is slow and requires considerable memory

Floyd’s Cycle Detection Algorithm

As the name it self states, Floyd's Cycle detection algorithm or Hair Tortoise algorithm is used to detect if there is a cycle in a linked list

Union Find Algorithm

- Recap Dis Joint Data Structure.
- A union-find algorithm is an algorithm that performs two useful operations find and union.
- Find: Determine which subset a particular element is in.
- Union: Join two subsets into a single subset.

KMP Algorithm

- The Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S.

- It is a Pattern Matching Algorithm

Sorting Algorithms


- A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements.

- Examples
      1. Insertion Sort Algorithm
      2. Selection Sort Algorithm
      3. Counting Sort Algorithm
      4. Heap Sort Algorithm

Euclid’s Algorithm


-  Efficient algorithm for computing the greatest common divisor (GCD)

My preparation to TCS Codevita

Hiesenberg — Thu, 20 Aug 2020 14:42:16 +0000

What is TCS Codevita ?

TCS CodeVita, is a contest for engineering and science students to experience the joy of coding and to sharpen their programming skills through real-life computing practices. The contest also aims at identifying the talent, besides providing the student community, an opportunity to earn peer recognition.

TCS conducts a coding exam for coders to let out an showcase their programming skills across the globe.Codevita majorly fcuses on the problem-solving skills of the participant.

How do i even get to know that there is an exam like Codevita ?

Tcs Campus commune is hectic active in promoting CODEVITA.I have received a mail from Campus Commune about Codevita and i got interested about the format of the exam and just googled about it.

And Then..

and then i just tried one of the past problems of codevita.
I am able to solve the one question which is named as "NumberGame"
and it's a little tricky but, when i learnt about the concept i thought it is easy.I get to know that is the first question in Codevita contest. And , the truth is

First questions in Codevita are said to be pretty easy and they don't involve any dynamic-programming stuff

How did I get my material for Codevita ?

Firstly , there is nothing called MATERIAL for codevita as far i know.But there are many platforms in which you can practice the previous problems of codevita and have a glance about the pattern of Codevita. Learning how to write basic syntaxes in programming languages we are comfortable with is always the basic prerequisite for the preparation of codevita.

Geeks for Geeks have all the previous problems of Codevita

I have started to solve the problems in Geeks for Geeks and i am stuck at a problem and searched for a related video of explanation and i get to know about EDYST.
I have enrolled in edyst's Codevita programme.I have practised all the questions which are in the edyst platform.
It gave me a basic idea of how to approach to questions which involves dynamic programming.
I had no idea about how time complexity and space complexity works.After solving some questions i get to understand how BigO notations works and how space while execting the code is used efficiently.

Mocktests..

Mocktests are conducted by codevita.

Mocktests conducted by codevita are very important and we also have an advantage of getting familiar with their platform and how it works.

Basic stuff in Problem solving

Hiesenberg — Thu, 20 Aug 2020 03:41:42 +0000

Some popular Competitive challenge contests I know..

Tcs           - Codevita
Infosys       - HackWithInfy
GOLDMAN SACHS - GOLDMAN SACHS 
Google        - Google'sCode Jam
Google        - APAC
Facebook      - Hacker Cup
Microsoft     - Imagine Cup 
ACM           - ICPC
Codechef      - SnackDown

and more..

Some useful topics...

 °Greedy Algorithm
 °Stack
 °Queue
 °Mapping Concepts
 °Array manipulation
 °String manipulation
 °Tree
 °Dynamic Programming
 °BackTracking
 °Graph

In most cases divide and conquer works well.
Every exam has its own pattern.

For instance,in Tcs codevita,
6 Coding questions will be asked and the difficulty increases as we move from question 1 to question 6 . 1st question does not involve any dynamic programming or difficult algorithm , but , will be on simple mathematics, and simple problem solving skills. It's well-known that

 TCS hires its digital 
 candidates from Codevita.

FYI, Many got an interview opportunity for solving 2-3 questions

Which programming language is best for problem solving ?

Every programming language has its own unique capabilities, features, services etc
In any programming language we can solve the problems .

  Proceed using the 
  programming language in 
  which you are most 
  comfortable with.

Usually...

 For beginners , python is 
 recommended in most cases.

Because,easy to Learn, Read, and Use .Unlike C++ or C# or java and other languages, Python's syntax is human readable and it's concise. As a beginner, this will allow you pick up the basics quickly, with less mental strain, and you can level up to advanced topics quicker. With one glance at Python code, you can infer what the code is doing.