This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

Link to original blog: MOOC ZJU Data Structures After-Class Problems Record - PTA Data Structures Problem Set (Complete)

This blog records the problem sets done while studying data structures. Feel free to point out any mistakes in the code! It also serves as a summary of data structures~ PS: Since I had already learned C, all solutions are written in C, though there is also quite a bit of C language content. MOOC Portal

Week 1 - Maximum Subsequence Sum Algorithm & Binary Search

Code and approach linked in blog: PTA Data Structures Problem Set Week 1 - Maximum Subsequence Sum Algorithm & Binary Search

01-Complexity 1 Maximum Subsequence Sum Problem (20 pts)

01-Complexity 2 Maximum Subsequence Sum (25 pts)

01-Complexity 3 Binary Search (20 pts)

Week 2 - Linear Structures

Study notes linked in blogs: Linear Lists, Stacks After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 2 - Linear Structures

02-Linear Structure 1 Merging Two Sorted Linked List Sequences (15 pts)

02-Linear Structure 2 Polynomial Multiplication and Addition (20 pts)

02-Linear Structure 3 Reversing Linked List (25 pts)

02-Linear Structure 4 Pop Sequence (25 pts)

Week 3 - Planting Trees (Binary Trees, etc.)

Study notes linked in blogs: Binary Trees, Queues After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 3 - Planting Trees (Binary Trees, etc.)

03-Tree 1 Isomorphism of Trees (25 pts)

03-Tree 2 List Leaves (25 pts)

03-Tree 3 Tree Traversals Again (25 pts)

Week 4 - Binary Search Trees & AVL Trees

Study notes linked in blog: Binary Search Trees and AVL Trees After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 4 - Binary Search Trees & AVL Trees

04-Tree 4 Is It the Same Binary Search Tree (25 pts)

04-Tree 5 Root of AVL Tree (25 pts)

04-Tree 6 Complete Binary Search Tree (30 pts)

04-Tree 7 Binary Search Tree Operations (30 pts)

Week 5 - Heaps & Huffman Trees & Union-Find

Study notes linked in blog: Heaps, Huffman Trees, and Union-Find After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 5 - Heaps & Huffman Trees & Union-Find

05-Tree 7 Path in Heap (25 pts)

05-Tree 8 File Transfer (25 pts)

05-Tree 9 Huffman Codes (30 pts)

Week 6 - Graphs (Part 1)

Study notes linked in blog: Graphs After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 6 - Graphs (Part 1) Topics covered include basic graph representation and traversal methods (BFS, DFS)

06-Graph 1 List Connected Components (25 pts)

06-Graph 2 Saving James Bond - Easy Version (25 pts)

06-Graph 3 Six Degrees of Separation (30 pts)

Week 7 - Graphs (Part 2)

Study notes linked in blog: Graph Theory After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 7 - Graphs (Part 2) Topics covered include single-source shortest path algorithms (Floyd’s algorithm, Dijkstra’s algorithm)

07-Graph 4 Harry Potter’s Exam (25 pts)

07-Graph 5 Saving James Bond - Hard Version (30 pts)

07-Graph 6 Travel Planning (25 pts)

Week 8 - Graphs (Part 3)

Study notes linked in blogs: Minimum Spanning Tree (Kruskal’s & Prim’s Algorithms), Data Structures Study Notes <8> Sorting After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 8 - Graphs (Part 3) Topics covered include minimum spanning trees, topological sorting, and critical path problems

08-Graph 7 Connecting All Villages with Roads (30 pts)

08-Graph 8 How Long Does It Take (25 pts)

08-Graph 9 Critical Activities (30 pts)

Week 9 - Sorting (Part 1)

Study blogs linked: Data Structures Study Notes <8> Sorting, Iterative Merge Sort Implementation (For Reference) After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 9 - Sorting (Part 1) Topics covered include various sorting algorithms (insertion sort, merge sort, heap sort, etc.)

09-Sort 1 Sorting (25 pts)

09-Sort 2 Insert or Merge (25 pts)

09-Sort 3 Insertion or Heap Sort (25 pts)

Week 10 - Sorting (Part 2)

Study blog linked: Data Structures Study Notes <8> Sorting After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 10 - Sorting (Part 2) Topics covered include applications of various sorting algorithms, struct sorting, cycle detection in table sorting, etc.

10-Sort 4 Counting Work Experience (20 pts)

10-Sort 5 PAT Judge (25 pts)

10-Sort 6 Sort with Swap(0, i) (25 pts)

Week 11 - Hash Search

Study blog linked: Data Structures Study Notes <9> Hash Search After-class exercise code and approach linked in blog: PTA Data Structures Problem Set Week 11 - Hash Search Topics covered include hash search applications, KMP, etc.

11-Hash 1 Phone Chat Addict (25 pts)

11-Hash 2 Hashing (25 pts)

KMP String Pattern Matching (25 pts)

Summary

While solving these problems, I intentionally used the data structure definitions taught in the MOOC for some, while for others I took shortcuts using STL. It would be painful not to use convenient tools when they are available (e.g., priority queues replacing min/max heaps, maps replacing hash lookups — STL is really handy). Regardless, after procrastinating until the last minute, I finally finished everything. This super~ long summer break was not wasted lol. Time to keep up the momentum during winter break and prepare to learn Java~ The end! [just kidding]

MOOC ZJU Data Structures After-Class Problems Record - PTA Data Structures Problem Set (Complete)