Course

Unit 1

Data Structures and Libraries 

• Implement and analyze sorting algorithms: Bubble, Selection, Insertion, Merge, and Quick sort. 
• Implement dynamic arrays using standard libraries and analyze resizing strategies. 
• Implement and use iterators for traversing data structures. 
• Implement Binary Tree creation and traversal (Inorder, Preorder, Postorder). 
• Implement Binary Search Tree (BST) with insertion, deletion, and search operations. 
• Implement a Trie data structure and perform word insertion, search, and prefix matching. 

Unit 2

Problem Solving Paradigms 

• Solve problems using Divide and Conquer (Binary Search, Merge Sort). 
• Implement Greedy algorithms (Activity Selection, Fractional Knapsack). 
• Implement Dynamic Programming problems:
  • Fibonacci sequence 
  • Longest Common Subsequence 
  • Matrix Chain Multiplication 
  • 0/1 Knapsack 

Unit 3

• Implement Depth First Search (DFS) and Breadth First Search (BFS) using adjacency lists. 
• Apply DFS and BFS to detect connected components and cycle detection. 
• Implement Minimum Spanning Tree using Kruskal’s Algorithm. 
• Implement Shortest Path Algorithms: 
  • Dijkstra’s Algorithm 
  • Bellman-Ford Algorithm 
  • Floyd-Warshall Algorithm 
• Implement Maximum Flow using Edmonds-Karp Algorithm. 
• Implement algorithms for special graphs (DAG shortest path, bipartite graph checking). 

Unit 4

Mathematics & String Processing 

• Implement Number Theory algorithms: GCD, LCM, prime number generation (Sieve of Eratosthenes). 
• Implement programs for factorial computation using recursion and dynamic programming. 
• Implement Combinatorics problems (nCr using DP). 
• Solve problems based on Probability theory simulations. 
• Implement Linear Algebra operations: Matrix addition, multiplication, and transpose. 
• Implement String Processing Algorithms: Pattern matching (Naive, KMP, Rabin-Karp). 

Unit 5

Computational Geometry 

• Implement Graham’s Scan Algorithm for Convex Hull computation. 
• Implement Line Segment Intersection detection algorithms. 
• Solve geometric problems involving points, orientation, and distance calculations. 

Course Description  

This course helps the students to apply familiar algorithms to solve complex problems as well as to write efficient code, which is necessary for a programmer. 

 Course Objectives 

In this course students will learn how to apply algorithms in order to solve complex problems. The goal of this course is to teach students how to apply familiar algorithms to non-intuitive problems. Along the way students will also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it‘s limited, apply basic algorithmic ideas to real problems, etc.

Course Outcomes 

CO-PO Mapping 

• Competitive Programming 3 by Felix Halim and Steven Halim.
• Guide to Competitive Programming: Learning and Improving Algorithms Through Contests by Antti Laaksonen.
• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein.
• The Algorithm Design Manual by Steven Skiena.
• Concrete Mathematics by Donald Knuth, Oren Patashnik, and Ronald Graham, 648 pages.
• Computational Geometry: Algorithms and Applications by Marc van Kreveld, Mark de Berg, and Otfried Cheong.