Sunday, August 4, 2013

Training path for Competitive Programming

Training path

We want to establish a knowledge base of unprecedented! We want this page to contain a more complete list of what needs to know an Olympic success. helps us and you!
Another list http://www.scribd.com/doc/58361421/Programming-Camp-Syllabus

Data Structures

Algorithms and programming techniques

Mathematics

Geometry

Computer Graphics FAQ
courses after Computational Geometry: Algorithms and Applications, Mark de Berg, M. van Krefeld, M. Overmars, O. Schwarzkopf
  • Intersection of two segments
  • The closest points of the plan
  • Point inside a polygon
    • http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
    • http://tog.acm.org/editors/erich/ptinpoly/
  • Point in convex polygon in O (log n)
    • http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm # Monotone% 20Polygons
  • Pick's Theorem
  • The area of ​​a polygon
  • Center of gravity of a polygon
  • Polygon triangulation in O (n ^ 2)
  • Intersection of two circles
  • Minimal enclosing circle
  • Convex hull
    • Educational Application Archive
    • http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull
    • http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
    • Application - onion peeling in O (n 2)
  • Swing vertical / radial
    • radial sweep
      • Given a set S of n points in the plane. Determine the fixed circle of radius R that covers as many points of S. O (n ^ 2 log n)
      • Given a set S of n points in the plane. To find a line that passes through the maximal number of points in S. O (n 2) with hashuri angles for O (n ^ 2 log n) with radial scanning.
      • Given a set S of n segments in the plan. To find a line that intersects the maximum number of segments in S. O (n ^ 2 log n) with radial scanning.
      • Building visibility graphics.
  • Rotating calipers
  • Intersection of convex polygons
  • Intersection of half-planes (without dualization)
  • Dualize

Sorting and searching

Greedy

Dynamic programming

Graphs

  • Shortest paths
    • Dijkstra (with Heaps, with links set with IS NOT sites, with tail as TC - Cosmin know)
    • Dijkstra low costs ;) how to use the issue of car
    • A * has a lot of intuitive appeal for me. If you compare Dijkstra's round. A *, Dijkstra's is like a puddle of water flooding outwards on a flat floor, Whereas A * is expanding like the same puddle on the floor Toward bumpy and graded to drain (the target node) at the Lowest point in the floor. INSTEAD of spreading out evenly on all sides, the water seeks the path of Least Resistance, only trying new paths When Something Gets In its way. The heuristic function is what provides the 'degree' of the hypothetical floor.
      • A * is used a lot in the game industry, being a very fast algorithm in practice. An example where it is used is the strategy game Starcraft.
    • Floyd-Warshall
    • Bellman-Ford
  • Flow
  • Trees
  • APM
    • First
    • Kruskal
    • The second APM
    • APM in directed graph
    • Kirchhoff's matrix tree theorem
  • For bipartite graphs: maximum coupling , minimal support, plenty maximum independence
  • LCA , RMQ , Level Ancestor, Tree decompositions
  • Coloring of edges, complete graphic / bipartite / some (Vizing's theorem)
  • Planar Graphs
  • Graphs tour / Hamiltonian cycle
  • Implication graph and 2-SAT

Strings

Formal languages ​​and finite automata

Game Theory

Various

STL (Standard Template Library)

  • vector, deque, stack, list
  • string
  • set, map, hash_map
  • peer
  • sort
  • priority_queue
  • bitset
  • iterators

Searches

  • backtracking
  • iterative deepening
  • branch and bound

Optimizations

Working with memory

Bulan

  • Randomization (2 to 8, k-opt)
  • Constants
  • Interpolation Taylor / Gauss polynomial formula

Smenuri

Useful Books

  • Ioan Tomescu
    • "Problems of Combinatorics and Graph Theory" (which was given to ONI or batch almost every year about a problem or more)
    • "Combinatorics and Graph Theory"
  • John Cuculescu
    • "International Mathematical Olympiad of Students'
  • EA Morozova, IS Petracov, VA Skvortova
    • "International Mathematics Olympiad"
  • "Mathematical Problems KVANT translated from Soviet magazine"
  • AM Iaglom, IM Iaglom
    • "Basic Problems treated neelementare"
  • Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest
  • DE Knuth
    • "The Art of Computer Programming" ("The Art of Computer Programming")
    • "Concrete Mathematics"
  • Jon Bentley
    • "Programming Pearls"
  • Steven Skien
    • "The Algorithm Design Manual"
  • M. Crochemore and W. Rytter
  • Mark de Berg
    • "Computational geometry"
  • Emanuela Cerchez and Marinel Serban
    • "Programming in C / C + + for high volume 1,2,3"
Posted by at 2 comments:

Saturday, November 3, 2012

Coding Guideline

Least Privilege Principle:
  • Put as much restriction as possible. 
Class:
  • Single Responsibility Principle - There should be only one reason to change a class. 
  • Class should always be responsible for maintaining its valid state. 
  • Class shouldn’t expose its internal implementation. 
  • Tell, don’t ask - Get the information you need from others, and then do your own calculations and make your own decisions. Don’t give up control to others! 
  • Main should be just the entry point of program, it shouldn't contain any program logic. 
  • Class containing main shouldn't contain any other fields or methods. 
Constructors:
  • Constructor should do minimal amount of work to make the object in valid state. 
  • Use factory or builder pattern when you need parameter validation. 
Variables:
  • No public variables. 
  • Variables should be exposed only by properties. 
  • Don't reuse variables. 
  • Always try to minimize the scope of variables. 
Methods: 
  • A method should do only one thing and does it well.
  • Don't mutate parameters of a method; if you do, return that parameter and make it explicit. 
Comments:
  • Comments that contradict the code are worse than no comments. 
  • Comments aren't replacement of documentation. 
  • Do not comment WHAT you are doing, but WHY you are doing it. 
Static:
  • Don't use static variables unless you have a compelling reason as static variables introduce global state. 
  • Think twice before introducing static methods. Does it belong to an object? 
  • Static methods shouldn't change any object's state. 
  • Regardless of state, static methods should give same output for same input set. 
Inheritance:
  • Favor composition over inheritance. 
  • Don't use inheritance for adding extra functionality. 
  • Don't use inheritance for code reuse. 
  • Use inheritance only when there is an "IS A" relationship 
  • Always obey Liskov Substitution Principle. 
Interface:
  • Code against interface as it reduces coupling, separates behavior from implementation 
  • Interface should be granular - an interface should only contain logically related set of behaviors. 
Validation:
  • Don’t trust user input or external data. Always validate them. 
Exceptions:
  • Exceptions are for exceptional scenarios, not for normal logical code flow. 
  • Don’t swallow exceptions without proper explanation 
Contract:
  • Design by contract. 
  • If you assume anything make it explicit by using assert/contract. 
  • For external library adopt Defensive Coding. 
Collections:
  • Use empty collection instead of null. 
  • Use list instead of array as list allows more flexibility unless there is a compelling reason. 
Optimization:
  • Premature optimization is root of all evil. 
  • Always optimize algorithm and data structures. 
  • Don’t micro-optimize as modern compilers are better in micro optimization. Micro optimization often leads to unreadable and buggy code. 
  • Optimize only when you need to. 
  • Don’t optimize without profiling your code or knowing the bottleneck. 
Miscellaneous:
  • Code for humans, not for machine. As machine only understands 0 or 1. 
  • Avoid Deep Nesting. 
  • Whatever you do, be consistent. 
  • Limit line length. Shouldn’t be more than 120 characters. 
  • Refactor early, refactor quick. As more time elapses, refactoring becomes more hard and costly. 
  • Write the least amount of clearly understandable code as number of bugs increases with LOC. 
Posted by at No comments:

Advice for undergrad students


  1. First read Teach Yourself Programming in Ten Years. This is one of the best articles for freshers. Every advice given in that article is priceless and applicable to not only to programming, but to any other profession.
  2. You may be interested in programming competition or research sort of thing. But whatever you do, learn at least one programming language very well and also its advance features. If you don’t have proper language skill, then you can’t know for sure your algorithm is going to work. Yes, you can learn any language you want, but to keep pace with software industry learn at least one object oriented language. C++, Java, C# would be great choice as they are widely used and have great libraries.
  3. Although there are many programming paradigms, object oriented paradigm is the dominant paradigm in software industry. Almost all the popular languages support object oriented paradigm. You should have knowledge how to design classes, assign responsibilities and properly sew them together to produce reusable, readable and testable code.
  4. You should learn at least one dynamic language for scripting. You may be a fan of static typing, but there’s some scenario where dynamic typing really comes in handy. Python, Ruby and Perl are great choice. Dynamic languages are also very popular in web development. If you really feel interested, you can learn one functional programming language. Functional programming is gaining popularity due to the rise in parallel and multi-core programming. F# which is supported on .NET and Scala on JVM are two great options for learning FP.
  5. Develop one great academic project to awe your future employer. It doesn’t necessarily have to be a big project. But keep your code clean and make your design elegant. And it should be developed in an OOP language. Remember, as you don’t have any industry experience, these sort of projects really come in handy to prove your coding skill.
  6. Use source control to keep track of modification of your source codes and keep backup of your codes. Although Subversion may be still very popular. But if you haven’t any prior experience with subversion, then you should start with distributed version control system. Git and Mercurial are two most popular distributed version control system. You can start with any of them. By comparison mercurial is somewhat easier than git.
  7. Keep your academic projects hosted in any online code hosting site.It serves multiple purposes. You have a safe backup storage, you can access your code anytime anywhere, provided that you have a decent internet connection and anyone (including your interviewer) can have a look at your code. There are several popular code hosting sites, among them github is the most popular one which uses
  8. Learn about refactoring and code smell. For writing clean, readable and maintainable code, they are extremely important. We usually code our academic project in hastily and haphazard manner with no code organization. We do this, because no one is going to read our source codes apart from us and no one has to maintain our academic projects. This sort of throw away coding may be acceptable for some scenarios in academia. But in software industry, this is simply unacceptable. Because, industry projects aren’t just for few months development and maintenance. Many projects are being actively developed and maintained for decades. Term projects or assignments have tiny codebase and industry projects have much more bigger codebase. If they aren’t written cleanly manner, it would be next to impossible to develop and maintain these projects. So focus on code readability.
  9. Many CS students aren’t familiar with testing. And many of them don’t even think testing is an important part of development. Writing testable code properly is an essential skill of a software engineer. Be familiar with software quality assurance and different kinds of testings - acceptance testing, regression test, integration test and most importantly unit test. You have to work with SQA engineers side by side. So if you don’t have any idea about their task, you may face some difficulties.
  10. Unit testing has become industry standard nowadays. And writing unit test isn’t testers’ responsibility, it’s programmers’ responsibility. At any software farm which maintains code quality, you have to write unit tests for your own code and make sure that every unit test passes. Unit testing isn’t all about testing per se, it’s about designing your code properly and making sure your individual module works in every probable scenario.
  11. Learn about software development methodology. Agile software development is currently the most popular one. Learn how projects are developed and delivered to the client using agile methodology. You can start with scrum which is widely used, a variant of agile methodology.

Posted by at No comments:
Subscribe to: Posts (Atom)