Computer Science

2024-06-2501:04 Status:Pseudo Tags: Discrete mathematics Electronics Cyber Security Internet University Notes: CPSC 110 Notes (Best Programming Practices) CPSC 121 Models of Computation CPSC 210 Notes

Overview:

Concepts

Base n number systems File storage Computer memory Priority Algorithms Data structures

Languages

SQL Console commands C language Python Java

Competitive Programming Roadmap

The order of subjects by topic that I find most didactic is the following:

Introduction: Binary search, algorithm complexity analysis, cool C++ tricks to use in a programming contest, sorting algorithms (quadratic, linearithmic and the linear ones), and ternary search.

Mathematics: Find all divisors on logarithmic time, factorization on logarithmic time, sieve of Eratosthenes, modular arithmetic basic properties, finding inverse using extended euclidean algorithm, Fermat’s little theorem, exponentiation in logarithmic time (iterative, recursive, modular and with matrices), using matrix exponentiation to solve linear recurrence equations in logarithmic time, Chinese remainder theorem, and FFT.

Data Structures: Queue, stack, deque, priority queue, std::set, std::map, std::pair, union find, binary indexed tree, segment tree, sqrt decomposition, and treap.

Graph Algorithms: DFS, BFS, using BFS to solve SSSP on undirected graph, using BFS to find the diameter of tree and its center, finding connected components, detecting cycles, flood fill, topological sort, finding articulation points and bridges, Prim’s algorithm, Kosaraju’s algorithm, 2-SAT problem, Kruskal’s algorithm, Prim’s algorithm, Bellman–Ford algorithm, Dijkstra’s algorithm, SSSP on DAG, Floyd–Warshall algorithm, lowest common ancestorFord–Fulkerson method, Edmonds–Karp algorithm, Dinic’s algorithm, minimum edge cover, minimum vertex cover, maximum independent set, and maximum matching problem using Hopcroft–Karp algorithm.

Paradigms: Two pointers, backtracking, divide and conquer, greedy algorithms, activity selection problem, dynamic programming, finding the n-th Fibonacci’s term in linear time, both coin change problem, knapsack problem, traveling salesman problem, meet in the middle, and dynamic programming optimizations.

Geometry: Points, vector, tuples, polygons, points orientation (clockwise or counterclockwise), checking if a polygon is convex, checking if a point is inside a polygon in logarithmic time, linear transformations, and line sweep algorithms.

Strings: Rabin–Karp algorithm, tries data structure, Manacher’s algorithm, Z function and Z algorithm, KMP algorithm, Aho–Corasick algorithm, and suffix tree.

---

It’s a terrible idea to focus on one topic and study it until mastering every subject. Graph’s algorithm, for example, is a topic that lasts throughout your whole life. You’ll never completely master it any time soon and, therefore, you’ll never start studying computational geometry (for example).

The best idea is to study each subject a little and change the topic after some days. The Competitive Programming 3 book provides a nice suggestion of a 13 weeks introductory course. Each week cover one or two topics.

• Wk1: Introduction
• Wk2: Data Structures & Libraries
• Wk3: Complete Search, Divide and Conquer, Greedy
• Wk4: Dynamic Programming 1 (Basic ideas)
• Wk5: Dynamic Programming 2 (More techniques)
• Wk6: Mid-Semester Team Contest
• Wk7: Graph 1 (Network Flow)
• Wk8: Graph 2 (Matching)
• Wk9: Mathematics (Overview)
• Wk10: String Processing (Basic skills, Suffix Array)
• Wk11: Computational Geometry
• Wk12: More Advanced Topics
• Wk13: Final Team Contest

Note that Steve Halim and Felix Halim (the authors) chose a different order for their course suggestion. It’s not a problem, because everything is just a guideline for you.