jwalsh / jwalsh/hy-algorithms

Implement online algorithms

Open
#39 0 comments 0 reactions 0 assignees View on GitHub
difficulty:hard
Dominant language
Hy
Stars
2
Forks
0
PR merge metrics
No merged PRs in 30d

Description

Create implementations for online algorithms:

## Online algorithm paradigms:
- Competitive analysis framework
- Adversarial models
- Randomized online algorithms
- Resource augmentation

## Classic online problems:
- Ski rental problem
- Secretary problem
- k-server problem
- Paging (cache replacement)
- Online scheduling
- Online bin packing
- Online matching

## Applications:
- Resource allocation
- Job scheduling
- Network routing
- Financial algorithms
- Memory management

## Requirements:
- Provide competitive ratio analysis
- Include lower bound proofs
- Create adversarial test cases
- Document practical applications

This collection will demonstrate algorithms that must make decisions with partial information, without knowledge of future inputs, which is essential in many real-time systems and reactive environments.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.