Eu tenho procurado por um bom curso on-line em estruturas de dados, mas descobri que o Google também retorna resultados para cursos de algoritmos, que dizem coisas como:

Neste curso, você aprenderá vários princípios fundamentais do design de algoritmos: métodos de dividir e conquistar, algoritmos de gráficos, estruturas práticas de dados (pilhas, tabelas de hash, árvores de pesquisa) , algoritmos aleatórios e muito mais. [fonte]

e

No final desta aula, você entenderá os principais conceitos necessários para criar novos algoritmos para gráficos e outras estruturas de dados importantes e avaliar a eficiência desses algoritmos. [fonte]

e

Este curso fornece uma introdução à modelagem matemática de problemas computacionais. Ele abrange os algoritmos comuns, paradigmas algorítmicos e estruturas de dados usados ​​para resolver esses problemas . [fonte]

Minha pergunta é: algoritmos e estruturas de dados estão intimamente ligados, o que significa que eles devem ser entendidos juntos ou um tópico é mais fundamental que o outro?

EDIT: Para aqueles que votaram para encerrar esta pergunta, você pode me dizer por que e talvez como melhorar essa? Aprender a fazer as perguntas certas faz parte do processo educacional.

Todos os tipos de misturas existem. Você possui estruturas de dados que não estão associadas a algoritmos, algoritmos que não exigem estruturas de dados (reais), mas na maioria das vezes os dois vêm em um pacote.

Editar: como o @Doval apontou corretamente, as estruturas de dados em si não possuem nenhuma operação associada a elas. O ato de combinar estrutura e algoritmo de dados forma um tipo de dados abstrato.

Estruturas de dados sem algoritmos

Considere, por exemplo, uma estrutura de dados para armazenar coordenadas bidimensionais, apropriadamente chamadas Point. Não há nada muito em termos de algoritmos para ser feito por um ponto e é realmente apenas um recipiente para um xe yvalor. Obviamente, fornecendo essa estrutura de dados, agora você pode adicionar todos os tipos de algoritmos (cálculo de distância, cascos convexos, o que você tem).

Você pode pensar em muitas estruturas de dados, que são simplesmente um acúmulo de dados individuais. Embora estes ocorram com frequência na prática, eles não são um bom material de ensino, porque não há nada a ser aprendido com ele, depois de entender que itens de dados únicos podem ser acumulados em uma nova estrutura de dados (como o que você aprende após o Pointexemplo acima , se eu fornecer uma estrutura de dados impressionante chamada Point3D, o que pode fazer a mesma coisa no espaço tridimensional?)

Algoritmos sem estruturas de dados (reais)

"Real", porque obviamente todo algoritmo interessante precisa de tipos de dados primitivos, como números inteiros ou booleanos, e não queremos considerá-los estruturas de dados neste contexto. Da mesma forma que acima, esses algoritmos são tipicamente simples. Em particular, eles não vêm com um estado complicado de qualquer tipo, porque isso geralmente entra em uma estrutura de dados (consulte a próxima seção).

Um exemplo para esse algoritmo seria calcular o maior divisor comum de dois números. Os algoritmos do Euklid para o gcd precisam apenas conter dois números inteiros e manipulá-los.

Quando as coisas começam a ficar mais interessantes, você logo entra no mundo dos tipos de dados abstratos. Por exemplo, a peneira de Eratóstenes é baseada em uma matriz. Poderíamos ter uma discussão agora, se uma matriz ainda é primitiva ou, de fato, você pode discutir se um número inteiro ainda não é uma estrutura de dados. De qualquer maneira, os algoritmos que existem completamente sem estruturas de dados são bastante chatos, mesmo se você aceitar a existência isolada deles.

Algoritmos combinados com estruturas de dados, também conhecidos como tipos de dados abstratos

Agora, esses são os mais interessantes, mas por duas razões muito diferentes. Normalmente, você pode abordá-las de duas direções: estrutura de dados primeiro ou algoritmo primeiro.

Enquanto um tipo de dado abstrato é definido pela combinação de estrutura de dados + algoritmos / operações, geralmente os vemos com foco em um deles e consideramos o outro como facilitadores.

Estrutura de dados e algoritmo

Você encontrará tipos de dados abstratos, que são bastante simples de usar, mas envolvem algoritmos mais ou menos complicados para fazê-los funcionar internamente. Por exemplo, a HashMapé trivial de usar, mas envolve uma função de hash bacana e lida com as colisões de hash no interior. No entanto, do seu ponto de vista como usuário, você se preocupa com isso como algo que contém dados para você, não como algo que faz algo por você.

Ao contrário do último grupo abaixo, essas estruturas de dados não expõem seus usuários a esses algoritmos. Você não precisa saber nem se importar com a HashMapfunção de hash interno de uma pessoa para poder usá-la. (Para usá-lo efetivamente, você pode querer saber essas coisas;)

Algoritmo, depois estrutura de dados

A outra direção significa que você tem um algoritmo, que deseja poder simplesmente usar, mas que precisa de estruturas de dados internamente para fazê-lo funcionar como pretendido. Um exemplo seria um algoritmo de particionamento de espaço binário (BSP), no qual você pode simplesmente solicitar a bidimensional a Pointpartir de um grande conjunto de pontos mais próximo de um determinado ponto de consulta. No entanto, você precisa de uma estrutura em árvore (e até de algoritmos adicionais, como cálculos de distância) por dentro para realmente escrever o algoritmo.

Em geral, pode-se dizer que os algoritmos deste grupo usam estruturas de dados envolvidas para sua representação interna do estado. Eu diria que esse grupo de algoritmos é o mais diversificado e você encontrará muitos diferentes que se encaixam nesse esquema geral. Em relação ao ponto de vista, nós os vemos como interessantes, porque eles fazem algo (por exemplo, classificação) por nós e não se importam tanto com a parte de retenção de dados.

Estruturas e algoritmos de dados intimamente relacionados

Por fim, você possui estruturas de dados muito próximas dos algoritmos que correspondem diretamente a eles. Um exemplo típico é uma árvore binária que, quando você deseja fazer algo significativo, força o tópico dos algoritmos de caminhada em árvore (profundidade primeiro, largura primeiro, qualquer que seja).

Para esses casos, mudamos o foco de nossa visão dos tipos de dados abstratos resultantes de tempos em tempos. Às vezes, você se preocupa com a estrutura da sua árvore, alguns minutos depois, se preocupa em poder executar uma operação de localização, depois se pergunta sobre a exclusão de um nó e imediatamente sobre a aparência da estrutura posteriormente. Embora tudo isso ocorra também nas outras seções acima, isso não é o foco principal da sua mente, por exemplo, quando você armazena / recupera dados de / para uma Mapou quando classifica uma lista vinculada.

As estruturas de dados geralmente influenciam os detalhes de um algoritmo. Por esse motivo, os dois andam frequentemente de mãos dadas.

Considere, por exemplo, um algoritmo para cortar seu gramado. Como você cortará seu gramado provavelmente será influenciado pela estrutura real do seu gramado. Se você mora em uma casa pequena em um subúrbio densamente lotado e seu gramado é apenas um pequeno retângulo com alguns metros quadrados de área, você provavelmente prefere cortar o gramado com um cortador de grama em vez de um trator / cortador de grama. Se o seu gramado envolve muitos hectares de terrenos planos, sua preferência pode ser pelo cortador de grama em vez do cortador de grama (embora esse cortador possa eventualmente fazer o trabalho). Se o seu gramado envolve hectares de terra com grandes áreas planas, mas algumas pequenas colinas e várias árvores, você pode desenvolver um algoritmo mais interessante para cortar o gramado que envolve um cortador de grama e um cortador de grama ou outra grama técnicas de corte.

Em última análise, porém, a estrutura dos seus dados pode ter um impacto significativo nas suas decisões sobre como desenvolver seu algoritmo (ou quais algoritmos usar). Por esse motivo, os dois tópicos geralmente andam de mãos dadas.

E vice-versa: às vezes o algoritmo que queremos usar influencia (pelo menos no início da computação) as estruturas de dados que você desenvolve para dar suporte ao algoritmo. Por exemplo, passando de uma lista de matrizes para a ideia de uma lista vinculada e, eventualmente, para uma BST por armazenar uma lista ordenada que permitirá a localização rápida.