ECS 342/442/642: Competitive Programming

---

If there is any feedback, please provide it anonymously in this Google form.

---

Lectures

	Date	References
Lecture 01	8th Jan 2025	Introduction (Ch 1, 2.1)
Lecture 02	9th Jan 2025	Recursive Algorithms (Ch 2.2.1, 2.2.2)
Quiz 01	10th Jan 2025	quiz-01
Lecture 03	15th Jan 2025	Algorithm Design Examples (Ch 3.2)
Lecture 04	16th Jan 2025	Algorithm Design Examples (Ch 3.2)
Lecture 05	17th Jan 2025	Computing Recurrence
Lecture 06	22nd Jan 2025	Sorting and Searching (Ch 4.1, 4.2, 4.3)
Lecture 07	23rd Jan 2025	Greedy Algorithms
Quiz 02	24th Jan 2025	Quiz-02
Lecture 08	25th Jan 2025	Git and GitHub
Lecture 09	29th Jan 2025	Dynamic Programming (Ch 6.1)
Lecture 10	30th Jan 2025	Dynamic Programming (Ch 6.2.1, 6.2.2)
Lecture 11	31st Jan 2025	Dynamic Programming (Ch 6.4 in [3])
Lecture 12	5th Feb 2025	Graph Algorithms (Ch 7.1, 7.2)
Lecture 13	6th Feb 2025	Directed Acyclic Graphs (Ch 7.4)
Lecture 14	12th Feb 2025	DAG and Successor Graphs (Ch 7.5)
Lecture 15	13th Feb 2025	Shortest Paths (Ch 7.3)
Lecture 16	14th Feb 2025	Minimum Spanning Trees (Ch 7.6)
Tutorial	19th Feb 2025	Minimum Spanning Trees (Ch 7.6)
Quiz 03	20th Feb 2025	Quiz-03
Quiz 04	21st Feb 2025	Quiz-04
Mid-Term	22st Feb 2025	Mid-term
Lecture 17	12th Mar 2025	Tree Algorithms (Ch 10.1.1) and Neeldhara's Notes
Lecture 18	13th Mar 2025	Tree Algorithms (Ch 10.1.2, 10.2.1)
Lecture 19	15th Mar 2025	Range Queries (Ch 9.1, 9.2.1)
Lecture 20	20th Mar 2025	Tree Range Queries (Ch 9.2.2, 10.2.2)
Lecture 21	21st Mar 2025	Number Theory (Ch 11.1.1 to 11.1.4)
Lecture 22	24th Mar 2025	Combinatorics (Ch 11.2.1 to 11.2.2)
Lecture 23	27th Mar 2025	Matrices (Ch 11.3.1 to 11.3.3)
Quiz 05	28st March 2025	Quiz-05
Lecture 24	2nd April 2025	Probability (Ch 11.4.1 to 11.4.2)
Lecture 25	3rd April 2025	Bit-Parallel Algorithm (Ch 2.3 and 8.1)
Quiz 06	4th April 2025	Quiz-06
Lecture 26	8th April 2025	Code Optimization (Ch 2.1, 3.3)
Lecture 27	9th April 2025	DP Optimization (Ch 15.4.2, 15.4.3)
Quiz 07	10th April 2025	Quiz-07
End-term Exam	21st April 2025	End-Term

Problems

We will use this Github repo to store the code. There are no individual links from problems to solutions. You can find corresponding solution in the repo using the problem name. The precise problem statement is mentioned at the start of the solution files in the comments.

Name	Description	Name	Description
test-01	Compute Fibonacci	test-02	Missing Number
test-03	Maximum Subarray Sum	test-04	Increasing Array
test-05	Two Knights	test-06	Repetitions
test-07	Permutations	test-08	Tower of Hanoi
test-09	Josephus Problem I	test-10	Josephus Problem II
test-11	Restaurant Customers	test-12	Sum of Two Values
test-13	Is Subsequence	test-14	Jump Game II
test-15	Fractional Knapsack Problem	test-16	Tasks and Deadlines
test-17	Minimizing Coins	test-18	Removing Digits
test-19	Increasing Subsequence	test-20	Grid Paths
test-21	Money Sums	test-22	Book Shop
test-23	Counting Rooms	test-24	Labyrinth
test-25	Planets Queries I	test-26	Investigation
test-27	Planets Queries II	test-28	Shortest Routes I
test-29	Flight Discount	test-30	Longest Flight Route
test-31	Road Reparation	test-32	Knight's Tour
test-33	Subordinates	test-34	Tree Matching
test-35	Tree Diameter	test-36	Company Queries I
test-37	Dynamic Range Sum Queries	test-38	Forest Queries
test-39	List Removal	test-40	Subtree Queries
test-41	Exponentiation	test-42	Counting Divisors
test-43	Binomial Coefficients	test-44	Bracket Sequences I
test-45	Fibonacci Numbers	test-46	Graph Paths I
test-47	Dice Probability	test-48	Airplane Seats
test-49	Hamming Distance	test-50	Beautiful Subgrids