A estrutura de dados é uma forma de definir, armazenar e recuperar dados de uma forma estrutural e sistêmica. Uma estrutura de dados pode conter diferentes tipos de itens de dados.

A disponibilidade da estrutura de dados pode variar de acordo com as linguagens de programação. Estruturas de dados comumente disponíveis são lista, matrizes, pilha, filas, gráfico, árvore etc.

Algoritmo é um procedimento passo a passo, que define um conjunto de instruções a serem executadas em determinada ordem para obter a saída desejada.

Um problema pode ser resolvido de mais de uma maneira. Portanto, muitos algoritmos de solução podem ser derivados para um determinado problema. Analisamos os algoritmos disponíveis para encontrar e implementar o algoritmo mais adequado.

Um algoritmo é geralmente analisado em dois fatores - tempo e espaço. Ou seja, quantoexecution tempo e quanto extra space exigido pelo algoritmo.

A análise assintótica de um algoritmo refere-se à definição do limite / enquadramento matemático de seu desempenho em tempo de execução. Usando a análise assintótica, podemos muito bem concluir o melhor caso, o caso médio e o pior caso de um algoritmo.

A análise assintótica pode fornecer três níveis de ligação matemática do tempo de execução de um algoritmo -

• O melhor caso é representado pela notação Ω (n).
• O pior caso é representado pela notação Ο (n).
• O caso médio é representado pela notação Θ (n).

Uma estrutura de dados linear possui itens de dados organizados sequencialmente. A próxima vez pode ser localizada no próximo endereço de memória. Ele é armazenado e acessado de maneira sequencial. Matriz e lista são exemplos de estrutura de dados linear.

As seguintes operações são comumente realizadas em qualquer estrutura de dados -

• Insertion - adicionar um item de dados

• Deletion - removendo um item de dados

• Traversal - acessar e / ou imprimir todos os itens de dados

• Searching - encontrar um determinado item de dados

• Sorting - organizar itens de dados em uma sequência predefinida

Existem três abordagens comumente usadas para desenvolver algoritmos -

• Greedy Approach - encontrar solução escolhendo a próxima melhor opção

• Divide and Conquer - mergulhar o problema em um subproblema mínimo possível e resolvê-los de forma independente

• Dynamic Programming - mergulhar o problema em um subproblema mínimo possível e resolvê-los de forma combinada

Os problemas a seguir encontram sua solução usando a abordagem de algoritmo ganancioso -

• Problema do caixeiro viajante
• Algoritmo de árvore de expansão mínima de Prim
• Algoritmo de árvore de expansão mínima de Kruskal
• Algoritmo de árvore de expansão mínima de Dijkstra
• Gráfico - Colorir Mapa
• Gráfico - Capa do vértice
• Problema da mochila
• Problema de programação de trabalho

Os problemas fornecidos abaixo encontram sua solução usando a abordagem de algoritmo de divisão e conquista -

• Mesclar Classificar
• Ordenação rápida
• Pesquisa Binária
• Multiplicação da matriz de Strassen
• Par mais próximo (pontos)

Os problemas fornecidos abaixo encontram sua solução usando a abordagem de algoritmo de divisão e conquista -

• Série de números de Fibonacci
• Problema de mochila
• Torre de Hanói
• Caminho mais curto para todos os pares por Floyd-Warshall
• Caminho mais curto por Dijkstra
• Agendamento de projeto

Uma lista vinculada é uma lista de itens de dados conectados com links, ou seja, ponteiros ou referências. A maioria das linguagens de programação de alto nível modernas não fornece o recurso de acessar diretamente a localização da memória, portanto, as listas vinculadas não são suportadas nelas ou estão disponíveis na forma de funções embutidas.

Na estrutura de dados, pilha é um tipo de dados abstrato (ADT) usado para armazenar e recuperar valores no método Last In First Out.

As pilhas seguem o método LIFO e a adição e recuperação de um item de dados leva apenas Ο (n) tempo. As pilhas são usadas onde precisamos acessar os dados na ordem inversa ou sua chegada. As pilhas são comumente usadas em chamadas de função recursivas, análise de expressão, primeiro travessia de profundidade de gráficos etc.

As operações abaixo podem ser realizadas em uma pilha -

• push() - adiciona um item à pilha

• pop() - remove o item da pilha superior

• peek() - dá valor ao item superior sem removê-lo

• isempty() - verifica se a pilha está vazia

• isfull() - verifica se a pilha está cheia

Fila é uma estrutura de dados abstrata, algo semelhante à pilha. Em contraste com a pilha, a fila é aberta em ambas as extremidades. Uma extremidade é sempre usada para inserir dados (enfileirar) e a outra é usada para remover dados (desenfileirar). A fila segue a metodologia First-In-First-Out, ou seja, o item de dados armazenado primeiro será acessado primeiro.

Como as filas seguem o método FIFO, elas são usadas quando precisamos trabalhar nos itens de dados na seqüência exata de sua chegada. Cada sistema operacional mantém filas de vários processos. As filas prioritárias e a amplitude da primeira travessia dos gráficos são alguns exemplos de filas.

As operações abaixo podem ser realizadas em uma pilha -

• enqueue() - adiciona um item ao final da fila

• dequeue() - remove o item da frente da fila

• peek() - dá valor ao item frontal sem removê-lo

• isempty() - verifica se a pilha está vazia

• isfull() - verifica se a pilha está cheia

A pesquisa linear tenta encontrar um item em um tipo de dados organizado sequencialmente. Esses itens de dados organizados em sequência, conhecidos como array ou lista, são acessíveis no incremento da localização da memória. A pesquisa linear compara o item de dados esperado com cada um dos itens de dados na lista ou matriz. A complexidade média do tempo do caso da pesquisa linear é Ο (n) e a complexidade do pior caso é Ο (n ² ). Os dados em matrizes / listas de destino não precisam ser classificados.

Uma pesquisa binária funciona apenas em listas ou arrays classificados. Esta pesquisa seleciona o meio que divide a lista inteira em duas partes. Primeiro, o meio é comparado.

Esta pesquisa compara primeiro o valor alvo com o meio da lista. Se não for encontrado, ele decide se.

A classificação por bolha é um algoritmo baseado em comparação em que cada par de elementos adjacentes é comparado e os elementos são trocados se não estiverem em ordem. Como a complexidade de tempo é Ο (n ² ), não é adequado para grandes conjuntos de dados.

A classificação por inserção divide a lista em duas sub-listas, classificadas e não classificadas. Ele pega um elemento por vez e encontra-o no local apropriado na sub-lista classificada e insere lá. A saída após a inserção é uma sub-lista classificada. Ele funciona iterativamente em todos os elementos da sub-lista não classificada e os insere na sub-lista classificada em ordem.

A classificação por seleção é uma técnica de classificação local. Ele divide o conjunto de dados em duas sub-listas: classificado e não classificado. Em seguida, ele seleciona o elemento mínimo da sub-lista não classificada e o coloca na lista classificada. Isso itera, a menos que todos os elementos da sub-lista não classificada sejam consumidos na sub-lista classificada.

Ambas as técnicas de classificação mantêm duas sublistas, classificadas e não classificadas, e ambas pegam um elemento por vez e o colocam em uma sublista classificada. A classificação por inserção funciona no elemento atual em mãos e o coloca na matriz classificada no local apropriado, mantendo as propriedades da classificação por inserção. Ao passo que a ordenação por seleção procura o mínimo da sub-lista não classificada e o substitui pelo elemento atual em mãos.

A classificação de mesclagem é um algoritmo de classificação baseado na abordagem de programação dividir e conquistar. Ele continua dividindo a lista em uma sub-lista menor até que toda a sub-lista tenha apenas 1 elemento. Em seguida, ele os mescla de maneira classificada até que todas as sublistas sejam consumidas. Ele tem uma complexidade de tempo de execução de Ο (n log n) e precisa de Ο (n) espaço auxiliar.

A classificação shell pode ser considerada uma variante da classificação por inserção. A classificação por shell divide a lista em uma sublista menor com base em algunsgapvariável e, em seguida, cada sub-lista é classificada usando classificação por inserção. Na melhor das hipóteses, ele pode executar até Ο (n log n).

A classificação rápida usa a abordagem de dividir e conquistar. Ele divide a lista em 'partições' menores usando 'pivô'. Os valores menores que o pivô são organizados na partição esquerda e os valores maiores na partição direita. Cada partição é classificada recursivamente usando classificação rápida.

Um gráfico é uma representação pictórica de um conjunto de objetos onde alguns pares de objetos são conectados por links. Os objetos interconectados são representados por pontos denominados vértices e os elos que conectam os vértices são chamados de arestas.

O algoritmo Depth First Search (DFS) percorre um gráfico em um movimento em profundidade e usa uma pilha para lembrar de obter o próximo vértice para iniciar uma pesquisa quando ocorre um beco sem saída em qualquer iteração.

O algoritmo de primeira pesquisa de amplitude (BFS) percorre um gráfico em um movimento de amplitude e usa uma fila para lembrar de obter o próximo vértice para iniciar uma pesquisa quando um beco sem saída ocorre em qualquer iteração.

Uma árvore é um gráfico minimamente conectado sem loops e circuitos.

Uma árvore binária tem uma condição especial de que cada nó pode ter no máximo dois filhos.

Uma árvore de pesquisa binária é uma árvore binária com uma provisão especial onde o filho esquerdo de um nó deve ter valor menor que o valor de seu pai e o filho direito do nó deve ter um valor maior que seu valor pai.

A travessia da árvore é um processo para visitar todos os nós de uma árvore. Porque, todos os nós são conectados por meio de arestas (links), sempre começamos a partir do nó raiz (cabeça). Existem três maneiras que usamos para atravessar uma árvore -

• Transversal em ordem
• Pré-encomendar Traversal
• Traversal pós-pedido

• Travessia em ordem - 10 14 19 27 31 35 42
• Transferência de pré-encomenda - 27 14 10 19 35 31 42
• Percurso pós-pedido - 10 19 14 31 42 35 27

As árvores AVL são árvores de pesquisa binárias de equilíbrio de altura. A árvore AVL verifica a altura das subárvores esquerda e direita e garante que a diferença não seja maior que 1. Essa diferença é chamada de Fator de equilíbrio.

BalanceFactor = height(left-sutree) − height(right-sutree)

Uma árvore geradora é um subconjunto do Gráfico G, que possui todos os vértices cobertos com o número mínimo possível de arestas. Uma Spanning Tree não tem ciclos e não pode ser desconectada.

Depende de quão conectado o gráfico está. Um grafo não direcionado completo pode ter no máximo n ^n-1 número de árvores geradoras, onde n é o número de nós.

Este algoritmo trata o gráfico como uma floresta e cada nó como uma árvore individual. Uma árvore se conecta a outra apenas e somente se ela tiver o menor custo entre todas as opções disponíveis e não violar as propriedades do MST.

O algoritmo de Prim trata os nós como uma única árvore e continua adicionando novos nós à árvore abrangente a partir do gráfico fornecido.

Em um gráfico ponderado, uma árvore de abrangência mínima é uma árvore de abrangência que tem peso mínimo que todas as outras árvores de abrangência do mesmo gráfico.

Heap é uma estrutura de dados de árvore binária balanceada especial em que a chave do nó raiz é comparada com seus filhos e organizada de acordo. Um min-heap, um nó pai tem um valor de chave menor que seus filhos e um nó pai de max-heap tem um valor maior que seus filhos.

Uma função recursiva é aquela que chama a si mesma, diretamente ou chama uma função que por sua vez a chama. Cada função recursiva segue as propriedades recursivas -base criteria onde as funções param de chamar a si mesmas e progressive approach onde as funções tentam atender aos critérios básicos em cada iteração.

Torre de Hanói, é um quebra-cabeça matemático que consiste em três torres (pinos) e mais de um anel. Todos os anéis são de tamanhos diferentes e empilhados uns sobre os outros, onde o disco grande está sempre abaixo do disco pequeno. O objetivo é mover a torre do disco de um pino para outro, sem quebrar suas propriedades.

A série Fibonacci gera o número subsequente adicionando dois números anteriores. Por exemplo - 0 1 1 2 3 5 8 13.

Hashing é uma técnica para converter um intervalo de valores-chave em um intervalo de índices de uma matriz. Usando tabelas de hash, podemos criar um armazenamento de dados associativo onde o índice de dados pode ser encontrado fornecendo seus valores-chave.

A pesquisa de interpolação é uma variante aprimorada da pesquisa binária. Este algoritmo de pesquisa funciona na posição de sondagem do valor necessário.

Notação de prefixo - * + ab + cd

Notação Postfix - ab + cd + *