How to improve in Math for Programming

How to improve in Math for Programming

My math skills aren’t that great, to be honest. I used to suffer from doing some easy problem solving that are math-related.

How to improve in Math for Programming

My math skills aren’t that great, to be honest. I used to suffer from doing some easy problem solving that are math-related.

I do think my poor math skills are mostly because I didn’t get a good foundation in high school. So, without further ado let’s get into it.

To improve in Math you would actually have to solve a lot of Math-related programming problems. Like the ones that competitive programmers do.

I was researching a lot and I found out some great resources.

First step

If you know nothing about math… The best way to start your journey is by watching Khan Academy, of course.

https://www.khanacademy.org/

Khan Academy has a huge library of educational videos about different Math topics, starting from kindergarten level to some university level topics.

Second step

Use the Open Source Society University math curriculum.

https://github.com/ossu/computer-science#core-math

Third step

In my opinion, this is the most important step. And it’s actually doing a lot of Problem Solving.

A really great resource is a book called Competitive Programming 3 the book is great overall, and most importantly the Math chapter in it. The authors have really gathered a lot of Math-related problems and if you solve just a few you will definitely improve your Math and Problem Solving skills.

You don’t need to buy the book to check the problems though. You can check the problems available in the book on a website called UVA-Online Judge.

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=695

There are more than 300 problems in this chapter focused on Math.

Conclusion

Finally, Math is hard but like anything in life if you do Math more and more you will eventually improve.

Good luck studying and I’ll be glad if you can share with me any other resource that you found helpful.

By Hassan El Desouky on October 3, 2019.

Canonical link

Tags: math, algorithm, data-structure, c++, advice, blogging   |   Edit on GitHub

The Ultimate Guide for the ICPC

The Ultimate Guide for the ICPC

Resources to prepare yourself for the The International Collegiate Programming Contest (ICPC) or any competitive programming contest

The Ultimate Guide for the ICPC

Resources to prepare yourself for the The International Collegiate Programming Contest (ICPC) or any competitive programming contest

Photo by Ariel Besagar on Unsplash

What is the ICPC?

“The ICPC, the ‘International Collegiate Programming Contest,’ is an extra-curricular, competitive programming sport for students at universities around the world. ICPC competitions provide gifted students opportunities to interact, demonstrate, and improve their teamwork, programming, and problem-solving process. The ICPC is a global platform for academia, industry, and community to shine the spotlight on and raise the aspirations of the next generation of computing professionals as they pursue excellence.” — Wikipedia

Disclaimer

I’m by no mean a top coder or a world finalist. I just wanted to share the resources I found helpful, and if you follow them, hopefully, you will be an ICPC world finalist.


Introduction

I really like competitive programming, and I really want to be someone like Gennady Korotkevich. He is truly a living legend in the field of competitive programming.

Anyways, let’s get into the details …


The Steps to be a Good Competitive Programmer

It’s really simple: There are no tricks and there’s no short way … all you need is dedication and a goal, and you are all set.

First, you will need to be familiar with at least one of the following programming languages: Python, Java, C, or C++.

Secondly, you will need to study all of the different topics about data structures and algorithms.

Finally, do a lot of problems … a lot!


Topics

These are the main topics that should be done thoroughly.

Number theory

  1. Euclidian and extended Euclidian algorithm
  2. Modular arithmetic and modular inverse
  3. Prime generation (sieve and segmented sieve)
  4. Fermat’s theorem
  5. Euler’s Totient function
  6. Miller Rabin primality test
  7. Chinese remainder theorem
  8. Lucas theorem

Greedy algorithms

  1. Activity-selection problem
  2. Kruskal’s algorithm
  3. Prim’s algorithm
  1. Topcoder binary search
  2. Binary search
  3. Ubiquitous binary search — get a grasp of discrete and continuous binary searches

Data structures

  1. Linked lists
  2. Binary-search tree
  3. Binary-indexed tree or Fenwick tree
  4. Segment Tree (RMQ, range sum,andlazy propagation)
  5. Red-Black trees
  6. Hashing
  7. Extensive list of data structures

Graph algorithms

  1. Breadth-first search (BFS)
  2. Depth-first search (DFS)
  3. Shortest path from source to all vertices (Dijkstra)
  4. Shortest path from every vertex to every other vertex (Floyd Warshall)
  5. Minimum spanning tree (Prim)
  6. Minimum spanning tree (Kruskal)
  7. Topological Sort
  8. Johnson’s algorithm
  9. Articulation points (or cut vertices) in a graph
  10. Bridges in a graph
  11. All graph algorithms

String algorithms

Learning library functions for string actually proves very helpful. (C++: See this, this, String in Java.)

  1. KMP algorithm
  2. Rabin karp
  3. Z’s algorithm
  4. Aho-Corasick string matching
  5. Suffix arrays
  6. Trie
  7. Finite automata

Dynamic programming

  1. Dynamic programming — GeeksforGeeks
  2. Dynamic Programming — Codechef

Dynamic programming is quite important and can be infused and asked with various other topics. Some different types of DP concepts are:

Classic DP

  1. Longest-common subsequence
  2. Longest-increasing subsequence
  3. Edit distance
  4. Minimum partition
  5. Ways to cover a distance
  6. Longest path in matrix
  7. Subset-sum problem
  8. Optimal strategy for a game
  9. 0–1 knapsack problem
  10. Assembly-line scheduling
  11. All DP algorithms

Computational geometry

  1. Convex-hull algorithms
  2. Geometric algorithms

Resources

“Competitive Programming 3” This book is beyond great. I’m currently in the middle of it and I’m enjoying the problems and the book structure. I highly recommended it.

“The ‘Science’ of Training in Competitive Programming” In this blog,the author explains how to train for CP and what he did in order to be a good problem solver.

How to be a red coder This Quora answer really goes deep into how to be a red coder and train efficiently.

By Hassan El Desouky on September 19, 2019.

Canonical link

Tags: algorithm, data-structure, c++, advice, competitive-programming, blogging   |   Edit on GitHub