Skip to content

Latest commit

 

History

History
49 lines (37 loc) · 6.72 KB

README.md

File metadata and controls

49 lines (37 loc) · 6.72 KB
Raw

Implementation of Data Structures and Algorithms

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.