- Rahul Nalawade (Fall 2018)
Collection of all the projects in Implementation of Data Structures and Algorithms course.
- Implementation of data structures (Lists, Stacks, Queues, Trees, Balanced Search Trees, Hashing, Graphs);
- 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)
| 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. |
| 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. |
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent