Implementation of Data Structures and Algorithms

• Rahul Nalawade (Fall 2018)

Collection of all the projects in Implementation of Data Structures and Algorithms course.

Topics:

1. Implementation of data structures (Lists, Stacks, Queues, Trees, Balanced Search Trees, Hashing, Graphs);
2. Implementation of algorithms (Sorting and searching, Recursion, Graph algorithms).

Emphasizing on practical approach to algorithms with many programming projects of types:

• Long: Implementation of data structures and algorithms (total 5). Teams of 3-4.
• Short: Empirical studies, Do-and-learn projects. One project (almost) every week. Teams of 2 or individual.
• Optional*: Individual (no collaboration).

Following is the detailed list of each project: (please feel free to check-out the links)

A. Long Projects:

Title	End_Date	Description
LP1: Integer Arithmetic with Arbitrarily Large Numbers	Sept 23, 2018	Array-based implementation of Calculator of very large integers with the length of the numbers as large as 2,147,483,647 (2^31 - 1), with Postfix and Infix evaluation of Arithmetic Expressions.
LP2: Skip List Implementation	Oct 14, 2018	Skip Lists: A generalization of sorted linked lists for implementing Dictionary ADT (insert, delete, find, min, floor, ceiling) in O(log n) expected time per operation. And competing with balanced search trees like AVL, Red-Black, and B-Trees.
LP3: Multidimensional Search(MDS) Implementation	Nov 04, 2018	Implementation of MDS for a website seller (like Amazon), having thousands of Products (each with its own ID, Price, Description). Organizing data into a TreeMap (Red-Black Tree), used HashMap, and HashSet to achieve insertion, deletion, search, modification efficiently.
LP4: PERT, Enumeration of Topological Orders	Nov 25, 2018	Enumeration of all Permutations (Recursion, Single Swap, and in Lexicographic Order), and Combinations. Enumeration of all Topological Orderings on a Directed Graph. Enumeration of all Paths in a connected Graph. Evaluates Critical Path using PERT Algorithm.
LP5: Minimum Spanning Tree Algorithms	Dec 09, 2018	Implementation of MST Algorithms - 1. Prim's Algorithm {with 3 versions: PriorityQueue(Edge), PriorityQueue(Vertex), and IndexedBinaryHeap(Vertex)}; 2. Kruskal's Algorithm on Connected Graphs.

B. Short Projects:

Title	End_Date	Data_Structure/ Algorithm	Description
SP01: Linked Lists	Aug 23, 2018	Linked Lists	Doubly Linked List Implementation using Singly Linked List with best Object Oriented practices.
SP02: Lists Stacks and Queue	Aug 30, 2018	Bounded Queue	Bounded Queue Implementation using arrays.
SP03: Priority Queue	Sept 23, 2018	Priority Queue	Implementation of Priority Queue (Binary Heap) using arrays.
SP04: Binary Search Tree	Sept 30, 2018	Binary Search Tree, TreeMap, TreeSet	Implementation of Binary Search Tree, with Bounded-size Stack, BST Map (like a TreeMap) on top of BST class, and solution to the 3 problems using TreeMap/ TreeSet.
SP05: Balanced Binary Search Trees	Optional*	AVL Tree, Red Black Tree, Splay Tree	Implementation of Balanced Binary Search Trees - AVLTree, RedBlackTree, SplayTree as an extension from BST Implementation.
SP06: Applications of Hashing	Jan 08, 2019	HashMap, HashSet	3 Problems from SP04 to be solved using HashMap/ HashSet instead of TreeMap/ TreeSet.
SP07: Comparison of Hashing Implementations	Oct 21, 2018	Hashing Algorithms (Arrays)	Comparison of Hashing Algorithms - Double Hashing, Robin Hood Hashing Cuckoo Hashing with Java's inbuilt HashMap/ HastSet over millions of add(), contains() and remove() operations.
SP08: Depth First Search	Oct 28, 2018	Graph, DFS, Topological Ordering	Implementation of Depth First Search algorithm for a Directed Acyclic Graph, Connected Components and Topological Orderings.
SP09: Divide and Conquer	Nov 04, 2018	Merge Sort, Insertion Sort	Implementation of divide and conquer algorithm to sort an array of integers - Merge Sort (take1, take2, take3), and O(n) vs O(log n) algorithms for Fibonacci Term using BigInteger Java library, and their comparison.
SP10: DFS and Divide and Conquer	Nov 11, 2018	DFS (Strongly Connected Components); Dual Pivot Quick Sort	Implementation of DFS - Strongly Connected Components on a Directed Graph, using same Object Oriented approach from SP08. Implementation of two versions of partition algorithms of Quick Sort and their comparison. Implementation of Dual-Pivot Quick Sort Algorithm.
SP11: K Largest Elements and Enumeration	Nov 18, 2018	K Largest (Quick Select, Priority Queue); and Enumeration	Implementation of O(n) Select Algorithm to find K largest elements and compare it's performance with an Algorithm to find K largest elements using Priority Queue. Implementation of Enumeration algorithms - permutations(), combinations(), heap(), and Knuth's Algorithm L.
SP12: Breadth-First-Search and Enumeration	Nov 25, 2018	Graph, BFS	Implementation of an Algorithm to find Diameter of a Tree (represented as a Graph) using BFS, to find Odd-Length Cycle in a Tree. Implementation of Enumeration of all Paths in a connected Graph, and Enumeration of all permutation with alternate parities.
SP13: String Algorithms	Optional*	String Algorithms	Implementation of String Algorithms - Trie, KMP Algorithm, Boyer-Moore Algorithm, and Automata Matcher.