🎯 Tema 3 PCLP - Advanced Data Structures & Algorithms

A comprehensive collection of advanced programming exercises focusing on data structures, algorithms, and low-level programming concepts implemented in C and Assembly.

📁 Project Structure

├── checker/                 # Automated testing framework
│   ├── checker.py          # Main checker script
│   ├── linter/             # Code quality analysis
│   └── task-{1-4}/         # Individual task checkers
├── src/                    # Source code implementations
│   ├── local_checker.py   # Local testing script
│   ├── linter/             # Code style enforcement
│   ├── task-1/             # Linked List Sorting
│   ├── task-2/             # String Operations
│   ├── task-3/             # K-Fibonacci Sequence
│   └── task-4/             # Composite Palindrome
└── local.sh               # Local testing utilities

🚀 Quick Start

Prerequisites

• GCC compiler
• NASM assembler
• Python 3.x (for checkers)
• Make utility

Building & Testing

Using Local Checker (Recommended)

# Navigate to src directory
cd src/

# Run checker without arguments to see available options
python3 local_checker.py

# Run all tasks
python3 local_checker.py --all

# Test specific task
python3 local_checker.py --task 1

# Run linter only
python3 local_checker.py --linter

# Create submission archive
python3 local_checker.py --zip

# Keep build files (no cleanup)
python3 local_checker.py --all --no_clean

Using Docker (Alternative)

# Build all tasks using Docker
./local.sh checker --all

# Test specific task
./local.sh checker --task 1

# Run linter
./local.sh checker --linter

Code Style Enforcement

# Navigate to linter directory
cd src/linter/

# Run linter without arguments to see options
./linter-script-file

# Lint specific file
./linter-script-file ../task-1/sortari.asm

# Lint all assembly files
./linter-script-file ../task-1/sortari.asm ../task-2/operatii.asm ../task-3/kfib.asm ../task-4/composite_palindrome.asm

📚 Tasks Overview

🔗 Task 1: Linked List Sorting

File: src/task-1/sortari.asm

Implements an efficient selection-sort algorithm for creating a sorted singly-linked list from an array of nodes.

Key Features:

• ✅ Non-destructive sorting (preserves original array structure)
• ✅ Memory-efficient node linking
• ✅ Assembly implementation for optimal performance

Algorithm Complexity:

• Time: O(n²)
• Space: O(1) - in-place linking

Memory Management:

• Uses existing node structures
• No dynamic allocation required
• Efficient pointer manipulation

📝 Task 2: String Operations

File: src/task-2/operatii.asm

Advanced string processing with word extraction and multi-criteria sorting.

Key Features:

• ✅ Delimiter-based word extraction (,, ., \n)
• ✅ Dual sorting criteria: length → lexicographic
• ✅ Assembly implementation with system calls

Memory Optimization:

• In-place string tokenization
• Minimal memory overhead
• Efficient pointer array management

🔢 Task 3: K-Fibonacci Sequence

File: src/task-3/kfib.asm

Recursive implementation of generalized Fibonacci sequence where each term is the sum of the previous K terms.

Mathematical Definition:

KFIB(n, k) = {
    0           if n < k
    1           if n = k
    Σ KFIB(n-i, k)  if n > k, i ∈ [1,k]
}

Key Features:

• ✅ Pure recursive implementation
• ✅ Elegant mathematical approach
• ✅ Handles edge cases efficiently

Complexity Analysis:

• Time: O(k^n) - exponential due to overlapping subproblems
• Space: O(n) - recursion depth

Constraints:

• 2 ≤ K ≤ 30 (Maximum Fibonacci type is 30)
• 2 ≤ n ≤ 40 (Maximum requested position is 40)
• K ≤ n (Result guaranteed to be > 0)

🔄 Task 4: Composite Palindrome Finder

File: src/task-4/composite_palindrome.asm

Finds the shortest lexicographically minimal palindrome from all possible string combinations.

Algorithm Strategy:

1. Combination Generation: Enumerates all 2ⁿ-1 possible string combinations
2. Palindrome Validation: Checks each concatenated result
3. Optimization: Two-pass algorithm for length-first, then lexicographic ordering

Key Features:

• ✅ Exhaustive search with pruning
• ✅ Lexicographic optimization
• ✅ Multiple subtasks with different constraints

Constraints:

• Subtask 1: Single string operations
• Subtask 2: 15 strings, max 10 characters each
• String alphabet: a-z (subtask 1), a-b only (subtask 2)

🛠️ Technical Implementation Details

Memory Management Strategies

• Task 1: Stack-based operations, no heap allocation
• Task 2: Efficient string tokenization with minimal copying
• Task 3: Recursive stack management
• Task 4: Dynamic allocation with proper cleanup

Code Quality Features

• Comprehensive linter integration via src/linter/
• Automated testing framework via src/local_checker.py
• Memory leak detection
• Performance benchmarking

Assembly Optimization

; Efficient node traversal using direct memory addressing
mov eax, [ebp + 8]    ; Load array address
mov ecx, [ebp + 12]   ; Load array size
; ... optimized selection sort implementation

📊 Performance Benchmarks

Task	Algorithm	Time Complexity	Space Complexity	Strengths
1	Selection Sort	O(n²)	O(1)	Memory efficient, Assembly optimized
2	String Processing	O(n log n)	O(n)	Efficient tokenization
3	Recursion	O(k^n)	O(n)	Mathematical elegance
4	Brute Force	O(2ⁿ × m)	O(m)	Exhaustive search guarantee

🔍 Code Quality & Testing

The project includes a comprehensive testing framework:

• Local Checker: src/local_checker.py - Main testing script
• Global Checker: checker/checker.py - Alternative checker
• Linter Integration: src/linter/ - Assembly code style enforcement
• Docker Support: Dockerfile - Containerized testing
• CI/CD Pipeline: .gitlab-ci.yml - Automated validation

Running Quality Checks

# Navigate to src directory first
cd src/

# Run all tests with linter and README check
python3 local_checker.py --all

# Run specific task
python3 local_checker.py --task 3

# Run only linter
python3 local_checker.py --linter

# Check specific assembly file
cd linter/
./linter-script-file ../task-1/sortari.asm

Individual Task Testing

Each task can be tested independently:

# Task 3 example - supports selective testing
cd src/task-3/
make
./checker 1    # Test first group only
./checker 2    # Test first 2 groups
./checker      # Test all groups

# Task 4 example - subtask testing
cd src/task-4/
make
./checker 1    # Test subtask 1
./checker 2    # Test subtask 2
./checker      # Test both subtasks

💡 Key Programming Concepts Demonstrated

🏗️ Data Structures

• Linked Lists: Dynamic node manipulation and traversal
• Arrays: Efficient memory access patterns
• Strings: Advanced text processing techniques

🧠 Algorithms

• Sorting: Selection sort with assembly optimization
• Recursion: Mathematical sequence generation
• Combinatorics: Exhaustive search with optimization
• String Processing: Multi-criteria sorting and tokenization

🔧 Systems Programming

• Assembly Language: Low-level optimization techniques
• Memory Management: Efficient allocation and deallocation
• Performance Optimization: Algorithm selection and implementation
• System Calls: Direct OS interaction

🎯 Software Engineering

• Testing: Comprehensive automated test suites
• Code Quality: Linting and style enforcement
• Documentation: Clear algorithmic explanations
• Modular Design: Separate checkers for each task

🌟 Project Highlights

1. Pure Assembly Implementation: All core algorithms implemented in x86 Assembly
2. Comprehensive Testing: Automated validation with edge case coverage
3. Memory Efficiency: Careful attention to memory usage and optimization
4. Academic Rigor: Implements fundamental CS algorithms with detailed analysis
5. Production Quality: Includes linting, testing, and CI/CD pipeline
6. Flexible Testing: Multiple testing options (local, Docker, individual tasks)

📈 Learning Outcomes

This project demonstrates proficiency in:

• Low-level programming and memory management
• Assembly language optimization techniques
• Algorithm design and analysis
• Data structure implementation
• Software testing and quality assurance
• Performance optimization techniques
• Systems programming concepts

---

Author: Iazinschi Mihail
Course: PCLP2 - Programming Concepts and Programming Languages 2