Data Structure and Algorithm 数据结构与算法
Course Number: 27000170, 3 Credits and 22011430, 2 Credits
School of Computer Science, Nanjing University
The course begins by showing how fundamental data organization methods, like arrays, linked lists, stacks, and queues, are structured and manipulated in memory. We learned how the choice of a data structure directly impacts data retrieval efficiency, and how abstract data types bridge the gap between conceptual problem-solving and actual code implementation. This knowledge has proven incredibly valuable for writing clean, optimized code from the ground up.
We also studied core algorithmic paradigms, such as recursion, divide-and-conquer, greedy approaches, and dynamic programming. The complexity analysis module showed me how to use Big O, Big \(\Theta\), and Big \(\Omega\) notations to evaluate time and space complexity, giving me a rigorous framework to predict program performance and analyze amortized bounds before running any code.
The course also delved into advanced, highly optimized structures, teaching us the intricacies of self-balancing trees, hashing techniques, and Fibonacci heaps. Learning how Fibonacci heaps achieve outstanding amortized running times for priority queue operations—especially in decreasing keys—helped me understand the structural innovations required to push theoretical limits to their edge.
As we progressed into complex network topologies, we covered graph traversal algorithms, shortest-path solutions, and advanced network flow problems. Mastering concepts like the Max-Flow Min-Cut theorem, alongside the Ford-Fulkerson and Edmonds-Karp algorithms, provided deep insights into how real-world routing, logistics, and resource allocation challenges are modeled and solved.
Furthermore, we explored scenarios where traditional deterministic approaches fall short. The module on randomized algorithms introduced me to the elegance of using probability—such as in Quicksort pivots or Primality testing—to trade certainty for massive gains in average-case efficiency and simplicity. Meanwhile, our study of online algorithms and competitive analysis shed light on how to make real-time, irreversible decisions under uncertainty, without full knowledge of future inputs.
We concluded with an introduction to NP-completeness and approximation algorithms, which taught us how to gracefully handle computationally intractable problems. This provided crucial context for understanding how data management, mathematical modeling, and algorithmic design collaborate to solve enterprise-level, computationally intensive problems both efficiently and scalably.