Course: Advanced Algorithms (NYCU, Spring 2025)
Author: Terry Liu (312709045)
This repository contains my programming assignments for the NYCU Advanced Algorithms course. Each assignment is a self-contained directory with source code, sample test cases, and a detailed README explaining the algorithm design.
| # | Folder | Topic | Algorithm | Language | Complexity |
|---|---|---|---|---|---|
| 1 | assignment1-interval-dp/ |
Non-Crossing Matching Pairs | Interval Dynamic Programming | C++ | O(m²) time & space |
| 2 | assignment2-maze-router/ |
Single-Layer Maze Routing | BFS / Lee Algorithm | Python | O(N·W·H) time |
Problem: Given m points on a line and m/2 pre-defined pairs, find the maximum number of pairs that can be selected such that no two selected pairs cross each other.
Key Idea: Two pairs cross if and only if their endpoints interleave. We define dp[i][j] as the maximum non-crossing pairs over the sub-range [i, j] and fill the table bottom-up by considering whether the rightmost point j is matched inside or outside the range.
dp[i][j] = dp[i][j-1] // partner of j is outside [i,j]
dp[i][j] = dp[i+1][j-1] + 1 // partner of j is i
dp[i][j] = max(dp[i][j-1], dp[i][k-1] + dp[k+1][j-1] + 1) // partner of j is k ∈ (i,j)
→ See assignment1-interval-dp/README.md for full details.
Problem: Given a rectangular chip grid with blockages and an ordered list of two-pin nets, route as many nets as possible. Each routed net must follow the shortest Manhattan path; ties are broken by minimizing bends.
Key Idea: Model the chip as a 2-D grid. For each net, run BFS (the Lee Algorithm) using state (x, y, direction) to track bend count. Once a net is routed, its wire cells become permanent obstacles for subsequent nets.
BFS state: (x, y, dir)
Cost key: (path_length, bends) ← ensures shortest & straightest path
→ See assignment2-maze-router/README.md for full details, test cases, and validation instructions.
cd assignment1-interval-dp
g++ -O2 -std=c++17 -o solution main.cpp
./solution < input.txtcd assignment2-maze-router
python main.py sample.in sample.out
cat sample.out
# Validate correctness
python evaluator_pure_v1.py sample.in sample.out25springalgorithm/
├── README.md ← This file
├── .gitignore
│
├── assignment1-interval-dp/ ← Assignment 1
│ ├── main.cpp ← Interval DP solution (C++)
│ └── README.md
│
└── assignment2-maze-router/ ← Assignment 2
├── main.py ← BFS/Lee router (Python)
├── evaluator_pure_v1.py ← Legality checker
├── Makefile
├── sample.in ← Sample input
├── shortest_path.in / .out ← Test: basic shortest paths
├── congestion.in / .out ← Test: congested routing
├── in_turn.in / .out ← Test: sequential routing
├── trade_off.in / .out ← Test: length vs. bend trade-offs
├── trap.in / .out ← Test: deadlock scenarios
└── README.md