Unit I
Introduction, Tips to be competitive, Problems on linear & non-linear data structures using STL/Collections/libraries, Problems on algorithmic paradigms – divide-and-conquer, greedy, dynamic programming.
| Course Name | Competitive Programming |
| Course Code | 23CSE453 |
| Program | B. Tech. in Computer Science and Engineering (CSE) |
| Credits | 3 |
| Campus | Amritapuri ,Coimbatore,Bengaluru, Amaravati, Chennai |
Introduction, Tips to be competitive, Problems on linear & non-linear data structures using STL/Collections/libraries, Problems on algorithmic paradigms – divide-and-conquer, greedy, dynamic programming.
Implementation and application of advanced data structures – segment tree, Fenwick tree, suffix tree, suffix array, decision tree. Java BigInteger, Combinatorics – Fibonacci numbers, Binomial coefficients, Catalan numbers, Number theory – prime numbers, GCD, LCM, finding prime factors with optimal trial divisions, working with prime factors, extended Euclid.
Computational geometry – Polygon representation, Plane Sweep Technique, Convex Hull and Algorithm, Duality Transform and Application- checking if polygon is convex, a point is in polygon, cutting polygon with straight line, Point Location and Triangulation, Voronoi diagrams and Delaunay triangulation.
Course Objectives
Course Outcomes
CO1: Use of programming libraries such as C++ STL or Java Collections for problem-solving
CO2: Apply algorithmic design strategies to solve problems from prominent online judge platforms
CO3: Learn advanced data structures and their applications to problem solving.
CO4: Apply algorithm analysis and optimization techniques to improve the efficiency of algorithms
CO5: Learn and apply the skills learned in the course to effectively tackle competitive-level contests.
CO-PO Mapping
|
PO/PSO |
PO1 |
PO2 |
PO3 |
PO4 |
PO5 |
PO6 |
PO7 |
PO8 |
PO9 |
PO10 |
PO11 |
PO12 |
PSO1 |
PSO2 |
|
CO |
||||||||||||||
|
CO1 |
1 |
– |
– |
– |
3 |
– |
– |
3 |
– |
– |
3 |
2 |
||
|
CO2 |
1 |
– |
– |
– |
3 |
– |
– |
3 |
– |
– |
3 |
2 |
||
|
CO3 |
2 |
3 |
2 |
– |
3 |
– |
– |
3 |
– |
– |
3 |
2 |
||
|
CO4 |
1 |
2 |
2 |
– |
3 |
– |
– |
3 |
2 |
– |
3 |
2 |
||
|
CO5 |
2 |
3 |
2 |
– |
3 |
– |
– |
3 |
2 |
– |
3 |
2 |
Evaluation Pattern: 70:30
|
Assessment |
Internal |
End Semester |
|
MidTerm Exam |
20 |
|
|
Continuous Assessment – Theory (*CAT) |
10 |
|
|
Continuous Assessment – Lab (*CAL) |
40 |
|
|
**End Semester |
30 (50 Marks; 2 hours exam) |
*CAT – Can be Quizzes, Assignments, and Reports
*CAL – Can be Lab Assessments, Project, and Report
**End Semester can be theory examination/ lab-based examination/ project presentation
Textbook(s)
Steven Halim and Felix Halim, “Competitive Programming 3 – The New Lower Bound of Programming Contests : Handbook for ACM ICPC and IOI Contestants”, Edition 3, 2013.
Reference(s)
Antti Laaksone , “Competitive Programmer’s Handbook” , 2018.
Bjarne Stroustrup, “C++ Programming Language”, Fourth Edition,2022.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”, Fourth Edition.
Ivor Horton, “Using the C++ Standard Template Libraries”, 2015 Edition.
DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.