Non-Linear-DS.md

Non-Linear DS

---

Outline

1. Balanced Binary Search Tree (Java TreeMap/TreeSet)

   1. Difference between a map and a set.
   2. Creating TreeMaps and TreeSets.
   3. Important functions and their complexity:
      • add, remove, contains, getValue
   4. Creating a comparator for an object to be the key in a TreeMap/Set.
   5. Traversing a TreeMap, TreeSet.

2. Heap (Java PriorityQueue)

   1. Creating PriorityQueues.
   2. Important functions and their complexities:
      • add, poll, peek 3.Defining a comparator.

3. Hash Table (Java HashMap/HashSet)

   1. Creating Hash/TreeMaps , Hash/TreeSets.
   2. Important functions and their complexities.
   3. HashMap/Set vs TreeMap/Set.
   4. Creating Hash functions and avoiding collisions.

---

Material Resources

Resource	Points Covered
CP section: 2.3	Most of the outline points
HE Heaps and Priority Queues	2
HE Hashing basics	3-iv
HE Heaps and Priority Queues	2

---

Problem Sets

Problem Set #1

Problem	Tags	Notes	Solution
Andy's First Dictionary	Hash/Treeset	some input parsing , sort output	Link
Add All	Priority Queues	better to add the smallest numbers first	Link
Updating a Dictionary	TreeMap	_	Link
Pangram	Hash/TreeSet	can be solved with a boolean array	Link
Argus	Priority Queue	-	Link

Problem Set #2

Problem	Tags	Notes	Solution
Hay Points	TreeMap	_	Link
I Can Guess the Data Structure	Queues,Stacks,Priority Queues	simulate the operation using the required datastructres	Link
CD	Hash/TreeSet	_	Link
Andy's Second Dictionary	TreeSet	_	Link
Conformity	TreeMap	_	Link