17 September 2010 Comments Off

Competitive Programming

Competitive Programming

Author(s): Steven Halim, Felix Halim

Competitive Programming Book’s 23 sample pages: click here

This book contains a collection of relevant data structures, algorithms, and programming tips written mainly for University students who want to be more competitive in the ACM International Collegiate Programming Contest (ICPC). Although written with predominantly ICPC format and University students in mind, this book can also be used by selected high school students who want to be competitive in the International Olympiad in Informatics (IOI) or anyone who wants to participate in other relevant programming competitions.

Steven Halim and his book (Image from Facebook)

According to the Author’s objective:

“Our objective in writing this book is similar with the ICPC vision: to further improve humanity by training current students to be more competitive in programming contests. The possible long term effect is future Computer Science researchers who are well versed in problem solving skills”.

The reader must have some background knowledge in basic data structures, algorithms, and programming languages. Typically, a 2nd year Computer Science students in a University (who have passed a kind of “programming methodology” and “basic data structures and algorithms” modules) or selected high school students who have participated in National or International Olympiad in Informatics should have the necessary background.

Book Information

  1. Introduction
    • Introducing the world of Competitive Programming
    • Tips to be a competitive programmer, shared by people who are involved in ICPC + IOI
  2. Data Structures (DS) and Libraries
    • Are you aware that many DS have built-in libraries? Do you use them often?
    • Are you aware that there are many other useful DS out there without built-in libraries as of 2010?
  3. Problem Solving Paradigms (the second largest chapter in the book with 32 pages)
      1. Complete Search that is not that brute…
      2. Divide and Conquer (D&C)
      3. Greedy
      4. Dynamic Programming (DP)
    • Do you hammer every contest problem with bruce force?
    • Are you sure that you are familiar with these terms:
  4. Graph (the largest chapter in the book with 35 pages)
    • Graph Traversals, Minimum Spanning Trees, Various Shortest Paths Problems, Maximum Flow Problems
    • Special Graphs (our highlight, this section usually does not exist in other algorithm books)
  5. Mathematics
    • Number Theory, Big Integer, and many more topics in mathematics that are frequently appear in programming contests
  6. String Processing
    • Ad hoc string problems, String problems solvable with DP,
      Large string problems that must be solved with efficient DS: Suffix Tree/Array
  7. (Computational) Geometry
    • Library of “Geometry Basics”, Convex Hull, Intersection Problems, D&C in Geometry Problems

More Details: http://sites.google.com/site/stevenhalim/

29 July 2010 Comments Off

Concrete Mathematics, Second Edition

Concrete Mathematics, Second Edition

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994)

This book introduces the mathematics that supports advanced computer programming and the analysis of algorithms. The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills – the skills needed to solve complex problems, to evaluate horrendous sums, and to discover subtle patterns in data. It is an indispensable text and reference not only for computer scientists – the authors themselves rely heavily on it! – but for serious users of mathematics in virtually every discipline.

Concrete Mathematics is a blending of CONtinuous and disCRETE mathematics. “More concretely,” the authors explain, “it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems.” The subject matter is primarily an expansion of the Mathematical Preliminaries section in Knuth’s classic Art of Computer Programming, but the style of presentation is more leisurely, and individual topics are covered more deeply. Several new topics have been added, and the most significant ideas have been traced to their historical roots. The book includes more than 500 exercises, divided into six categories. Complete answers are provided for all exercises, except research problems, making the book particularly valuable for self-study.

Major topics include:

  • Sums
  • Recurrences
  • Integer functions
  • Elementary number theory
  • Binomial coefficients
  • Generating functions
  • Discrete probability
  • Asymptotic methods

This second edition includes important new material about mechanical summation. In response to the widespread use of the first edition as a reference book, the bibliography and index have also been expanded, and additional nontrivial improvements can be found on almost every page. Readers will appreciate the informal style of Concrete Mathematics. Particularly enjoyable are the marginal graffiti contributed by students who have taken courses based on this material. The authors want to convey not only the importance of the techniques presented, but some of the fun in learning and using them.

Download now! Concrete Mathematics – Graham-Knuth-Patashnik

More Books…

[...]

21 July 2010 Comments Off

C for Contest

The website of the book http://www.c4contests.net/ is accompanied with lecture series of C in You Tube and PowerPoint Slides. The book seems to be available in Bangladesh and part of India (Calcutta) only.

More news on this book :  http://www.ulab.edu.bd/Latest-News/Page-3/

10 July 2010 Comments Off

Art of Programming Contest in 48 Mirrors!

Art of Programming Contest in 48 Mirrors!

In the year 2005, I was working on compiling a manual for local programmers (in Bangladesh) and finally with the help of Steven Halim I ended up with The  “Art of Programming Contest” in 2006. Now, it is hosted by 48 Mirrors around the world! Here is few of them:

  1. psu.edu [PDF]AS Arefin – Citeseer
  2. unalmed.edu.co [PDF]AS Arefin – pisis.unalmed.edu.co
  3. huihoo.org [PDF]AS Arefin – books.huihoo.org
  4. wmwave.cn [PDF]AS Arefin – wmwave.cn
  5. neuroaio.biz [PDF]AS Arefin – kbradero.neuroaio.biz
  6. zitez.net [PDF]AS Arefin – goodies.zitez.net
  7. icpc-bolivia.edu.bo [PDF]AS Arefin – icpc-bolivia.edu.bo
  8. nus.edu.sg [PDF]AS Arefin – iscs.nus.edu.sg
  9. gwu.edu [PDF]AS Arefin – seas.gwu.edu
  10. homelinux.org [PDF]AS Arefin – vo.homelinux.org
  11. eracode.com [PDF]AS Arefin – eracode.com
  12. iftytech.com [PDF]AS Arefin – iftytech.com
  13. academia.edu [PDF]AS Arefin – newcastle-au.academia.edu
  14. ecnu.edu.cn [PDF]AS Arefin – acm.cs.ecnu.edu.cn
  15. ufrj.br [PDF]AS Arefin – maratona.dcc.ufrj.br
  16. neuroaio.biz [PDF]AS Arefin – neuroaio.biz
  17. eracode.com [PDF]AS Arefin – eracode.com
  18. ecnu.edu.cn [PDF]AS Arefin – acm.cs.ecnu.edu.cn
  19. uva.es [PDF]AS Arefin – online-judge.uva.es
  20. lesthack.com.mx [PDF]AS Arefin – lesthack.com.mx
  21. nus.edu [PDF]AS Arefin – comp.nus.edu
  22. mmu.edu.my [PDF]AS Arefin – fit.mmu.edu.my
  23. uri.com.br [PDF]AS Arefin – inf.uri.com.br
  24. csuci.edu [PDF]AS Arefin – cs.csuci.edu
  25. mmhs.ca [PDF]AS Arefin – access.mmhs.ca
  26. persiangig.com [PDF]AS Arefin – rafifar.persiangig.com
  27. indowebster.com [PDF]AS Arefin – indowebster.com
  28. uva.es [PDF]AS Arefin – online-judge.uva.es
  29. <More>

[...]

4 July 2010 2 Comments

Art of Programming Contest

Art of Programming Contest

Publication info

Author : Ahmed Shamsul Arefin (Project Compiler), Member, ACM Valladolid Online Judge Algorithmic Team, PhD Student, The University of Newcastle, Australia.
Foreworded By : Professor Miguel A. Revilla, ACM-ICPC International Steering Committee Member and Problem Archivist
ISBN : 984-32-3382-4
Pages : 247
Publication Date : 2006
Publisher : Gyankosh Prokashoni

Online version available

Book Excerpts:

This book is designed to serve as a textbook for an algorithm course focusing on programming as well as a programming course focusing on algorithms. The book is specially designed to train students to participate in competitions, especially the ACM International Collegiate Programming Contest.

The book covers several important topics related to the development of programming skills such as, fundamental concepts of contest, game plan for a contest, essential data structures for contest, input/output techniques, brute force method, mathematics, sorting, searching, greedy algorithms, dynamic programming, graphs, computational geometry, Valladolid Online Judge problem category, selected ACM programming problems, common codes/routines for programming, Standard Template Library (STL), PC2 contest administration and team guide. The book also lists some important websites/books for ACM/ICPC Programmers.

About ACM International Collegiate Programming Contest:

The Association for Computing Machinery (ACM) sponsors a yearly programming contest, recently with the sponsorship of IBM. The contest is both well-known and highly regarded: in 2005, 2400 teams competed from more than 100 nations competed at the regional levels. Sixty of these went on to the international finals. This contest is known as ACM International Collegiate Programming Contest (ICPC).

The regional contest itself is typically held in November, with the finals in March. Teams of three students use C, C++, or Java to solve six to eight problems within five hours. One machine is provided to each team, leaving one or two team members free to work out an approach. Often, deciding which problems to attack first is the most important skill in the contest. The problems test the identification of underlying algorithms as much as programming savvy and speed.

Review(s):

Dr. M. Lutfar Rahman, Professor, Department of Computer Science and Engineering, University of Dhaka:

Smile “I believe that the book will be book will be of immense use for young programmers interested in taking part in programming competitions.”