CSE2305 Problem Solving using Competitive Programming PDF

Sir Padampat Singhania University, Udaipur B. Tech in Detailed Syllabus Semester – III Course Category CSE2305...

Sir Padampat Singhania University, Udaipur B. Tech in Detailed Syllabus Semester – III Course Category CSE2305 L T P C Problem Solving using Competitive Programming 2 0 2 4 Pre-requisites: Data Structures and Basic Mathematical Concepts Course Objective/s:  Introduce students to the fundamentals of competitive programming and develop their problem-solving skills. This includes teaching strategies for breaking down problems and designing efficient algorithms.  Familiarize students with various data structures and their applications in problem- solving. Introduce common sorting and searching algorithms and their implementations. Provide an understanding of advanced data structures such as trees, heaps, and graphs.  Introduce advanced problem-solving techniques such as dynamic programming and greedy algorithms. Develop skills in solving contest-style coding problems efficiently. Enhance students' ability to analyze and solve problems using various techniques. Course Outcomes Course Outcome Level* Explain the principles, operations, and applications of various data 1 CO1 structures and algorithms, including arrays, strings, linked lists, stacks, queues, trees, graphs, heaps and tries. Apply problem-solving strategies to solve a variety of 2 CO2 programming problems Analyze problem requirements and select appropriate data 3 CO3 structures and algorithms to efficiently solve problems. Evaluate the efficiency and effectiveness of different algorithms 4 CO4 and data structures based on their time complexity, space complexity, and problem-specific requirements. Synthesize and create algorithms and code solutions for complex 5 CO5 programming problems, demonstrating proficiency in algorithm design and implementation. *Level of Learning- Use the number from 1 to 5 for indicating the level. Level 1- Remember & Understand, Level 2- Apply, Level 3- Analyse, Level 4- Evaluate, Level 5- Create. Mention the highest level that will be attained in the particular Course Outcome. Course Contents: Module I: Introduction to Competitive Programming and Time Complexity Analysis, Arrays and Strings. Introduction to Competitive Programming: Overview of competitive programming, Importance and benefits of competitive programming, How to approach problem-solving in competitive programming. SPSU/Syllabus Format 2023 Page 1 of 4 Basics of Algorithm Analysis: Introduction to time and space complexity, Big O notation and its significance, Analysing time complexity of simple algorithms (e.g., loops, recursion) Arrays: Basic operations and manipulations, Solving problems involving arrays Strings: String manipulation techniques, Pattern matching algorithms Module II: Mathematical Principles for Competitive Programming and Recursion Number theory Concepts: Sieve Method, Euclid’s Algorithm, Modular Arithmetic, Combinatorics. Recursion and problems based on recursion. Module III: Linked List Linked Lists: Singly linked lists and its operations, Doubly linked lists and its operations, Applications and problem-solving using linked lists Module IV: Stacks and Queues Stacks and Queues: Implementing stacks and queues using arrays and linked lists, solving problems using stacks and queues. Module V: Trees and Graphs Trees: Binary Trees and Binary Search Trees (BST), Tree traversals (pre-order, in-order, post-order), Common tree algorithms and their applications Graphs: Graph representation (adjacency list, adjacency matrix), Graph traversals (BFS and DFS) Module VI: Heaps and Tries Heaps: Introduction to heap data structure, Heap operations and priority queues, Applications of heaps in competitive programming Tries: Structure and implementation of trie, solving problems involving tries. List of Laboratory Experiments: Lab No. Name of the Experiment 1 Introduction to Competitive Programming: Understanding Input, Output and Constraints. Problem Solving using Arrays: https://www.codingninjas.com/studio/problems/reverse-the-array_1262298 https://www.codingninjas.com/studio/problems/pair-sum_697295 https://www.codingninjas.com/studio/problems/find-duplicate-in- array_1112602 https://www.codingninjas.com/studio/problems/rotate-array_1230543 https://www.codingninjas.com/studio/problems/maximum-subarray- sum_630526 SPSU/Syllabus Format 2023 Page 2 of 4  https://www.codingninjas.com/studio/problems/pascal-s-triangle_1089580 https://www.codingninjas.com/studio/problems/spiral-matrix_840698 2 Problem Solving using Strings: https://www.codingninjas.com/studio/problems/check-if-the-string-is-a- palindrome_1062633 https://www.codingninjas.com/studio/problems/reverse-words_696444 https://www.codingninjas.com/studio/problems/subsequences-of- string_985087 https://www.codingninjas.com/studio/problems/remove-consecutive- duplicates_893195 https://www.codingninjas.com/studio/problems/compress-the-string_526 3 Problem Solving using Mathematical Principles for Competitive Programming: Program to implement Prime Number and Factorization using Sieve Method. Program to implement Euclid’ Algorithm and compute GCD. Program to compute Modular Arithmetic. Birthday Paradox Problem 4 Problem Solving using Recursion: https://leetcode.com/problems/power-of-two/ https://leetcode.com/problems/fibonacci-number/ https://www.codingninjas.com/studio/problems/binary-search_972 https://www.codingninjas.com/studio/problems/reverse-the-string_799927 https://www.codingninjas.com/studio/problems/merge-sort_920442 5 Problem Solving using Linked List: https://www.codingninjas.com/studio/problems/reverse-the-singly-linked- list_799897 https://www.codingninjas.com/studio/problems/middle-of-linked-list_973250 https://www.codingninjas.com/studio/problems/merge-two-sorted-linked- lists_800332 https://www.codingninjas.com/studio/problems/delete-kth-node-from-end-in- linked-list_799912 https://www.codingninjas.com/studio/problems/reverse-list-in-k- groups_983644 6 Problem Solving using Stacks and Queues: https://www.codingninjas.com/studio/problems/sort-a-stack_985275 https://www.codingninjas.com/studio/problems/reverse-stack-using- recursion_631875 https://www.codingninjas.com/studio/problems/redundant-brackets_975473 https://www.codingninjas.com/studio/problems/delete-middle-element-from- stack_985246 https://www.codingninjas.com/studio/problems/reverse-the-singly-linked- list_799897 7 Problem Solving using Queues: https://www.codingninjas.com/studio/problems/reversing-a-queue_982934 https://www.codingninjas.com/studio/problems/find-the-first-circular-tour-that- visits-all-the-petrol-pumps_799923 https://www.codingninjas.com/studio/problems/reverse-first-k-elements-of- queue_982771 https://leetcode.com/problems/simplify-path/ https://www.codingninjas.com/studio/problems/span-of-ninja-coin_1475049 8 Problem Solving using Trees: https://www.codingninjas.com/studio/problems/tree-height_4609628 https://www.codingninjas.com/studio/problems/count-leaf-nodes_893055 https://www.codingninjas.com/studio/problems/kth-level_920333 SPSU/Syllabus Format 2023 Page 3 of 4  https://www.codingninjas.com/studio/problems/left-view-of-a-binary- tree_920519 https://www.codingninjas.com/studio/problems/construct-a-binary-tree-from- preorder-and-inorder-traversal_920539 https://www.codingninjas.com/studio/problems/k-th-largest-number_920438 https://www.codingninjas.com/studio/problems/h_920474 9 Problem Solving Using Graphs: https://www.codingninjas.com/studio/problems/bfs-in-graph_973002 https://www.codingninjas.com/studio/problems/detect-cycle-in-a-directed- graph_1542162 https://www.codingninjas.com/studio/problems/get-path-dfs_2033590 https://www.codingninjas.com/studio/problems/topological-sort_985252 10 Problem Solving Using Heaps and Tries: https://www.codingninjas.com/studio/problems/min-heap_4691801 https://www.codingninjas.com/studio/problems/kth-smallest-element_893056 https://www.codingninjas.com/studio/problems/k-th-largest-sum-contiguous- subarray_920398 https://www.codingninjas.com/studio/problems/merge-two-binary-max- heaps_1170049 https://www.codingninjas.com/studio/problems/implement-trie_1387095 https://www.codingninjas.com/studio/problems/longest-common- prefix_2090383 Examination Scheme: Theory Total – 100 Marks Components Continuous Internal Assessment (A, External Assessment CA, TP, Q, MT, CT etc.) Weightage (%) 40 60 * A-Attendance, CA-Class Assignment, TP-Term Paper, Q-Quiz, MT-Mid Term, CT-Class Test etc. The attendance will carry 5% weightage, for other assessment components and the % weightage may vary. Examination Scheme: Practical Total – 100 Marks Components Continuous Internal Assessment (LP, External Assessment MTP, VV, R, P, etc.)* Weightage (%) 40 60 * LP-Lab Performance, R-Lab Record, MTP-Mid Term Practical, VV- Viva Voce, P-Project. The attendance will carry 5% weightage, for other assessment components and the % weightage may vary. Text & Reference Books:  Narasimha Karumanchi. Data Structures and Algorithms Made Easy. Careermonk Publications. 2016.  Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, The MIT Press. 2009.  Robert Sedgewick and Kevin Wayne. Algorithms, 4th Edition  Antti Laaksonen. Guide to Competitive Programming. Springer. 2017. Web Links:  https://www.codingninjas.com/  https://leetcode.com/  https://www.geeksforgeeks.org/  https://codeforces.com/ SPSU/Syllabus Format 2023 Page 4 of 4