Data Structures

Data Structures
CS203 at IITG by R. Inkulu

Asymptotic notation [CLRS]: 43-52
Intro to algorithm design [CLRS]: 5-14, 23-25, 27-29; [more]
Elementary data structures [CLRS]: 232-240, 246-248; [note]
More analysis techniques
- Average-case analysis [CLRS]: 114-116, 120-121; [more]
- More on probabilistic analysis [CLRS]: 139-141
- Expected analysis [CLRS]: 122-124
- Permuting uniformly at random [CLRS]: 126-128
- Analyzing a Monte Carlo algorithm [KT]: 708-713
Sorting
- Bubble, Selection [wiki]: 1, 2
- Insertion, Shell [CLRS]: 16-22; [wiki]: 1, 2
- Bucket [CLRS]: 200-202; [more]
- Quick, Merge [CLRS]: 170-176, 29-37
- Heapsort [CLRS]: 159-161
- Lower bounding with decision trees [CLRS]: 191-193
- Counting, Radix [CLRS]: 194-196, 197-199
- Avg-case time: Insertion, Bucket [note]; [CLRS]: 202-204
- Expected time: Randomized quick [CLRS]: 179, 181-184
Selection
- Minimum and Maximum [CLRS]: 213-215
- Blum et al.,'s algorithm [CLRS]: 220-222
- Lower bounding with adversary arguments [note]
- Range minimum queries [note]
- Hoare's Las Vegas algorithm [CLRS]: 215-219
- A Monte Carlo algorithm [MU]: 47, 51-52, 57-62
- In dynamic sets with a BST a variant of [CLRS]: 339-347
A few reductions for lower bounding [note]
Amortized analysis
- Three methods with two examples [CLRS]: 451-461
- Dynamic arrays [CLRS]: 463-469
Heaps
- Binary [CLRS]: 151-159, 162-165, exer 6.1-2, 6.1-7, 6.3-3
- Leftist [note]
- Fibonacci [CLRS]: 505-526
Dictionaries: search trees
- Binary search tree [CLRS]: 286-299, exer 12.2-6
- AVL tree [note]
- 2-4 tree and its generalization [CLRS]: 488-502
- Red-black tree [CLRS]: 308-329; [24vsRB]
- Splay tree [note]
- Tries [note]
More on suffix arrays [wiki]: 1, 2 --- not covered this time
Randomized dictionaries
- Randomly built BST [CLRS]: 299-303; [Jensen's ineq]
- Random treap [note]
- Skip list [note]
Hashing based dictionaries
- Separate chaining [CLRS]: 253-260, 263
- 2-Universal hashing [CLRS]: 265, 267-268
- Static perfect hashing [CLRS]: 277-282
- Open addressing [CLRS]: 269-271, 274-276
- Bloom filter for set membership [note] --- AR
For disjoint-sets
- Two representations [CLRS]: 561-562, 564-571
- Analysis of disjoint-set forest [note]
- Link-cut trees [SleaTarj]: 2-10 --- not covered this time
For graphs
- Three representations [CLRS]: 589-592+, 562-564
- Breadth-first traversal [CLRS]: 594-601
- Depth-first traversal [CLRS]: 603-610

This is a core course for second-year undergrads. It introduces design and analysis of data structures. After reviewing asymptotic notation and elementary data structures (array, stack, queue, linked list, rooted tree), the course details the following: various analysis measures, sorting, selection, lower bounds on the worst-case performance, balancing search trees, randomized dictionaries, priority queues, hashing, dictionaries for strings, data structures for disjoint-sets, and graph traversals.

Texts:
Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Third Edition. [CLRS]
[For those (sub)topics covered in lectures but not detailed in the above textbook, links/notes are posted on this page.]

Prereqs: Elementary combinatorics, discrete probability, proof techniques, (dis)proving propositions, and CS101.

Lectures are held in 5102, in Slot D: Mon 11-11:55, Th 9-9:55, and Fri 10-10:55 am.
The academic calendar is here.

Teaching Assistants: k.abhik@, c.himanshu@, d.mayukh@, v.subramanian@.
The set of guidelines for TAs is here.

The grading is relative, and it is based on the total marks obtained in the following:

exam1	14 points	10 am to 11:30 am on 19th Aug (Sat) in L3
mid-sem	18	2 hours; refer to institute time table
exam3	15	6 pm to 7:30pm on 20th Oct (Fri) in L2
end-sem	25	3 hours; refer to institute time table
surprise (4 to 6)	3*(≥4)	15 minutes each; not scheduled beforehand
homework	0	one/two problems posted after every lecture
class participation	4	-

Attendance at each lecture, out of 125 registrants, is here.

Guidelines Fall '23