XKCDCS
From XKCD Wiki
Hello wiki!
Contents 
[edit] Topics covered by #xkcdcs
 algorithms
 computer languages
 programming
[edit] Recommended reading
Title  ISBN  Author(s)  Recommended By  

Algorithms, Coding 
The Art of Computer Programming  ISBN 0201485419  Donald E. Knuth  R.K., cypren, IceKarma 
Introduction to Algorithms  ISBN 0262032937  Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein 
R.K., cypren  
Algorithms: A Functional Programming Approach  ISBN 0201596040  Fethi A. Rabhi Guy Lapalme 
R.K.  
Software Engineering, Development Methodology 
Code Complete, Second Edition  ISBN 9780735619678  Steve McConnell  cypren 
The Pragmatic Programmer  ISBN 9780201616224  Andrew Hunt David Thomas 
cypren  
When Teams Work Best  ISBN 9780761923664  LaFasto, Frank M. J., and Carl Larson.  Fredd  
SystemLevel Programming  Machine Architecture: Things Your Programming Language Never Told You 

Herb Sutter  cypren 
What Every Programmer Should Know About Memory  
Ulrich Drepper  cypren  
Linux System Programming  ISBN 9780596009588  Robert Love  cypren  
Linux Assembly Language Programming  ISBN 9780130879400  Bob Neveln  cypren  
Understanding the Linux Kernel, 3rd Edition  ISBN 9780596005658  Daniel P. Bovet Marco Cesati 
cypren  
Windows System Programming, Third Edition  ISBN 9780321256195  Johnson M. Hart  cypren  
C  ISO/IEC 9899  
ISO/IEC JTC1/SC22/WG14  R.K., IceKarma 
The C Book  
Mike Banahan Declan Brady Mark Doran 
R.K.  
The C Programming Language  ISBN 9780131103627  Brian W. Kernighan Dennis M. Ritchie 
You  
C Programming Notes  
Steve Summit  R.K.  
C++  C++ FAQs, Second Edition  ISBN 9780201309836  Marshall Cline Greg Lomow Mike Girou 
cypren 
C++ FAQ Lite   
Effective C++, Third Edition  ISBN 9780321334879  Scott Meyers  cypren  
Exceptional C++ More Exceptional C++ Exceptional C++ Style 
ISBN 9780201615623 ISBN 9780201704341 ISBN 9780201760422 
Herb Sutter  cypren 
[edit] Programming challenges
 Project Euler
 About.com challenges
 IEEEXtreme 24 Hour Programming Challenge
 Programming Contest Problems Archive
 Golf
 Sphere Online Judge
 Waterloo AI contest / Google AI challenge
[edit] Links
 Dictionary of Programming Languages
 99 Bottles of Beer: one program in 1200 variations
 Programmer Competency Matrix
 Ali & Asma's C by Example
 Languages
 Books
 Multithreaded books
[edit] Source code
 Pastebin
 Arbitrary precision prime number listing
 Sophie Germain prime generator
 Fraction approximator
 Multithreaded factorization
 Speed test
 Quines
 Tarpit
[edit] Exercises
This section uses the difficulty score system of Donald Knuth, which is quasilogarithmic and encodes the needed time (indicated by the tens digit) and creativity (indicated by the ones digit).
[edit] 10
Time: no more than a few minutes total. Unlike the Project Euler minute, this is truly an accurate indication of the effort required.
 Write a "hello world" program. [10]
 Write a "99 bottles of beer" program. [11]
 Write a program that copies its input to its output. [12]
 Study features of plants. [13]
 Practice writing trivial programs. [14]
 Write a prioritized list of topics to study. [16]
[edit] 20
Time: Fifteen minutes to half an hour.
 Implement a fundamental algorithm. [20]
 Investigate artwork by M.C. Escher or Leonardo da Vinci. [23]
 Solve the problem given in xkcd comic 287, "NPComplete" [25]
 Bonus: Prove it is not NPcomplete.
 Prove or derive a proposition important to computer science. [25]
 Find other interesting exercises. [27]
 Write a program to factor the time. [28]
[edit] 30
Time: Possibly a few hours.
 Minimize the CPU user time^{*} to solve a Project Euler problem. [33]
 ^{*} See e.g. the man pages for
times()
orgetrusage()
.
 Write a useful utility program. [34]
 Find multiples of π or e that are nearly integers. [35]
 Bonus: Extend your solution to arbitrary real numbers.
 Write a parser. [35]
 Write a IRC bot to relay messages between channels, for example to link #xkcdcs with #xkcdcompsci. [35]
 Bonus: Use the sockets library to do so.
 Write a program that solves Project Euler problem 76 in less than sixty seconds of CPU user time (60 s_{u})^{†} without recursion or formulas. [35]
 Bonus: Find the solution in less than 5 s_{u} with this approach.
 Bonus: Minimize the s_{u} needed to solve for 128 instead of 100.
 ^{†} This is not intended to be competitive, but if you would like to compare results, multiply s_{u} by 100 and divide by the s_{u} used to run the speed test program.
 Write a program to locate strings in π. [36]
 Bonus: Locate strings in another irrational number, such as e.
 Program a simple game. [36]
 Create a nice image of a Project Euler problem. [37]
 Bonus: Create an image of a problem that lacks an obvious connection to geometry.
 Programmatically generate images of any kind. [39]
 Implement Conway's Game of Life. [39]
 Write a quine. [39]
[edit] 40
Time: Days or weeks.
 Learn a new language. [42]
 Bonus: Use it to write a nontrivial program.
 Port a program to a different architecture. [45]
 Program a complex game. [45]
 Write a critique of a programming language. [46]
 Rewrite a program in a different language. [47]
 Bonus: Cross paradigms; e.g. use a functional style instead of an imperative object oriented style.
 Minimize the length of raptorproof fencing needed to contain n raptors^{†}. Assume they are sleeping, and not woken by fence construction. [47]
 Bonus: Find the optimal sleeping arrangement for n paranoid but very tired raptors; that is, maximize the fence needed by an adversary. [50]
 ^{†} Raptors are highly intelligent. Two or more in the same fenced area will be able to escape through cooperation.
 Implement an unusual number system. [48]
 Find floor plans that maximize the chance for a human with perfect knowledge of their layout to escape naïve invading raptors and leave the building, given the information provided in xkcd comic 135. [49]
 Program a complex game in no more than seven calendar days. [49]
 Bonus: Finish in three days.
 Design a new language. [49]
 Bonus: Write a nontrivial program in the language.
 Bonus: Prove the language is Turing complete.
 Bonus: Alternatively, prove the language is not Turing complete, and demonstrate a useful application.
[edit] 50
Time: Unknown. Not known to have been attempted or solved, and likely to be worth at least one formal paper.
 Reverse engineer a program without reference to its source code.
 Bonus: Adhere to some variety of "clean room" constraints, such as working without knowledge of the executable contents.
 Solve a Project Euler problem with a Turing machine.
 Bonus: Solve it in under a minute.
 Write a CAPTCHA decoding program.
 Write a formal paper on a computer science topic and submit it to arXiv. Please be aware of arXiv's moderation policies.
 Write a computer science related book.