Algorithms

Data Structuring

Partha Pratim Das

Department of Computer Science and Engineering

Indian Institute of Technology, Kharagpur
ppd@[Link]

T10KT Coordinators’ Workshop

March 17, 2015

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 1 / 32
Where to analyse?

Algorithmic Situation
Core Idea: Identify data configurations or scenarios for analysis
Best Case
Worst Case
Average Case
Probabilistic Case
Amortized Case

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 2 / 32
 Types of analyses

Worst case. Running time guarantee for any input of size n.

Ex. Heapsort requires at most 2 n log2 n compares to sort n elements.

Probabilistic. Expected running time of a randomized algorithm.

Ex. The expected number of compares to quicksort n elements is ~ 2n ln n.

Amortized. Worst-case running time for any sequence of n operations.

Ex. Starting from an empty stack, any sequence of n push and pop
operations takes O(n) operations using a resizing array.

Average-case. Expected running time for a random input of size n.

Ex. The expected number of character compares performed by 3-way
radix quicksort on n uniformly random strings is ~ 2n ln n.

Also. Smoothed analysis, competitive analysis, ...

8

Courtesy: Algorithm Design by Jon Kleinberg & Éva Tardos

Bounds

Determination of Quality of an Algorithm

Core Idea: Understand how well we are doing, and, how and if we can do
better
Upper Bound
Bubble Sort: O(n2 ), O(n2 )
Quick Sort: O(n2 ), O(n log n)
Merge Sort: O(n log n), O(n log n)
Lower Bound
Sorting: O(n log n)
Optimal Algorithm
Merge Sort

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 4 / 32
Client, Implementation, Interface

Separate interface and implementation

Ex: stack, queue, bag, priority queue, symbol table, union-find, · · · .
Benefits
Client cannot know details of implementation ⇒ Client has many
implementation from which to choose.
Implementation cannot know details of client needs ⇒ Many clients
can re-use the same implementation.
Design: creates modular, reusable libraries.
Performance: use optimized implementation where it matters.

Client program using operations defined in interface

Implementation actual code implementing operations
Interface description of data type, basic operations

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 5 / 32
Types of Data Structures

Containers:

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 6 / 32
Types of Data Structures

Containers:
Sequence Containers – Array, List

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 6 / 32
Types of Data Structures

Containers:
Sequence Containers – Array, List
Associative Containers – Map

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 6 / 32
Types of Data Structures

Containers:
Sequence Containers – Array, List
Associative Containers – Map
Container Adaptors – Stack, Queue

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 6 / 32
Types of Data Structures

Containers:
Sequence Containers – Array, List
Associative Containers – Map
Container Adaptors – Stack, Queue
Memorizers & Special:

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 6 / 32
Types of Data Structures

Containers:
Sequence Containers – Array, List
Associative Containers – Map
Container Adaptors – Stack, Queue
Memorizers & Special:
Networks – Graph

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 6 / 32
Types of Data Structures

Containers:
Sequence Containers – Array, List
Associative Containers – Map
Container Adaptors – Stack, Queue
Memorizers & Special:
Networks – Graph
Threads

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 6 / 32
Types of Data Structures

Containers:

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 7 / 32
Types of Data Structures

Containers:
Language Supported – Uses machine primitives: Array, List

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 7 / 32
Types of Data Structures

Containers:
Language Supported – Uses machine primitives: Array, List
Language Library Supported – Uses language primitives & system
support: Vector

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 7 / 32
Types of Data Structures

Containers:
Language Supported – Uses machine primitives: Array, List
Language Library Supported – Uses language primitives & system
support: Vector
Memorizers & Special:

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 7 / 32
Types of Data Structures

Containers:
Language Supported – Uses machine primitives: Array, List
Language Library Supported – Uses language primitives & system
support: Vector
Memorizers & Special:
Third-party Library Supported – Graph, pthreads

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 7 / 32
Types of Data Structures

Containers:
Language Supported – Uses machine primitives: Array, List
Language Library Supported – Uses language primitives & system
support: Vector
Memorizers & Special:
Third-party Library Supported – Graph, pthreads
Co-designed with Algorithms

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 7 / 32
Data Structure Design

1 Interface Design (Use Model)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

2 Implementation Design (Deployment Model)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

Necessary Interfaces

2 Implementation Design (Deployment Model)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

Necessary Interfaces
Auxiliary Interfaces

2 Implementation Design (Deployment Model)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

Necessary Interfaces
Auxiliary Interfaces
Implementation Interfaces
2 Implementation Design (Deployment Model)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

Necessary Interfaces
Auxiliary Interfaces
Implementation Interfaces
2 Implementation Design (Deployment Model)
Specification of Data

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

Necessary Interfaces
Auxiliary Interfaces
Implementation Interfaces
2 Implementation Design (Deployment Model)
Specification of Data
Specification of Costs (O(1), O(log n), O(n), ...; Worst Case, Average
Case, Amortised, ...)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

Necessary Interfaces
Auxiliary Interfaces
Implementation Interfaces
2 Implementation Design (Deployment Model)
Specification of Data
Specification of Costs (O(1), O(log n), O(n), ...; Worst Case, Average
Case, Amortised, ...)
Choice of Container(s) (Array, List, Deque, ...)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

Necessary Interfaces
Auxiliary Interfaces
Implementation Interfaces
2 Implementation Design (Deployment Model)
Specification of Data
Specification of Costs (O(1), O(log n), O(n), ...; Worst Case, Average
Case, Amortised, ...)
Choice of Container(s) (Array, List, Deque, ...)
Design of Algorithms

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Data Structure Design

1 Interface Design (Use Model)

Necessary Interfaces
Auxiliary Interfaces
Implementation Interfaces
2 Implementation Design (Deployment Model)
Specification of Data
Specification of Costs (O(1), O(log n), O(n), ...; Worst Case, Average
Case, Amortised, ...)
Choice of Container(s) (Array, List, Deque, ...)
Design of Algorithms
Error Behaviour

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 8 / 32
Stack Design

Interface Design (Use Model = LIFO)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 9 / 32
Stack Design

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty
void push(String&)
String pop()
bool empty()
create()
destroy()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 9 / 32
Stack Design

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty
void push(String&)
String pop()
bool empty()
create()
destroy()
Auxiliary Interfaces: top, size
String& top()
size t size()
Iterator Interfaces:
first() or begin()
next() or ++()
isdone() or end()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 9 / 32
Stack Design

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty
void push(String&)
String pop()
bool empty()
create()
destroy()
Auxiliary Interfaces: top, size
String& top()
size t size()
Iterator Interfaces:
first() or begin()
next() or ++()
isdone() or end()
Implementation Interfaces: full
bool full()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 9 / 32
Stack Design

Implementation Design (Deployment Model = C++)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 10 / 32
Stack Design

Implementation Design (Deployment Model = C++)

Specification of Data
Problem Data: Container of items
Support Data: Top marker

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 10 / 32
Stack Design

Implementation Design (Deployment Model = C++)

Specification of Data
Problem Data: Container of items
Support Data: Top marker
void push(String&) O(1) Amortised
Specification of Costs String pop() O(1) Amortised
bool empty() O(1) Worst Case

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 10 / 32
Stack Design

Implementation Design (Deployment Model = C++)

Specification of Data
Problem Data: Container of items
Support Data: Top marker
void push(String&) O(1) Amortised
Specification of Costs String pop() O(1) Amortised
bool empty() O(1) Worst Case
Choice of Container(s)
list (language-defined container: when pointer is supported)
array (language-defined container: where random access is supported)
deque / vector / list (library-defined container)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 10 / 32
Stack Design

Implementation Design (Deployment Model = C++)

Specification of Data
Problem Data: Container of items
Support Data: Top marker
void push(String&) O(1) Amortised
Specification of Costs String pop() O(1) Amortised
bool empty() O(1) Worst Case
Choice of Container(s)
list (language-defined container: when pointer is supported)
array (language-defined container: where random access is supported)
deque / vector / list (library-defined container)
Design of Algorithms – Depends on
Interfaces
Container
Primitives
Complexity

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 10 / 32
Stack Design

Implementation Design (Deployment Model = C++)

Specification of Data
Problem Data: Container of items
Support Data: Top marker
void push(String&) O(1) Amortised
Specification of Costs String pop() O(1) Amortised
bool empty() O(1) Worst Case
Choice of Container(s)
list (language-defined container: when pointer is supported)
array (language-defined container: where random access is supported)
deque / vector / list (library-defined container)
Design of Algorithms – Depends on
Interfaces
Container
Primitives
Complexity
Error Behaviour
What if memory runs out during push
What if destructor in pop throws
Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 10 / 32
Stack Implementation: Using List

Container = Singly Linked List

push and pop at front
Defect:
Time to create/destroy Node
Time to deference link
Space for link

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 11 / 32
Stack Implementation: Using Array

Container = Array
push and pop at back
Defect:
Stack overflows when capacity of array is exceeded

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 12 / 32
Stack Implementation: Using Array: Issues

Overflow and underflow

Underflow: throw exception if pop from an empty stack
Overflow: use resizing array for array implementation

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 13 / 32
Stack Implementation: Using Array: Issues

Overflow and underflow

Underflow: throw exception if pop from an empty stack
Overflow: use resizing array for array implementation
Null items. We allow null items to be inserted.

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 13 / 32
Stack Implementation: Using Array: Issues

Overflow and underflow

Underflow: throw exception if pop from an empty stack
Overflow: use resizing array for array implementation
Null items. We allow null items to be inserted.
Loitering. Holding a reference to an object when it is no longer
needed

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 13 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): increase size of array s[] by 1
pop(): decrease size of array s[] by 1

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 14 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): increase size of array s[] by 1
pop(): decrease size of array s[] by 1
Too expensive
Need to copy all items to a new array, for each operation.
Array accesses to insert first N items =
N + (2 + 4 + · · · + 2(N − 1)) ˜N 2 .

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 14 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): increase size of array s[] by 1
pop(): decrease size of array s[] by 1
Too expensive
Need to copy all items to a new array, for each operation.
Array accesses to insert first N items =
N + (2 + 4 + · · · + 2(N − 1)) ˜N 2 .
Challenge. Ensure that array resizing happens infrequently.

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 14 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): double size of array s[] when array is full
pop(): halve size of array s[] when array is one-half full

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 15 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): double size of array s[] when array is full
pop(): halve size of array s[] when array is one-half full
Too expensive in worst case
Consider push-pop-push-pop- sequence when array is full
Each operation takes time proportional to N

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 15 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): double size of array s[] when array is full
pop(): halve size of array s[] when array is one-half full
Too expensive in worst case
Consider push-pop-push-pop- sequence when array is full
Each operation takes time proportional to N
Remedy. Introduce hysteresis

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 15 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): double size of array s[] when array is full
pop(): halve size of array s[] when array is one-quarter full

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 16 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): double size of array s[] when array is full
pop(): halve size of array s[] when array is one-quarter full
Invariant. Array is between 25% and 100% full.

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 16 / 32
Stack Implementation: Using Array: Resizing Array

How to grow and shrink array?

push(): double size of array s[] when array is full
pop(): halve size of array s[] when array is one-quarter full
Invariant. Array is between 25% and 100% full.
Amortised costs of push and pop both are O(1).

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 16 / 32
Stack Implementation: Using Array: Resizing Array

Costs:
Best Worst Amortised
create 1 1 1
push 1 N 1
pop 1 N 1
size 1 1 1

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 17 / 32
Stack Design: Interface Review

Interface Design (Use Model = LIFO)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 18 / 32
Stack Design: Interface Review

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty
void push(String&)
String pop()
bool empty()
create()
destroy()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 18 / 32
Stack Design: Interface Review

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty
void push(String&)
String pop()
bool empty()
create()
destroy()
Auxiliary Interfaces: top, size
String& top()
size t size()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 18 / 32
Stack Design: Interface Review

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty
void push(String&)
String pop()
bool empty()
create()
destroy()
Auxiliary Interfaces: top, size
String& top()
size t size()
Implementation Interfaces: full
bool full()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 18 / 32
Stack Design: Interface Review: pop()

String Stack::pop() {
return data_[top_--]; // Memory leaks when
// the next push is done
}

String Stack::pop() {
String s = data_[top_];
data_[top_--].~String(); // What if the
// destructor throws?
return s;
}

Issue: pop() performs two responsibilities – return top-most object and

remove from stack
Prefer: One Method One Responsibilities
Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 19 / 32
Stack Design: Interface Review

Interface Design (Use Model = LIFO)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 20 / 32
Stack Design: Interface Review

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty, top
void push(String&)
void pop()
bool empty()
String& top()
create()
destroy()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 20 / 32
Stack Design: Interface Review

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty, top
void push(String&)
void pop()
bool empty()
String& top()
create()
destroy()
Auxiliary Interfaces: size
size t size()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 20 / 32
Stack Design: Interface Review

Interface Design (Use Model = LIFO)

Necessary Interfaces: push, pop, empty, top
void push(String&)
void pop()
bool empty()
String& top()
create()
destroy()
Auxiliary Interfaces: size
size t size()
Implementation Interfaces: full
bool full()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 20 / 32
Stack Applications

Parsing in a compiler.
Java virtual machine.
Undo in a word processor.
Back button in a Web browser.
PostScript language for printers.
Implementing function calls in a compiler.

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 21 / 32
Stack Interface across Languages
C++ Java Python
stack() Stack() stack = []
void push(const value type&) Object push(Object element) append(item)
void pop() Object pop( ) pop()
value type& top() Object peek( ) stack[0]
bool empty() const boolean empty() isEmpty()
size t size() const len(<list>)
Underlying Container / Implementation
vector, list, deque list

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 22 / 32
Queue Design

Interface Design (Use Model = FIFO)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 23 / 32
Queue Design

Interface Design (Use Model = FIFO)

Necessary Interfaces: addq, delq, empty, front
void addq(String&)
void delq()
bool empty()
String& front()
create()
destroy()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 23 / 32
Queue Design

Interface Design (Use Model = FIFO)

Necessary Interfaces: addq, delq, empty, front
void addq(String&)
void delq()
bool empty()
String& front()
create()
destroy()
Auxiliary Interfaces: size
size t size()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 23 / 32
Queue Design

Interface Design (Use Model = FIFO)

Necessary Interfaces: addq, delq, empty, front
void addq(String&)
void delq()
bool empty()
String& front()
create()
destroy()
Auxiliary Interfaces: size
size t size()
Implementation Interfaces: full
bool full()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 23 / 32
Queue Design

Implementation Design (Deployment Model = C++)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 24 / 32
Queue Design

Implementation Design (Deployment Model = C++)

Specification of Costs
void addq(String&) O(1) Amortised
String delq() O(1) Amortised
bool empty() O(1) Worst Case
String& front() O(1) Worst Case

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 24 / 32
Queue Design

Implementation Design (Deployment Model = C++)

Specification of Costs
void addq(String&) O(1) Amortised
String delq() O(1) Amortised
bool empty() O(1) Worst Case
String& front() O(1) Worst Case
Choice of Container(s)
list (add / delete at two ends)
array (Circular - how to resize)

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 24 / 32
Queue Design

Implementation Design (Deployment Model = C++)

Specification of Costs
void addq(String&) O(1) Amortised
String delq() O(1) Amortised
bool empty() O(1) Worst Case
String& front() O(1) Worst Case
Choice of Container(s)
list (add / delete at two ends)
array (Circular - how to resize)
Design of Algorithms – Depends on
Interfaces
Container
Primitives
Complexity

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 24 / 32
Queue Design

Implementation Design (Deployment Model = C++)

Specification of Costs
void addq(String&) O(1) Amortised
String delq() O(1) Amortised
bool empty() O(1) Worst Case
String& front() O(1) Worst Case
Choice of Container(s)
list (add / delete at two ends)
array (Circular - how to resize)
Design of Algorithms – Depends on
Interfaces
Container
Primitives
Complexity
Error Behaviour
What is memory runs out during addq
What if destructor in delq throws

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 24 / 32
Language-specific Data Structure
Language Data Structures Remarks
C array, linked list User-defined
using language
primitives
Sequence vector, deque, list
Containers
Container queue, priority queue, stack
C++ STL
Adapters
Associative set, multiset, map, multimap
Containers
Java Vector, Stack, Dictionary / Hashtable Utilities
Python list [], tuple (), range, set {}, dictionary {:} Built-in

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 25 / 32
Container Iterators

Iterator Interface:

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 26 / 32
Container Iterators

Iterator Interface:
first() or begin()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 26 / 32
Container Iterators

Iterator Interface:
first() or begin()
next() or operator++()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 26 / 32
Container Iterators

Iterator Interface:
first() or begin()
next() or operator++()
isdone() or end()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 26 / 32
Container Iterators

Iterator Interface:
first() or begin()
next() or operator++()
isdone() or end()
item() or operator*()

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 26 / 32
Container Iterators

Iterator Interface:
first() or begin()
next() or operator++()
isdone() or end()
item() or operator*()
Iterator example:
#include <iostream>
#include <list>
using namespace std;

int main () {
int myints[] = {75,23,65,42,13};
list<int> mylist (myints,myints+5);

cout << "mylist contains:";

for(list<int>::iterator it = [Link](); it != [Link](); ++it)
cout << ’ ’ << *it;

cout << ’\n’;

return 0;
}
Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 26 / 32
Search Data Structure

Operations:
insert: List good, Array bad
delete: List good, Array bad
find: Array good, List bad

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 27 / 32
Search Data Structure

Operations:
insert: List good, Array bad
delete: List good, Array bad
find: Array good, List bad
Use BST – Needs balancing:
Guaranteed Bound: AVL, 2-3-4 Tree, Red-Black Tree, B+-Tree
Probabilistic Bound: Randomized BST, Skip List
Amortised Bound: Splay

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 27 / 32
Search Data Structure

Operations:
insert: List good, Array bad
delete: List good, Array bad
find: Array good, List bad
Use BST – Needs balancing:
Guaranteed Bound: AVL, 2-3-4 Tree, Red-Black Tree, B+-Tree
Probabilistic Bound: Randomized BST, Skip List
Amortised Bound: Splay
Applications:
Associative containers like set, map
Indexing

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 27 / 32
Problem

Elementary, Dr. Watson!

Use stacks to implement a queue. Analyse its performance.

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 28 / 32
Problem

Doctor’s Appointment List

Patients come to see the doctor by appointment. The appointments are
decided by the arrival time (in the order). However, patients with
emergency needs will be treated ahead of the regular appointments.
Design the Interface
Propose an implementation

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 29 / 32
Problem

Tournament Sorting
Consider the interface:
Build-Tournament-Tree: The first step in which by equal splits, we
build up the balanced comparison tree [O(n)]
Remove Max: The maximum element at the root is removed and
replaced by -1 [O(log n)]
Re Build Tree: Re-build the tournament tree properly after deletion
of maximum [O(log n)]
Build a data structure.

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 30 / 32
Problem

Arrangement of Points
You are given a planar geometric structure comprising vertices, edges
connecting vertices, and faces bounded by edges. The expected operations
are:
Walk around the boundary of a given face in CCW order
Access a face from an adjacent one
Visit all the edges around a given vertex

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 31 / 32
Problem

Searching Points in a Plane

You are given a set of points on a plane. The expected operations are:
Insert: Add a new point
Delete: Remove an existing point
Nearest Neighbour Search: Find the point that is nearest to a given
input point
Find points within the rectangle given by [Xlow · · · Xhigh ] ×
[Ylow · · · Yhigh ]

Partha Pratim Das (IIT, Kharagpur) Data Structuring March 17, 2015 32 / 32