Data structure with competitive coding

Course Code (Credit):

CUCS1002(2+4+0)

Course Objectives:

  • To train students in algorithm analysis, recursion, and selecting suitable data structures for problem-solving, focusing on algorithm correctness.
  • To implement dynamic data structures (linked lists, binary trees) and sub-quadratic sorting algorithms (quick sort, merge sort, heap sort) to solve data structure problems.
  • To able to get jobs in different IT firms as a developer with core and competitive coding skills.

Course Outcomes:

  • CO1: Recall and relate algorithmic techniques and recursive methods to efficiently solve complex problems, demonstrating proficiency in analyzing and validating algorithm correctness.
  • CO2: Describe and discuss dynamic data structures, optimizing data manipulation and storage solutions.
  • CO3: Apply and demonstrate sorting and searching algorithms, achieving sub-quadratic performance in data processing tasks.
  • CO4: Analyse and test coding problems using advanced data structures and algorithms under timed conditions.
  • CO5: Formulate strategies and show readiness for software development roles by enhancing coding skills and practical data structure knowledge.

Course Syllabus:

Module I: Data Structures Basics (10 hours)
Theory
  • Definition, Importance, Algorithm, and Pseudocode
  • Types of Data Structures, Abstract Data Types (ADTs)
  • Complexity Analysis & Asymptotic Notations
Module II: Arrays and Linked Lists (20 hours)
Theory
  • Array Operations
  • Linked Lists: Singly, Doubly, Circular
  • Operations on Linked Lists: Insert, Delete, Search, Sort, Reverse, Merge
Practice Experiment
  • Experiment 2.1: Write a program to demonstrate the use of arrays.
  • Experiment 2.2: Experiment 2.2: Implement a program to perform insertion and deletion operations on an array.
  • Experiment 2.3: Develop a program to implement a singly linked list.
  • Experiment 2.4: Write a program to perform insertion and deletion operations on a singly linked list.
  • Experiment 2.5: Implement a program to implement a doubly linked list.
  • Experiment 2.6: Develop a program to perform insertion and deletion operations on a doubly linked list.
  • Experiment 2.7: Write a program to implement a circular linked list.
  • Experiment 2.8: Implement a program to perform insertion and deletion operations on a circular linked list.
  • Experiment 2.9: Develop a program to reverse a linked list.
  • Experiment 2.10: Write a program to merge two sorted linked lists.
Module III: Stacks and Queues (20 hours)
Theory
  • Stack Operations and Applications
  • Queue Operations and Applications
  • Variants: Circular Queue, Priority Queue, Deque
Practice Experiment
  • Experiment 3.1: Write a program to implement a stack using an array.
  • Experiment 3.2: Implement a program to perform push and pop operations on a stack.
  • Experiment 3.3: Develop a program to implement a queue using an array.
  • Experiment 3.4: Write a program to perform enqueue and dequeue operations on a queue.
  • Experiment 3.5: Implement a program to implement a circular queue.
  • Experiment 3.6: Develop a program to perform insertion and deletion operations on a circular queue.
  • Experiment 3.7: Write a program to implement a priority queue.
  • Experiment 3.8: Implement a program to perform insertion and deletion operations on a priority queue.
Module IV: Trees (30 hours)
Theory
  • Binary Trees: Traversals, Insertion, Deletion
  • Binary Search Trees (BST)
  • Balanced Trees: AVL, Red-Black Trees
Practice Experiment
  • Experiment 4.1: Write a program to implement a binary tree.
  • Experiment 4.2: Implement a program to perform inorder, preorder, and postorder traversal on a binary tree.
  • Experiment 4.3: Develop a program to implement a binary search tree (BST).
  • Experiment 4.4: Write a program to perform insertion and deletion operations on a BST.
  • Experiment 4.5: Implement a program to find the height of a binary tree.
  • Experiment 4.6: Develop a program to implement an AVL tree.
  • Experiment 4.7: Write a program to perform insertion and deletion operations on an AVL tree.
  • Experiment 4.8: Implement a program to implement a red-black tree.
Module V: Graphs (20 hours)
Theory
  • Representation of Graphs
  • Graph Traversal Algorithms: BFS, DFS
  • Shortest Path Algorithms: Dijkstra, Floyd-Warshall
Practice Experiment
  • Experiment 5.1: Write a program to represent a graph using adjacency matrix.
  • Experiment 5.2: Implement a program to represent a graph using adjacency list.
  • Experiment 5.3: Develop a program to perform BFS traversal on a graph.
  • Experiment 5.4: Write a program to perform DFS traversal on a graph.
  • Experiment 5.5: Implement a program to find the shortest path in a graph using Dijkstra's algorithm.
  • Experiment 5.6: Develop a program to find the shortest path in a graph using Floyd-Warshall algorithm.
  • Experiment 5.7: Write a program to find the minimum spanning tree in a graph using Kruskal's algorithm.
  • Experiment 5.8: Implement a program to find the minimum spanning tree in a graph using Prim's algorithm.
Module VI: Hashing and Heaps (20 hours)
Theory
  • Hash Tables: Hash Functions, Collision Handling
  • Heaps: Min-Heap, Max-Heap, Operations
Practice Experiment
  • Experiment 6.1: Write a program to implement a hash table.
  • Experiment 6.2: Implement a program to handle collisions using chaining.
  • Experiment 6.3: Develop a program to handle collisions using open addressing.
  • Experiment 6.4: Write a program to implement a min-heap.
  • Experiment 6.5: Implement a program to perform insertion and deletion operations on a minheap
  • Experiment 6.6: Develop a program to implement a max-heap.
  • Experiment 6.7: Write a program to perform insertion and deletion operations on a max-heap.
  • Experiment 6.8: Implement a program to heap sort an array.
Module VII: Sorting and Searching (20 hours)
Theory
  • Linear Search, Binary Search
  • Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Radix Sort
Practice Experiment
  • Experiment 7.1: Write a program to implement linear search.
  • Experiment 7.2: Implement a program to implement binary search.
  • Experiment 7.3: Develop a program to implement bubble sort.
  • Experiment 7.4: Write a program to implement selection sort.
  • Experiment 7.5: Implement a program to implement insertion sort.
  • Experiment 7.6: Develop a program to implement quick sort.
  • Experiment 7.7: Write a program to implement merge sort.
  • Experiment 7.8: Implement a program to implement heap sort.