The problems can be viewed at ACM OJ, BUT it should be restricted to student-only for now.
- Instructor:
Bo Tang (唐博) - TA:
Yun Shen (沈昀) - Semester:
Fall 2023 - Textbook:
Data Structures and Algorithm Analysis in C++ (4th Edition)
The course contains only two parts, theory and lab. Project is excluded and the assignment is to finish all labs.
For quiz, midterm and final exams.
| Lecture | Content | Duration |
|---|---|---|
| Introduction | Intro to Data Structure and Algorithm | 1 week |
| Binary Search | Complexity Analysis and Binary Search | 2 weeks |
| Sort | Bubble Sort, Merge Sort and Quick Sort | 2 weeks |
| Linked List | Linked List and doubly Linked List | 1 week |
| Stack and Queue | Stack, Queue, Ring Queue and Deque | 1 week |
| String | KMP, Robin-Karp and FSM | 1 week |
| Tree | Intro to Tree and Advanced Tree | 2 weeks |
| Graph | Intro to Graph and Advanced Graph | 2 weeks |
Warning
The source codes are only for learning purpose. DON'T copy directly and submit to OJ, which might ruin you. Try understanding the idea, if trapped, feel free to contact me.
There're 10 labs in total and 6 problems for each lab with (15 + 15 + 20 + 20 + 25 + 25) points.
| Lab | Problem | Note |
|---|---|---|
| lab0 | Search Problem I | Brute Force |
| Welcome Lab | Search Problem II | Sort + Binary Search |
| Majsoul | Sort + Simulation | |
| Maximum difference | Greedy | |
| 3-D Print | Simulation | |
| Mahhjong | DFS | |
| lab1 | Binary Search | Binary Search Template |
| Complexity | Sum | Math + High Accuracy |
| Binary Search | Simple Problem | Binary Search |
| Counting Triples | Binary Search + Double Pointer | |
| Sport Meeting | Binary Search of Solutions + Greedy | |
| Catching Neko | Binary Search of Solutions + Simulation | |
| lab2 | Merge | Merge Sort Template (Merge part) |
| Sorting | Double Median | Sort |
| Bubble Sort | Count Inversions (Merge Sort) | |
| Lucky Number | Sort ( |
|
| Arrange Seats in a Round Table | Sort + Greedy | |
| Plants vs. Zombies | Sort + Greedy | |
| lab3 | Polynomial Summation | LinkedList Template |
| LinkedList | Help Narnal | LinkedList + Simulation (Text Editor) |
| Black era | LinkedList + Section Exchange + Sort | |
| LowbieH's best friend | LinkedList + Deletion + Sort | |
| Minimum Difference | LinkedList + Deletion + Sort | |
| Non-decreasing Sequence | LinkedList + Deletion + Optimization | |
| lab4 | Brackets Matching | Stack and Queue Template |
| Stack & Queue | Cinema | Queue |
| Deque | Playroom | Evaluation Process |
| Exciting Spider | Minimum Lexicographical Order | |
| Magic Sequences | Deque + Sliding Window | |
| Fencing Hall | Duque + Sliding Window | |
| lab5 | How many substrings | String Basic |
| String | Find Next | KMP Basic |
| FSA | FSA Basic | |
| Necklace! | Next Array | |
| Stick! | Rabin-Karp | |
| String Problem F | Next Array | |
| lab6 | Leaves | Leaf Node |
| Tree | Paths | Path between Root and Leaf Node |
| Pre, in and post | Tree Traversal | |
| Cut the Stick | Min Heap/Huffman Tree | |
| Giant | Search + Simulation | |
| Node Activation | Root Exchange DP | |
| lab7 | Judgement | Heap |
| Advanced Tree | Meet my friend HEAP! | Heap Swap |
| We only want the smallest | Heap + Greedy | |
| Funny Fluffy Tuzi | Heap + Simulation | |
| Nth Element in Sliding Window | AVL Tree + Nth Element | |
| Pet Adoption | AVL Tree + Succeeder | |
| lab8 | Adjacency Matrix | Matrix Representation |
| Graph | Shortest Path | BFS |
| Defensive Tower | Simulation | |
| Ancestor | DFS Order | |
| Sum | Search | |
| The Elves | Traverse | |
| lab9 | Travel | SPFA Shortest Path |
| Advanced Graph | Sign in Problem | Kruskal Minimum Spanning Tree |
| Game | Kruskal Maximum Spanning Tree | |
| Naive Problem | Dijstra + Multiple Source | |
| Simple Problem | Tarjan SCC | |
| Portal | Dijstra + Layer |