XKCD-CS

From XKCD Wiki
Jump to: navigation, search

Hello wiki!

Contents

[edit] Topics covered by #xkcd-cs

  • 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 978-0-7356-1967-8 Steve McConnell cypren
The Pragmatic Programmer ISBN 978-0-201-61622-4 Andrew Hunt
David Thomas 		cypren
When Teams Work Best ISBN 978-0-7619-2366-4 LaFasto, Frank M. J., and Carl Larson. Fredd
System-Level Programming Machine Architecture: Things Your
Programming Language Never Told You
N/A
 Herb Sutter cypren
What Every Programmer Should Know About Memory
N/A
 Ulrich Drepper cypren
Linux System Programming ISBN 978-0-59-600958-8 Robert Love cypren
Linux Assembly Language Programming ISBN 978-0-13-087940-0 Bob Neveln cypren
Understanding the Linux Kernel, 3rd Edition ISBN 978-0-59-600565-8 Daniel P. Bovet
Marco Cesati 		cypren
Windows System Programming, Third Edition ISBN 978-0-321-25619-5 Johnson M. Hart cypren
C ISO/IEC 9899
N/A
 ISO/IEC JTC1/SC22/WG14 R.K., IceKarma
The C Book
N/A
 Mike Banahan
Declan Brady
Mark Doran 		R.K.
The C Programming Language ISBN 978-0-131-10362-7 Brian W. Kernighan
Dennis M. Ritchie 		You
C Programming Notes
N/A
 Steve Summit R.K.
C++ C++ FAQs, Second Edition ISBN 978-0-201-30983-6 Marshall Cline
Greg Lomow
Mike Girou 		cypren
C++ FAQ Lite
N/A
Effective C++, Third Edition ISBN 978-0-321-33487-9 Scott Meyers cypren
Exceptional C++
More Exceptional C++
Exceptional C++ Style 		ISBN 978-0-201-61562-3
ISBN 978-0-201-70434-1
ISBN 978-0-201-76042-2 		Herb Sutter cypren

[edit] Programming challenges

[edit] Links

[edit] Source code

[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, "NP-Complete" [25]
    • Bonus: Prove it is not NP-complete.
  • Prove or derive a proposition important to computer science. [25]
  • Find other interesting exercises. [27]

[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() or getrusage().
  • 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 #xkcd-cs with #xkcd-compsci. [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 su)† without recursion or formulas. [35]
    • Bonus: Find the solution in less than 5 su with this approach.
    • Bonus: Minimize the su needed to solve for 128 instead of 100.
† This is not intended to be competitive, but if you would like to compare results, multiply su by 100 and divide by the su 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]
  • 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 raptor-proof 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.
Retrieved from "http://wiki.xkcd.com/wirc/index.php?title=XKCD-CS&oldid=14218"