Algorithms, Software Engineering Curriculum

Topic 4 – Introduction to Data Structures and Algorithms

Leave a comment

Why do I need to learn data structures and algorithms?

Your software should address real-world problems. While knowing a programming language is important for writing software, it doesn’t help you leverage existing solutions to save time and effort when building a system.

Many real-world problems have already been solved, and their solutions are documented as data structures and algorithms. It’s important to learn these so you don’t reinvent the wheel, enabling you to apply them to your specific problems, thereby reducing time and effort, or optimizing your solutions.

Additionally, learning algorithms and data structures will help you develop algorithmic thinking and problem-solving skills, which are essential for any software developer.

What can I do after finishing learning algorithms and data structures?

Given a problem, you’ll be able to choose the appropriate data structures to represent concepts in a computer.

You’ll be capable of writing a program that instructs the computer to:
– Store and search for data efficiently,
– Sort information,
– Compute irrational numbers,
– Find the shortest path between two locations, or
– Encrypt and decrypt sensitive information.

When examining source code, you’ll also be able to determine which program will run faster.

That sounds useful! How can I learn algorithms and data structures?

Please read this Jay Wengrow (2020). A Common-Sense Guide to Data Structures and Algorithms. Pragmatic Bookshelf first.

After that please read this Richard J. Trudeau (1993). Introduction to Graph Theory. Dover Publications book to learn about graph theory.

After that please read this Thomas H. Cormen et al. (2022). Introduction to Algorithms. The MIT Press book to learn in depth about algorithms and data structures.

Alternatively, please audit this MIT 6.006 – Introduction to Algorithms, Fall 2011 course (Lecture Notes).

After that, if you are interested in delving deeper into data structures and algorithms, you can audit this MIT 6.046J – Design and Analysis of Algorithms, Spring 2015 course (Lecture Notes).

Terminology Review:

  • Arrays.
  • Selection Sort.
  • Invariant Reasoning.
  • Order of Growth, Big O, Big Theta.
  • Insertion Sort. Complexity: O(n²).
  • Merge Sort, Recursion Tree. Complexity: O(nlgn).
  • Bubble Sort. Complexity: O(n²).
  • Quick Sort. Complexity: O(nlgn).
  • Counting Sort. Complexity: O(n + k).
  • Radix Sort. Complexity: O(nlogₙk).
  • Sets.
  • Stacks.
  • Queues.
  • Lists, Linked Lists, Sorted Lists.
  • Trees, Binary Trees, Heaps.
  • Heapsort. Complexity: O(nlgn).
  • Hash Tables, Maps, Dictionaries: Chaining, Division Method, Multiplication Method, Open Addressing, Linear Probing, Double Hashing, Cuckoo Hashing.
  • Linear Search.
  • Binary Search.
  • String Matching: Karp-Rabin Algorithm, Rolling Hash ADT.
  • Binary Trees: Depth, Height, Traversal Order.
  • Binary Search Trees (BST).
  • AVL Trees, Rotations, AVL Sort.
  • Sequence Binary Trees.
  • Red-Black Trees.
  • 2-3 Trees.
  • B-Trees.
  • B+ Trees.
  • Comparison Model of Computation, Decision Tree, Search Lower Bound, Sorting Lower Bound.
  • Hierarchical Structure.
  • Karatsuba’s Algorithm.
  • Newton’s Method for Computing Square Roots.
  • Graphs: Complete Graphs, The Handshaking Lemma, Identical Graphs, Graph Isomorphism,  Adjacency Lists, Implicit Graphs, Adjacency Matrix, Incidence Matrix.
  • Breadth-First Search: Shortest Paths.
  • Depth-First Search: Tree Edges, Nontree Edges (Back Edges, Forward Edges, Cross Edges), Cycle Detection, Job Scheduling, Topological Sort.
  • Dijkstra’s Algorithm.
  • Bellman–Ford Algorithm.
  • Single-source Single-target Dijkstra.
  • Bi-Directional Search.
  • A* Algorithm.
  • Dynamic Programming: Subproblems, Guessing, Recursion and Memoization, Bottom-up, Topological Order, Original Problem and Parent Pointers.
  • Dynamic Programming Examples: Fibonacci Numbers, Text Justification, Parenthesization, Edit Distance.
  • Computational Difficulty: P, NP, EXP, R.
  • Hardness and Completeness: NP-hard, NP-complete, EXP-hard, EXP-complete.

After finishing learning about data structures and algorithms please click Topic 5 – Object-Oriented Programming to continue.

 

(Visited 103 times, 1 visits today)

Leave a Reply