Design-and-Analysis-of-Algorithms-Assignments

KO | EN

gitlite — search

#gemini #git #privacy #codex #tensorflow #java #developer-tools #golang #graphql #http

Design-and-Analysis-of-Algorithms-Assignments

(★ 9)

Assignments of Design and Analysis of Algorithms

File Explorer

ZIP Download

- - q1_growth_order.c
  - README.md
  - sample.txt
- - coin_toss_analysis.csv
  - coin_toss_analysis.svg
  - q2_coin_toss.c
  - README.md
  - sample.txt
- - bubble_sort_analysis.csv
  - bubble_sort_analysis.svg
  - q3_bubble_sort_performance_analysis.c
  - README.md
  - sample.txt
- - q4_towers_of_hanoi.c
  - README.md
  - sample.txt
  - toh.csv
  - toh.svg
- - q5_partition_point.c
  - README.md
  - sample.txt
- - q6_element_uniqueness.c
  - README.md
  - sample.txt
- 2026_Week1_DAA_Lab_01.pdf
- - q1_dictionary_operations.c
  - README.md
  - sample.txt
- - q2
  - q2_merge_sort_variants.c
  - README.md
  - sample.txt
- - q3
  - q3_merge_k_sorted_arrays.c
  - README.md
  - sample.txt
- 2026_Week2_DAA_Lab_02.pdf
- - q1_binary_vs_ternary_search.c
  - README.md
  - sample.txt
- - q2_defective_coin.c
  - README.md
  - sample.txt
- - q3_max_min_divide_conquer.c
  - README.md
  - sample.txt
- - q4_strassen_matrix_multiply.c
  - README.md
  - sample.txt
- - q5_pattern_matrix_multiply.c
  - README.md
  - sample.txt
- - q6_selection_sort_invariant.c
  - README.md
  - sample.txt
- 2026_Week3_DAA_Lab_03.pdf
- - q1_three_colour_stable_sort.c
  - README.md
  - sample.txt
- - q2_pair_sum_two_sets.c
  - README.md
  - sample.txt
- - q3_k_sum_subset.c
  - README.md
  - sample.txt
- - q4_party_peak_occupancy.c
  - README.md
  - sample.txt
- - q5_merge_intervals.c
  - README.md
  - sample.txt
- - q6_max_overlap_point.c
  - README.md
  - sample.txt
- 2026_Week4_DAA_Lab_04.pdf
- - q1_median_without_sorting.c
  - README.md
  - sample.txt
- - q2_kth_smallest_without_sorting.c
  - README.md
  - sample.txt
- - q3_quicksort_file.c
  - README.md
  - sample.txt
- - q4_heapsort_file.c
  - README.md
  - sample.txt
- 2026_Week1_DAA_Lab_05.jpeg
- - q1_array_operations.c
  - README.md
  - sample.txt
- - q2_matrix_operations.c
  - README.md
  - sample.txt
- - q3_convolution_fft.c
  - README.md
  - sample.txt
- - q4_sort_by_reversals.c
  - README.md
  - sample.txt
- 2026_Week6_DAA_Lab_06.pdf
- - q1_invert_coin_triangle.c
  - README.md
  - sample.txt
- - q2_super_egg_testing.c
  - README.md
  - sample.txt
- - q3_reves_puzzle.c
  - README.md
  - sample.txt
- - q4_security_switches.c
  - README.md
  - sample.txt
- - q5_moving_target.c
  - README.md
  - sample.txt
- - q6_scientists_alive.c
  - README.md
  - sample.txt
- - q7_matrix_chain.c
  - README.md
  - sample.txt
- 2026_Week7_DAA_Lab_07.pdf
README.md

# Use via CDN

jsDelivr

jsDelivr serves any public GitHub repository as a CDN with zero setup. Pick a version and a file to get a ready-to-paste link and snippet.

Version

File

Link

Example

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

<h1 align="center">Design and Analysis of Algorithms</h1>

DAA Laboratory Assignments — IIIT Bhubaneswar

---

## Overview

This repository is my running record of the Design and Analysis of Algorithms
Laboratory at IIIT Bhubaneswar. Every lab session gets its own folder, and each
question inside it gets a folder of its own containing the solution, its
documentation, and a sample test case.

DAA is less about getting a program to run and more about showing how it behaves
as the input grows. So most programs here do two jobs at once: they solve the
problem, and then they instrument themselves — counting comparisons, counting
moves, tabulating values across decades of `n` — so the growth can be shown
rather than asserted. Week 1 exports its measurements to CSV and commits a plot
beside the source; Week 2 commits its plots too, and additionally prints its
measurements as tables, each one normalised by the growth function it is supposed
to follow, so a flat column is the proof. Week 3 prints the solved recurrence as
a column of its own — `3n/2 − 2`, `n(n−1)/2`, `7^log₂n` — beside the measured
count, so the two columns can be read as an equality rather than an
approximation, and every count is printed only after the answer that produced it
has been checked against a brute-force reference. Week 4 keeps the table and the
brute-force cross-check but drops the expectation of a flat column: its ratios
climb, and each is printed beside the ceiling it climbs towards — `2 − 1/log₂ n`,
`1/(k−1)!`, `1 − c/log₂ m` — because `O(n log n)` bounds a ratio rather than
fixing it, so convergence, not flatness, is what the bound actually asks for.
Week 5 goes back to exact closed forms — `2(1 + ln 2)n` for selection,
`2(n+1)H(n) − 4n` for quicksort's average, `2n` for building a heap — and adds a
second table beside the first: one that holds `n` fixed and varies the *shape* of
the input instead. For selection and sorting the size is not what decides the
complexity class; the pivot rule and the distribution of keys are, and a table of
random inputs alone would quietly hide that a last-element pivot needs
`n(n−1)/2` comparisons on a list that is already sorted. Week 6 returns to
compact classroom implementations: direct array scans, bubble sort where a
sorted copy is useful, standard matrix loops and Gaussian elimination, a
recursive FFT, and reversal-only sorting. Week 7 applies geometric reasoning,
dynamic programming, recursive search, event sweeps, and matrix-chain
optimization to seven algorithmic puzzles. Each program prints one worked
example and a short complexity summary, with no plot directories in Weeks 6 and
7.

**Every question has its own README** with the problem statement, approach,
complexity analysis, and worked sample. Start from the [Lab Index](#lab-index)
below.

| Field | Details |
|-------|---------|
| Name | Raghvendra Singh |
| Student ID | B125092 |
| Branch | Computer Science and Engineering (CSE-B) |
| Institute | IIIT Bhubaneswar |
| Course | Design and Analysis of Algorithms Laboratory |
| Semester | B.Tech 3rd Semester |
| Instructor | Dr. Ajaya Kumar Dash |

---

## Repository Structure

Each lab session has its own folder. Every question folder contains the C source,
its README, and a sample output; some earlier weeks also include generated plots
or data files.

<details>
<summary>Every file, as a conventional tree</summary>

```text
Design-and-Analysis-of-Algorithms-Assignments/
│
├── README.md                                   # this file — overview and navigation
│
├── WEEK 1/
│   ├── 2026_Week1_DAA_Lab_01.pdf               # question paper
│   │
│   ├── Q1/                                     # Put Them in Order
│   │   ├── README.md
│   │   ├── q1_growth_order.c
│   │   ├── sample.txt
│   │   └── plots/                              # 7 plots of the 12 functions
│   │       ├── 1_overview_linear.png
│   │       ├── 2_group_a_sublinear.png
│   │       ├── 3_group_b_linear_quad.png
│   │       ├── 4_group_c_fast.png
│   │       ├── 5_all_loglog.png
│   │       ├── 6_decades_log10.png
│   │       └── 7_crossovers.png
│   │
│   ├── Q2/                                     # Fair vs Biased Coin
│   │   ├── README.md
│   │   ├── q2_coin_toss.c
│   │   ├── sample.txt
│   │   ├── coin_toss_analysis.csv              # generated by Q2
│   │   └── coin_toss_analysis.svg
│   │
│   ├── Q3/                                     # Bubble Sort Performance
│   │   ├── README.md
│   │   ├── q3_bubble_sort_performance_analysis.c
│   │   ├── sample.txt
│   │   ├── bubble_sort_analysis.csv            # generated by Q3
│   │   └── bubble_sort_analysis.svg
│   │
│   ├── Q4/                                     # Towers of Hanoi
│   │   ├── README.md
│   │   ├── q4_towers_of_hanoi.c
│   │   ├── sample.txt
│   │   ├── toh.csv                             # generated by Q4
│   │   └── toh.svg
│   │
│   ├── Q5/                                     # Find the Partition Point
│   │   ├── README.md
│   │   ├── q5_partition_point.c
│   │   └── sample.txt
│   │
│   └── Q6/                                     # Element Uniqueness
│       ├── README.md
│       ├── q6_element_uniqueness.c
│       └── sample.txt
│
├── WEEK 2/
│   ├── 2026_Week2_DAA_Lab_02.pdf               # question paper
│   │
│   ├── Q1/                                     # Dictionary Operations
│   │   ├── README.md
│   │   ├── q1_dictionary_operations.c          # all six structures, measurement, validation
│   │   ├── sample.txt
│   │   └── plots/                              # 6 plots of the 42 measured cells
│   │       ├── 1_all_operations.png
│   │       ├── 2_search.png
│   │       ├── 3_per_structure.png
│   │       ├── 4_complexity_table.png
│   │       ├── 5_cost_at_max_n.png
│   │       └── 6_doubling_ratio.png
│   │
│   ├── Q2/                                     # Merge Sort vs Three-Way Merge Sort
│   │   ├── README.md
│   │   ├── q2_merge_sort_variants.c
│   │   ├── sample.txt
│   │   └── plots/                              # 4 plots of the two variants
│   │       ├── 1_growth_comparisons.png
│   │       ├── 2_normalised_constants.png
│   │       ├── 3_base_of_logarithm.png
│   │       └── 4_tradeoff.png
│   │
│   └── Q3/                                     # Merging k Sorted Arrays
│       ├── README.md
│       ├── q3_merge_k_sorted_arrays.c
│       ├── sample.txt
│       └── plots/                              # 5 plots of the two methods
│           ├── 1_growth_moves.png
│           ├── 2_normalised_constants.png
│           ├── 3_speedup.png
│           ├── 4_sweep_n.png
│           └── 5_merge_tree_shape.png
│
├── WEEK 3/
│   ├── 2026_Week3_DAA_Lab_03.pdf               # question paper
│   │
│   ├── Q1/                                     # Binary Search vs Ternary Search
│   │   ├── README.md
│   │   ├── q1_binary_vs_ternary_search.c
│   │   ├── sample.txt
│   │   └── plots/                              # binary and ternary, 2 plots
│   │       ├── 1_comparisons_growth.png
│   │       └── 2_cost_per_level_and_ratio.png
│   │
│   ├── Q2/                                     # Search the Defective Coin
│   │   ├── README.md
│   │   ├── q2_defective_coin.c
│   │   ├── sample.txt
│   │   └── plots/                              # the log3 bound, 2 plots
│   │       ├── 1_weighings_growth.png
│   │       └── 2_bound_margin.png
│   │
│   ├── Q3/                                     # Max and Min using Divide and Conquer
│   │   ├── README.md
│   │   ├── q3_max_min_divide_conquer.c
│   │   ├── sample.txt
│   │   └── plots/                              # the 3n/2 - 2 bound, 2 plots
│   │       ├── 1_comparisons.png
│   │       └── 2_saving.png
│   │
│   ├── Q4/                                     # Matrix Multiplication, Strassen's Method
│   │   ├── README.md
│   │   ├── q4_strassen_matrix_multiply.c
│   │   ├── sample.txt
│   │   └── plots/                              # multiplications, totals, crossover
│   │       ├── 1_multiplications.png
│   │       ├── 2_total_operations.png
│   │       └── 3_crossover.png
│   │
│   ├── Q5/                                     # Multiplying Special-Pattern Matrices
│   │   ├── README.md
│   │   ├── q5_pattern_matrix_multiply.c
│   │   ├── sample.txt
│   │   └── plots/                              # n multiplications, 2 plots
│   │       ├── 1_operations_growth.png
│   │       └── 2_normalised_constant.png
│   │
│   └── Q6/                                     # Selection Sort and Loop Invariants
│       ├── README.md
│       ├── q6_selection_sort_invariant.c
│       ├── sample.txt
│       └── plots/                              # one panel: the three curves coincide
│           └── 1_comparisons_identical.png
│
├── WEEK 4/
│   ├── 2026_Week4_DAA_Lab_04.pdf               # question paper
│   │
│   ├── Q1/                                     # Sorting Pairs by Colour in Linear Time
│   │   ├── README.md
│   │   ├── q1_three_colour_stable_sort.c
│   │   ├── sample.txt
│   │   └── plots/                              # the 3n touches, stability, 2 plots
│   │       ├── 1_linearity.png
│   │       └── 2_stability.png
│   │
│   ├── Q2/                                     # A Pair from Two Sets Summing to x
│   │   ├── README.md
│   │   ├── q2_pair_sum_two_sets.c
│   │   ├── sample.txt
│   │   └── plots/                              # sort, search and walk, 2 plots
│   │       ├── 1_growth.png
│   │       └── 2_ratio.png
│   │
│   ├── Q3/                                     # Do k of n Integers Sum to T?
│   │   ├── README.md
│   │   ├── q3_k_sum_subset.c
│   │   ├── sample.txt
│   │   └── plots/                              # the n^(k-1) log n bound, 3 plots
│   │       ├── 1_probes.png
│   │       ├── 2_ratio.png
│   │       └── 3_saving.png
│   │
│   ├── Q4/                                     # Peak Simultaneous Attendance at the Party
│   │   ├── README.md
│   │   ├── q4_party_peak_occupancy.c
│   │   ├── sample.txt
│   │   └── plots/                              # the half-open sweep, 3 plots
│   │       ├── 1_growth.png
│   │       ├── 2_ratio.png
│   │       └── 3_worked_example.png
│   │
│   ├── Q5/                                     # Merging Overlapping Intervals
│   │   ├── README.md
│   │   ├── q5_merge_intervals.c
│   │   ├── sample.txt
│   │   └── plots/                              # the n - 1 merge steps, 3 plots
│   │       ├── 1_growth.png
│   │       ├── 2_ratio_and_compression.png
│   │       └── 3_worked_example.png
│   │
│   └── Q6/                                     # The Point Lying in the Most Intervals
│       ├── README.md
│       ├── q6_max_overlap_point.c
│       ├── sample.txt
│       └── plots/                              # the closed-interval sweep, 3 plots
│           ├── 1_growth.png
│           ├── 2_ratio.png
│           └── 3_worked_example.png
│
├── WEEK 5/
│   ├── 2026_Week1_DAA_Lab_05.jpeg              # question paper (photographed)
│   │
│   ├── Q1/                                     # The Median Without Sorting
│   │   ├── README.md
│   │   ├── q1_median_without_sorting.c
│   │   ├── sample.txt
│   │   └── plots/                              # selection stays linear, 2 plots
│   │       ├── 1_growth.png
│   │       └── 2_ratio.png
│   │
│   ├── Q2/                                     # The K'th Smallest Without Sorting
│   │   ├── README.md
│   │   ├── q2_kth_smallest_without_sorting.c
│   │   ├── sample.txt
│   │   └── plots/                              # cost against the rank, 2 plots
│   │       ├── 1_cost_vs_k.png
│   │       └── 2_growth.png
│   │
│   ├── Q3/                                     # Quicksort on N Elements in a File
│   │   ├── README.md
│   │   ├── q3_quicksort_file.c
│   │   ├── sample.txt
│   │   └── plots/                              # the exact average, six shapes, 2 plots
│   │       ├── 1_growth.png
│   │       └── 2_pivot_rules.png
│   │
│   ├── Q4/                                     # Heapsort on N Elements in a File
│   │   ├── README.md
│   │   ├── q4_heapsort_file.c
│   │   ├── sample.txt
│   │   └── plots/                              # Floyd's 2n build, the guarantee, 2 plots
│   │       ├── 1_build.png
│   │       └── 2_guarantee.png
│   │
│   └── make_plots.py                           # redraws the eight figures above
│
├── WEEK 6/
    ├── 2026_Week6_DAA_Lab_06.pdf               # question paper
    │
    ├── Q1/                                     # Operations on an Unsorted Array
    │   ├── README.md
    │   ├── q1_array_operations.c
    │   └── sample.txt
    │
    ├── Q2/                                     # Operations on Square Matrices
    │   ├── README.md
    │   ├── q2_matrix_operations.c
    │   └── sample.txt
    │
    ├── Q3/                                     # Vector Convolution with the FFT
    │   ├── README.md
    │   ├── q3_convolution_fft.c
    │   └── sample.txt
    │
    └── Q4/                                     # Sorting a Permutation by Reversals
        ├── README.md
        ├── q4_sort_by_reversals.c
        └── sample.txt

└── WEEK 7/
    ├── 2026_Week7_DAA_Lab_07.pdf               # question paper
    ├── Q1/                                     # Invert the coin triangle
    │   ├── README.md, q1_invert_coin_triangle.c, sample.txt
    ├── Q2/                                     # Super egg testing
    │   ├── README.md, q2_super_egg_testing.c, sample.txt
    ├── Q3/                                     # Reve's four-peg puzzle
    │   ├── README.md, q3_reves_puzzle.c, sample.txt
    ├── Q4/                                     # Security switches, recursive DFS
    │   ├── README.md, q4_security_switches.c, sample.txt
    ├── Q5/                                     # Hitting a moving target
    │   ├── README.md, q5_moving_target.c, sample.txt
    ├── Q6/                                     # Scientists alive at once
    │   ├── README.md, q6_scientists_alive.c, sample.txt
    └── Q7/                                     # Matrix-chain multiplication
        ├── README.md, q7_matrix_chain.c, sample.txt
```

</details>

---

## Lab Index

| Lab | Topic | Date | Questions | Folder |
|-----|-------|------|-----------|--------|
| Lab 01 | Growth of functions, empirical analysis, recurrences | 28 Jul 2026 | 6 | [WEEK 1](WEEK%201) |
| Lab 02 | Data structure trade-offs, divide and conquer, the master theorem | 04 Aug 2026 | 3 | [WEEK 2](WEEK%202) |
| Lab 03 | Divide and conquer — search, matrix multiplication, loop invariants | 11 Aug 2026 | 6 | [WEEK 3](WEEK%203) |
| Lab 04 | Applications of sorting — counting sort, sorted search, event sweeps | 18 Aug 2026 | 6 | [WEEK 4](WEEK%204) |
| Lab 05 | Selection and sorting — quickselect, quicksort, heapsort | 25 Aug 2026 | 4 | [WEEK 5](WEEK%205) |
| Lab 06 | Array and matrix costs, FFT convolution, reversal sorting | 31 Aug 2026 | 4 | [WEEK 6](WEEK%206) |
| Lab 07 | Algorithmic puzzles, DP, recursive search, event sweeps, MCM | 08 Sep 2026 | 7 | [WEEK 7](WEEK%207) |

Each row below links directly to its lab folder and question documentation.

### WEEK 1 — Lab 01

> Growth rates, randomised simulation, and counting the work an algorithm
> actually does.

[Open the Week 1 folder](WEEK%201)

### WEEK 2 — Lab 02

> Choosing a data structure by what it costs, and what changes — and what does not —
> when you split a problem into more than two pieces.

[Open the Week 2 folder](WEEK%202)

### WEEK 3 — Lab 03

> Splitting a problem and paying for the split: when a three-way division wins,
> when it loses, and what structure in the input is worth.

[Open the Week 3 folder](WEEK%203)

### WEEK 4 — Lab 04

> Sorting as the step that comes first: what it buys you — a lookup instead of a
> scan, a sweep instead of every pair — and what it cannot buy.

[Open the Week 4 folder](WEEK%204)

### WEEK 5 — Lab 05

> One order statistic without sorting anything, and then sorting properly: where
> the constant in front of `n log n` comes from, and what a worst-case guarantee
> costs when you insist on one.

[Open the Week 5 folder](WEEK%205)

### WEEK 6 — Lab 06

> Worst-case costs on arrays and matrices, FFT convolution, and sorting when the
> permitted primitive is reversal rather than comparison or swap.

[Q1 — Array operations](WEEK%206/Q1) ·
[Q2 — Matrix operations](WEEK%206/Q2) ·
[Q3 — FFT convolution](WEEK%206/Q3) ·
[Q4 — Sorting by reversals](WEEK%206/Q4)

### WEEK 7 — Lab 07

> Puzzle applications using geometric reasoning, dynamic programming, recursive
> state search, event sweeps, and matrix-chain optimization. Every question
> includes a compact C implementation, README derivation, and captured sample
> output.

[Q1 — Coin triangle](WEEK%207/Q1) ·
[Q2 — Super egg testing](WEEK%207/Q2) ·
[Q3 — Reve's puzzle](WEEK%207/Q3) ·
[Q4 — Security switches](WEEK%207/Q4) ·
[Q5 — Moving target](WEEK%207/Q5) ·
[Q6 — Scientists alive](WEEK%207/Q6) ·
[Q7 — Matrix chain](WEEK%207/Q7)

## Features

- **Self-documenting programs.** The analysis travels with the code. Week 1 and
  Week 2 solutions print their own time and space complexity before exiting;
  Week 3 closes instead with the recurrence it solved and the conclusion drawn
  from it — `T(n) = 2T(n/2) + 2 → 3n/2 − 2`, and so on for each question. Week 4
  closes with the bound it has just demonstrated together with a reading of the
  column that demonstrates it, naming what that column converges to and why.
  Week 5 prints both halves of the derivation: the recurrence *and* the closed
  form it solves to, `T(n) = T(n/2) + n → 2(1 + ln 2)n ≈ 3.386n` for selection,
  and where a sum is the honest derivation rather than a recurrence, the sum
  itself — `Σ 2h·n/2^(h+1) = 2n` for building a heap — followed in each case by
  which measured column the reader is being asked to check it against. Weeks 6
  and 7 use a shorter classroom style: each code file demonstrates one readable
  example and then prints the complexity of the loops, recurrence, or search it
  just used.
- **Empirical alongside asymptotic.** Programs that study growth measure it
  rather than assume it. Week 1 writes its measurements to CSV and commits the
  plot as SVG beside the source; Week 2 commits its plots as PNG and also prints
  the counts as a table, dividing each one by the growth function it should
  follow, so the claim stands or falls on whether that column stays flat. Week 3
  goes further and prints the exact closed form as a column of its own next to
  the measured count, turning the check into an equality between two columns
  rather than a ratio that merely settles. Week 4 keeps the same layout and
  argues the other way round: its ratio columns rise monotonically, and the
  reading explains what each is rising towards — `2 − 1/log₂ n` for a sort plus
  `n` searches, `1/(k−1)!` because only increasing tuples are enumerated,
  `1 − c/log₂ m` for a merge sort's linear correction term. A bound requires the
  ratio to stay bounded, not to stay constant, so the honest claim is
  convergence. Week 5 goes back to exact closed forms and keeps two normalising
  columns side by side to show why that matters: `obs/pred` divides quicksort's
  measured count by the exact average `2(n+1)H(n) − 4n` and stays within 1% over
  five decades, while dividing the same count by the leading term `n log₂ n`
  alone reads 1.27 rather than 1.386 — the gap is precisely the `−4n` that the
  closed form keeps and the leading term throws away. Beside each growth table
  sits a second one that fixes `n` and varies the *shape* of the input instead,
  because for selection and sorting the pivot rule and the distribution of keys
  decide the complexity class every bit as much as the size does.
- **Answers checked before counts are trusted.** Every Week 3 program validates
  its result against an independent reference and calls `exit(1)` on any
  disagreement — binary and ternary search against a linear scan, the coin
  search against every hiding place exhaustively, max–min three ways against one
  another, both matrix methods entry-by-entry against the naive triple loop, and
  selection sort's invariant asserted at initialisation, at every pass and at
  termination. A printed table is therefore evidence in itself: the numbers only
  appear because the algorithm was right at every size. Week 4 keeps that rule
  and adds two habits. Where the quadratic reference is no longer affordable the
  table prints `-` in that column rather than a number it did not earn, and the
  cheaper checks that survive — a re-count of the reported witness, a re-addition
  of the reported pair — still run at every size. And Q1 asserts that the *wrong*
  algorithm fails: the linear three-way partition is run beside the counting sort
  and caught breaking within-colour order from `n = 100` upward, so the property
  under test is shown to be discriminating rather than merely satisfied. Week 5
  runs into the one case where the obvious reference is circular — verifying a
  sort by sorting proves nothing — and replaces it with three cheap invariants
  that together are enough: ascending order, the sum of all keys, and their XOR,
  which catches the compensating errors a sum alone would miss, plus a count of
  bytes written against bytes read back. Selection *can* afford references and
  uses two, agreeing quickselect with a bounded heap and with a full sort over
  thousands of duplicate-heavy instances; heapsort re-checks the heap property
  across all `n` indices after every build. Week 6 keeps its checks small and
  visible: the array answers can be read from the example, FFT convolution is
  compared with the direct formula, and both reversal methods must produce the
  identity permutation. Week 7 validates the coin-triangle overlap, the 33-move
  Reve solution, every security-switch transition, and the matrix-chain cost
  reconstruction.
- **Verified samples.** Each question ships a `sample.txt` with input and output
  captured from an actual run, not written from memory.
- **Hand-written algorithms.** Every algorithm under study is implemented from
  scratch rather than delegated to a library routine, so the implementation is
  part of the answer. Week 4 is the deliberate exception, and says so where it
  matters: what is under study there is what sorting *buys*, so the sort is
  `qsort` and the `O(n log n)` worst case is inherited from the library's
  contract rather than proved — Q1, the one question whose subject is the sort
  itself, is written out by hand. Week 5 calls a library sort exactly once, for
  the same kind of reason: `qsort` runs beside the hand-written quicksort purely
  as a measuring stick, and the number it yields is the point of running it —
  18674766 comparisons against this quicksort's 25224169, with
  `log₂(n!) = 18488885` the floor no comparison sort can beat.
- **No external dependencies to build or run.** The C standard library only —
  nothing to install beyond a compiler, and nothing left behind after the program
  exits. Redrawing the committed figures is the single exception:
  `WEEK 5/make_plots.py` needs Python 3 and matplotlib. Nothing needs it in order
  to *read* the repository, since every figure is committed as an image.
- **Consistent documentation.** Every question README covers the same ground:
  problem statement, approach or analysis, complexity, sample input and output,
  explanation, and files — plus committed artefacts or figures wherever a
  question ships generated data. Weeks 1 and 2 use explicit build/run and
  complexity sections; Weeks 3 through 5 use detailed header tables and measured
  analysis; Weeks 6 and 7 use shorter classroom-style notes and complexity
  derivations.

---

## Requirements

| Tool | Version | Purpose |
|------|---------|---------|
| GCC | any C99/C11-capable release | Compilation |
| C standard library | — | `stdio.h`, `stdlib.h`, `string.h`, `time.h`, `math.h`, `float.h` |
| Python 3 + matplotlib | *optional* | Redrawing the Week 5 figures with `WEEK 5/make_plots.py`; not needed to build, run, or read anything |

That is the whole list, and the one optional row is optional in the strict
sense: every figure in the repository is committed as an image, so the Python is
needed only to redraw one. The programs themselves have no external dependencies
— Weeks 1 through 5 commit their plots, while Weeks 6 and 7 intentionally use
  console examples without plot folders. Reading the repository requires nothing but a
browser and running it requires nothing but GCC. Questions that pull in `math.h`
are linked with `-lm`; each question's README carries its exact build line.

Installing GCC, if it is not already present:

```bash
sudo apt update && sudo apt install build-essential      # Debian / Ubuntu
brew install gcc                                         # macOS
```

On **Windows**, use MinGW-w64 and append `.exe` to the output name.

A terminal with UTF-8 support is recommended — Week 1 Q1 to Q4 draw their ASCII
charts using block characters. The Week 2 through Week 7 programs use plain
ASCII output, so they render anywhere.

---

## Repository Conventions

- One folder per lab session, named `WEEK <n>`, containing the question paper and
 one subfolder per question.
- One folder per question, named `Q<number>`, containing the source, a `README.md`,
 a `sample.txt`, and any generated artefacts.
- Sources are named `q<number>_<short_description>.c` — the file name describes the
 problem, not just its number. One question, one source file.
- Every program closes with its own analysis — Weeks 1 and 2 print the time and
 space complexity, Week 3 prints the recurrence it solved and the conclusion
 that follows, Week 4 prints the bound it demonstrated together with what its
 normalising column converges to, and Week 5 prints the recurrence — or the sum,
 where a sum is the honest derivation — beside the exact closed form its
 measured column is divided by. Weeks 6 and 7 instead close each small example
 with a direct complexity summary suitable for a classroom lab submission.
- Growth data is shown, never asserted. Week 1 writes a CSV and commits a
 hand-written `.svg` of the same name; Week 2 commits its plots under `plots/`
 and prints the measured counts as a table alongside a column normalised by the
 growth function under test; Week 3 keeps that layout and adds the exact closed
 form as a column of its own; Week 4 keeps it too and reads the normalised
 column as a converging one, printing `-` wherever the reference check it is
 compared against was too expensive to run; Week 5 keeps the closed-form column
 and puts a second table beside each growth table, one that holds `n` fixed and
 varies the shape of the input, so no claim rests on a single distribution;
 Weeks 6 and 7 use worked examples and complexity summaries and omit plots
 entirely. None of Weeks 2, 3, 4, 6 and 7 leave anything behind on disk when
 they run. Week 5 Q3
 and Q4 must write a file by construction — the question itself asks for `n`
 elements stored in a file — so they delete both the generated and the sorted
 file on the way out unless `--keep` is passed.
- Where a program can check its own answer it does, and aborts on a mismatch, so
 a table that prints at all is a table from a correct run.

---

## Contributing

This is a personal coursework record, so pull requests that add solutions are not
expected. Corrections are welcome — if you spot an error in an analysis, a broken
link, or a bug in a program, please open an issue describing the problem and which
file it affects.

---

## License

Coursework, published for reference and learning. Feel free to read, run and learn
from it; please do not submit it as your own.

---

Maintained by Raghvendra Singh · B125092 · CSE-B, IIIT Bhubaneswar

Design-and-Analysis-of-Algorithms-Assignments

Owner Repos

File Explorer

# Use via CDN

Was this content helpful?

Recent Feedback

Design-and-Analysis-of-Algorithms-Assignments

Owner Repos

File Explorer

# Use via CDN

Was this content helpful?

Recent Feedback

Download README