Algorithm Visualizer — Greedy & Dynamic Programming

A project demonstrating classic algorithm techniques through interactive visualizations. Built as part of the 2nd Year Algorithm Design course — CCC Submission.

---

Table of Contents

• Team Members
• Project Overview
• Folder Structure
• Web Interface — How to Use
• Python CLI — How to Run
• Algorithm 1 — Task Scheduler (Greedy)
• Algorithm 2 — 0/1 Knapsack (DP)
• Greedy vs Dynamic Programming
• Test Cases
• Sample CLI Output
• Output Files Generated
• Technologies Used
• References

---

Team Members

#	Name	Roll Number
1	K. Abiramasree	AP24110011197
2	P. Om Keerthana Bhavani	AP24110011229
3	K. Nandini	AP24110011363
4	S. Keerthi	AP24110011365
5	M. Sri Soumitha	AP24110011395

---

Project Overview

This project implements and visualizes two fundamental algorithm types:

#	Algorithm	Type	Problem Solved
1	Task Scheduler	Greedy	Job Sequencing with Deadlines
2	0/1 Knapsack	Dynamic Programming	Max value within weight capacity

Both algorithms are available through:

• Web Interface (index.html) — works in any browser, no setup needed
• Python CLI (algorithm-project/src/main.py) — command line with charts

---

Folder Structure

CCC_PROJECT/
│
├── algorithm-project/
│   ├── src/
│   │   ├── scheduler.py        ← Greedy algorithm logic
│   │   ├── knapsack.py         ← DP algorithm logic
│   │   ├── visualizer.py       ← Chart generation (matplotlib)
│   │   └── main.py             ← CLI entry point
│   │
│   ├── sample_input.json       ← Sample input data for CLI
│   ├── greedy_gantt.png        ← Generated Gantt chart
│   └── knapsack_chart.png      ← Generated Knapsack chart
│
├── tests/
│   ├── test_scheduler.py       ← Unit tests for greedy scheduler
│   └── test_knapsack.py        ← Unit tests for knapsack DP
│
├── images/                     ← UI screenshots for documentation
├── index.html                  ← Web interface (HTML + JS)
├── requirements.txt            ← Python dependencies
├── greedy_gantt.png            ← Generated chart output
├── knapsack_chart.png          ← Generated chart output
└── README.md                   ← Project documentation (this file)

---

Web Interface — How to Use

Step 1 — Open the Web Page

Just double-click index.html — opens directly in any browser. No installation. No internet. No server needed.

Step 2 — Tab 1: Task Scheduler (Greedy)

1. Enter a Job Name, Deadline (slot number), and Profit
2. Click + Add Job to add it to the list
3. Repeat for multiple jobs (or click Load Example Data to auto-fill 8 sample jobs)
4. Click Run Greedy Scheduler
5. See the results:
   • Stats — jobs scheduled, total profit, jobs skipped
   • Gantt timeline — which job is in which slot
   • Step-by-step greedy decisions log

Step 3 — Tab 2: 0/1 Knapsack (DP)

1. Enter an Item Name, Weight (kg), and Value
2. Click + Add Item to add it to the list
3. Set the Max Weight (capacity) at the bottom (or click Load Example Data to auto-fill 5 sample items)
4. Click Run 0/1 Knapsack (DP)
5. See the results:
   • Stats — max value, weight used, items picked
   • Selected items display
   • Full DP table with highlighted values
   • Traceback decisions log

Tip: Press the Enter key as a shortcut to run the active algorithm.

---

Python CLI — How to Run

1. Install Python Dependencies

pip install -r requirements.txt

2. Run Both Algorithms with Sample Data

python algorithm-project/src/main.py --input algorithm-project/sample_input.json

3. Run with Charts (saves PNG files)

python algorithm-project/src/main.py --input algorithm-project/sample_input.json --chart

4. Run Only One Algorithm

# Greedy Task Scheduler only
python algorithm-project/src/main.py --mode greedy --input algorithm-project/sample_input.json

# 0/1 Knapsack only
python algorithm-project/src/main.py --mode knapsack --input algorithm-project/sample_input.json

5. Compare Greedy vs Naive Approach

python algorithm-project/src/main.py --mode greedy --input algorithm-project/sample_input.json --compare --chart

6. Manual Input (no JSON file needed)

python algorithm-project/src/main.py

Then type each job/item one by one when prompted.

7. Run Unit Tests

python tests/test_scheduler.py
python tests/test_knapsack.py

---

Algorithm 1 — Task Scheduler (Greedy)

Problem Statement

Given n jobs, each with a deadline and a profit:

• Only one job can run per time slot
• A job must be completed at or before its deadline
• Goal: maximize total profit

Greedy Strategy

At every step, pick the highest profit job available and assign it to the latest free slot before its deadline.

This is called the Greedy Choice Property — making the locally best choice at each step leads to the globally optimal solution.

Algorithm Steps

Step 1: Sort all jobs by profit in DESCENDING order
Step 2: Find the maximum deadline value → create that many time slots
Step 3: Initialize all slots as empty
Step 4: For each job (highest profit first):
            Find the latest free slot at or before the job's deadline
            If found  → assign job to that slot, add profit
            If not    → skip the job
Step 5: Return the schedule and total profit

Worked Example

Input:

Job	Deadline	Profit
J1	2	100
J2	1	19
J3	2	27
J4	1	25

After sorting by profit: J1(100) > J3(27) > J4(25) > J2(19)

Slot assignment process:

Step	Job	Action
1	J1 (100, D:2)	Slot 2 is free — assign to Slot 2 [Scheduled]
2	J3 (27, D:2)	Slot 2 taken, Slot 1 free — assign to Slot 1 [Scheduled]
3	J4 (25, D:1)	Slot 1 taken, no free slot <= 1 — skip [Skipped]
4	J2 (19, D:1)	Slot 1 taken, no free slot <= 1 — skip [Skipped]

Final Schedule:

[ Slot 1: J3  27 ] [ Slot 2: J1  100 ]

Total Profit = 127
Jobs Scheduled = 2
Jobs Skipped = 2

Why Greedy is Correct Here

Exchange Argument Proof: Suppose we have an optimal schedule S that does NOT pick the highest-profit available job at some step. We can always swap in the higher-profit job without reducing total profit. Therefore the greedy schedule is at least as good as any other schedule — it is optimal.

Complexity Analysis

Operation	Time Complexity	Space Complexity
Sort jobs by profit	O(n log n)	O(1)
Assign each job to a slot	O(n * d)	O(d)
Total	O(n * d)	O(d)

Where n = number of jobs, d = maximum deadline value

---

Algorithm 2 — 0/1 Knapsack (Dynamic Programming)

Problem Statement

Given n items each with a weight and a value, and a knapsack with maximum weight capacity W:

• Each item can be taken once only (0 = leave it, 1 = take it)
• Total weight must not exceed W
• Goal: maximize total value

DP Strategy

Build a 2D table where:

dp[i][w] = maximum value achievable
           using the first i items
           with weight limit w

Fill the table bottom-up using the recurrence relation.

Recurrence Relation

If item i's weight > w (doesn't fit):
    dp[i][w] = dp[i-1][w]
                ^ skip item i, same value as without it

Else (item fits):
    dp[i][w] = max(
        dp[i-1][w],                          <- don't take item i
        dp[i-1][w - weight[i]] + value[i]    <- take item i
    )

Algorithm Steps

Step 1: Create a (n+1) x (W+1) table, fill with 0
Step 2: For i = 1 to n (each item):
            For w = 0 to W (each capacity):
                Apply recurrence relation
Step 3: Answer is at dp[n][W]
Step 4: Traceback — start at dp[n][W]:
            If dp[i][w] != dp[i-1][w] -> item i was taken
                subtract its weight, move to row i-1
            Else -> item i was not taken, move to row i-1

Worked Example

Items: Phone (W:1, V:60), Book (W:2, V:40), Watch (W:1, V:50) Capacity: W = 3

DP Table:

Item \ W	0	1	2	3
(none)	0	0	0	0
Phone (W:1, V:60)	0	60	60	60
Book (W:2, V:40)	0	60	60	100
Watch (W:1, V:50)	0	60	110	110

Answer: dp[3][3] = 110

Traceback:

• Row 3 (Watch): dp[3][3]=110 != dp[2][3]=100 -> Watch taken, w = 3-1 = 2
• Row 2 (Book): dp[2][2]=60 = dp[1][2]=60 -> Book not taken
• Row 1 (Phone): dp[1][2]=60 != dp[0][2]=0 -> Phone taken

Selected: Phone (60) + Watch (50) = 110

Why DP and NOT Greedy for Knapsack

Greedy (sort by value/weight ratio) does NOT work for 0/1 Knapsack because items cannot be split.

Counter-example (Greedy fails):

Item	Weight	Value	Ratio
A	1	6	6.0
B	2	10	5.0
C	3	12	4.0

Capacity = 5

• Greedy picks: A(1) + B(2) + partial C -> but 0/1 means no partial -> A + B = 16
• DP optimal: B(2) + C(3) = 22 (correct)

DP correctly finds 22 because it evaluates all combinations.

Complexity Analysis

Operation	Time Complexity	Space Complexity
Fill DP table	O(n * W)	O(n * W)
Traceback to find items	O(n)	O(1)
Total	O(n * W)	O(n * W)

Where n = number of items, W = maximum weight capacity

---

Greedy vs Dynamic Programming

Feature	Greedy	Dynamic Programming
Strategy	Locally optimal choice at each step	Solve all subproblems, combine results
Optimal?	Only for specific problem types	Always optimal (overlapping subproblems)
Speed	Fast — O(n log n) typically	Slower — O(n * W)
Memory	Low — O(d)	Higher — O(n * W)
Works for Task Scheduler?	Yes — provably optimal	Yes but overkill
Works for 0/1 Knapsack?	No — gives wrong answer	Yes — always correct
When to use	When greedy choice is provably safe	When problem has optimal substructure

---

Test Cases

Greedy Scheduler Tests

Test Name	Input	Expected Result
Basic schedule	J1(D:2,P:100), J2(D:1,P:19), J3(D:2,P:27), J4(D:1,P:25)	Profit = 127
Single slot	3 jobs all with deadline = 1	Only highest profit job scheduled
All jobs fit	3 jobs with unique deadlines 1, 2, 3	All 3 scheduled, profit = sum of all
Empty input	No jobs	Profit = 0, no crash
Greedy vs Naive	Same job list	Greedy profit >= Naive profit always

Knapsack DP Tests

Test Name	Input	Expected Result
Basic	A(W:2,V:6), B(W:2,V:10), C(W:3,V:12), Cap=5	Value = 22
Nothing fits	Single item with weight > capacity	Value = 0, no items chosen
All items fit	All items within capacity	All items chosen
Zero capacity	Any items, W = 0	Value = 0
Empty items list	No items, any capacity	Value = 0

---

Sample CLI Output

=======================================================
        GREEDY TASK SCHEDULER — RESULTS
=======================================================
Slot         Job ID          Profit
-------------------------------------------------------
Slot 1       J3              27
Slot 2       J1              100
Slot 3       J6              50
Slot 4       J8              60
-------------------------------------------------------
Total Profit:                          237
Jobs Scheduled:                            4
Jobs Skipped:                              4
=======================================================

DP TABLE (rows = items, columns = weight 0 to 6)
--------------------------------------------------------
Item           0    1    2    3    4    5    6
--------------------------------------------------------
[empty]        0    0    0    0    0    0    0
Laptop         0    0    0   90   90   90   90
Phone          0   60   60  90  150  150  150
Book           0   60   60   90  150  150  190
Camera         0   60   60   90  150  160  190
Watch          0   60  110  150  200  200  200
--------------------------------------------------------
Max value (dp[5][6]) = 200

=======================================================
        0/1 KNAPSACK (DP) — RESULTS
=======================================================
Item            Weight      Value
-------------------------------------------------------
Laptop           3 kg       90
Phone            1 kg       60
Watch            1 kg       50
-------------------------------------------------------
Total Weight:                      5 / 6 kg
Maximum Value:                        200
=======================================================

---

Output Files Generated (with --chart flag)

File	What It Shows
greedy_gantt.png	Gantt chart — job schedule timeline across slots
knapsack_chart.png	Bar chart — selected vs not-selected items by value
comparison_chart.png	Side-by-side comparison of Greedy vs Naive profit

---

Technologies Used

Technology	Version	Purpose
Python	3.x	Core algorithm implementation
matplotlib	>= 3.5.0	Chart and graph generation
HTML5	—	Web page structure
CSS3	—	Web page styling
Vanilla JavaScript	—	Web interface algorithm logic

---

References

• Cormen, T. H. et al. — Introduction to Algorithms (CLRS), Chapter 16: Greedy Algorithms
• Cormen, T. H. et al. — Introduction to Algorithms (CLRS), Chapter 15: Dynamic Programming
• GeeksforGeeks — Job Sequencing Problem
• GeeksforGeeks — 0/1 Knapsack Problem

---

This project was created purely for academic purposes as part of the
Coding-Skills-II course for academic year 2025-2026 — 2nd year.