README.md

Analysis of Algorithms Lab — 5CS4-23

Lab manual and complete Python source code for 5CS4-23 Analysis of Algorithms Lab, III Year / V Semester, B.Tech. Computer Science and Engineering, Rajasthan Technical University, Kota.

Ten experiments, twelve programs. Every program reads its input data from a Microsoft Excel workbook, so the data can be changed without touching the code. Every program in this repository was executed before the manual was written — the console output and the two timing graphs in the manual are the real output of those runs.

---

What to download

File	What it is
AOA_Lab_Manual_5CS4-23_RTU.pdf	The manual, ready to read or print
src/	The twelve .py files
xlsx/	The ten Excel input workbooks

---

Repository structure

.
├── AOA_Lab_Manual_5CS4-23_RTU.pdf
├── src/
│   ├── prog1_1.py    prog2_1.py    prog3_1.py    prog3_2.py
│   ├── prog4_1.py    prog5_1.py    prog6_1.py    prog7_1.py
│   └── prog7_2.py    prog8_1.py    prog9_1.py    prog10_1.py
├── xlsx/
│   ├── exp1_quicksort_input.xlsx   exp2_mergesort_input.xlsx
│   ├── exp3_graph_input.xlsx       exp4_knapsack_input.xlsx
│   ├── exp5_dijkstra_input.xlsx    exp6_kruskal_input.xlsx
│   ├── exp7_bfs_dfs_input.xlsx     exp8_prim_input.xlsx
│   └── exp9_floyd_input.xlsx       exp10_nqueens_input.xlsx
└── README.md

---

Getting started

Requirements: Python 3.8 or later.

pip install pandas openpyxl matplotlib

multiprocessing, used by the parallel merge sort, is part of the standard library.

Running a program — the workbook must be in the same folder as the .py file:

cp xlsx/exp4_knapsack_input.xlsx src/
cd src
python prog4_1.py

Or copy every workbook once and forget about it:

cp xlsx/*.xlsx src/ && cd src
python prog1_1.py

Experiments 1 and 2 take a minute or two, because they sort arrays of up to 320,000 elements several times over. They also write a PNG graph into the current folder when they finish.

---

The experiments

#	Experiment	Program	Workbook
1	Quicksort, and time taken versus n	prog1_1.py	exp1_quicksort_input.xlsx
2	Parallelized Merge Sort, and time taken versus n	prog2_1.py	exp2_mergesort_input.xlsx
3a	Topological ordering of a digraph (Kahn and DFS)	prog3_1.py	exp3_graph_input.xlsx
3b	Transitive closure using Warshall's algorithm	prog3_2.py	exp3_graph_input.xlsx
4	0/1 Knapsack using dynamic programming	prog4_1.py	exp4_knapsack_input.xlsx
5	Single source shortest paths — Dijkstra	prog5_1.py	exp5_dijkstra_input.xlsx
6	Minimum cost spanning tree — Kruskal	prog6_1.py	exp6_kruskal_input.xlsx
7a	Nodes reachable from a given node — BFS	prog7_1.py	exp7_bfs_dfs_input.xlsx
7b	Checking whether a graph is connected — DFS	prog7_2.py	exp7_bfs_dfs_input.xlsx
8	Minimum cost spanning tree — Prim	prog8_1.py	exp8_prim_input.xlsx
9	All pairs shortest paths — Floyd	prog9_1.py	exp9_floyd_input.xlsx
10	N-Queens using backtracking	prog10_1.py	exp10_nqueens_input.xlsx

Each experiment in the manual carries a problem description, the theory and algorithm, a complexity analysis table, the input data as it appears in the workbook, the source code, the console output, and viva voce questions with answers.

---

Editing the input data

Change the numbers in the workbook and re-run — no code change is needed. Every sheet uses the same layout, and the programs read it with skiprows=2:

Row	Contents
1	A descriptive title
2	Blank
3	The heading row
4 onward	The data

So the headings must stay on row 3. If you insert or delete a row above the headings, pandas will read the wrong line and the program will fail with a KeyError.

The data is not filler. The Dijkstra workbook holds a road network between six cities of Rajasthan; the Prim workbook holds the classic seven-vertex graph whose minimum spanning tree costs 39; the BFS digraph deliberately contains a component that cannot be reached from the start node, so the "not reachable" branch of the program actually prints something.

---

Two results worth reading

Quicksort (Experiment 1). As n went from 1,000 to 64,000 — a factor of 64 — the measured time grew by a factor of about 84. The n log n prediction is 102; n² would have predicted 4096. The program prints this comparison itself, which is the whole point of the experiment.

Parallel Merge Sort (Experiment 2). On a two-core machine the parallel version is slower than the sequential one below roughly n = 40,000, and only reaches about 1.5× speed-up at n = 320,000. The crossover is visible in the graph. Each worker process has to receive a copy of its block and send the sorted block back, and for a small array that copying costs more than the work it saves. Your own numbers will differ — record what your machine gives you rather than copying these.

---

Troubleshooting

Problem	Cause and fix
FileNotFoundError	The workbook is not in the folder you ran the program from. Copy the .xlsx next to the .py, or give the full path.
ImportError: Missing optional dependency 'openpyxl'	pip install openpyxl — pandas needs it to open .xlsx files.
KeyError: 'Value'	The heading row moved. Headings belong on row 3; check that skiprows=2 is still there.
First column reads as NaN	index_col=0 was dropped. It is needed when reading an adjacency matrix.
No graph appears over SSH	There is no display. The programs already call matplotlib.use("Agg") and save a PNG — look for the .png file rather than a window.
RuntimeError about the start method	Multiprocessing code must sit inside if __name__ == "__main__":. Program 2.1 already does.

---

A note for students

Use this as a reference for the algorithm and the report format, not as something to copy into your practical file unread. The viva questions at the end of each experiment are the ones examiners actually ask, and the complexity tables are worth learning before the external exam. Your timing measurements will not match the ones printed here — they depend on your processor, your memory and your Python version — so run the experiments yourself and record your own numbers.

---

License

Released under the MIT License. You are free to use, modify and distribute this material, including for teaching, with attribution.