Infopage about the C++ lab of NPRG041.

• Taught by: Miroslav Kratochvil
• contact: kratochvil@ksi.mff.cuni.cz (please include the course name/code in the subject, e.g. C++)
• Rule of thumb: When in any doubt, mail me.

Groups:

• Czech group: every Wednesday at 10:40 in SU2
• English group: every Wednesday at 17:20 in SU2

Reading material:

• Very probably any good book about C++ will do. There are some in the faculty library. Because MFF students are generally more apprehending than the common programming crowd, I highly suggest you go directly to the Standard . (click on the 2014 Programming Language C++ link in Published standards)
• I maintain a local copy of the C++ standard PDF
• Cplusplus.com — especially following sections:
  • Containers (list, vector, set, map, string, …)
  • Commandline I/O in iostream
  • File I/O and in-memory I/O
  • complex
  • …

Lab requirements#

To get the credit, you have to attend the course reasonably (at least accordingly to your knowledge of the topic), do the homework (see below) and finish an individual project (also below).

You will be assigned several points for finishing the homework. These will be added to the points from the final test, therefore improving your final grade for the whole course. Details are available in the main course slides.

Depending on many factors, students from Erasmus programs may need a completely different set of rules to fit into different time limits. If you are an ERASMUS student, contact us!

Homework#

There are two homework assignments. Please refer to ReCodex.

Project#

Each student has to create an individual project and submit it to get the credit. Topics of the projects may vary wildly, but you should discuss your topic before the end of November so that it is agreed upon. Size of the project is not an issue and largely depends on the topic, around 500 lines of (neat) C++ code is a good guideline (on the other hand, packing the same functionality into a smaller program using e.g. advanced language features is even better).

Bad topics:

• Boring libraries
• Boring games
• Anything that does not behave C++-ish (e.g. code without a single class construction)
• Anything that requires complicated or very specific user interface (e.g. bank account simulator, unless the interface is solved neatly in some novel C++ way)
• Database workalikes, e.g. “evidence of hotel guests”, “evidence of soccer results”, etc.; unless the underlying database storage is somehow interesting.
• Anything that has 100000 implementations already hanging around the internet
• Also, there’s already too many of checkers, worms, tetris, pacman, snake, tictactoe, etc.

Good topics:

• Small fast games (fun!)
• Convenience programming libraries (convenient!)
• Efficient data structures with demos (useful!)
• Physics-like simulations of something (collisions, gravity, particles, etc. look cool)
• Networking (internet!)
• Virtual machines or interpreters for small programming languages.

Deadlines:

• Topic agreed upon, written down in SIS: November 30th, 2019. Send me an e-mail to make sure the topic is confirmed and added to SIS.
• Recommended time for submitting final version: March 2020.
• Final version incl. documentation or example demonstration: April 10th, 2020. If you miss this deadline, we will assume that you are not aiming to obtain the credit. Projects that are first submitted after this deadline will not be evaluated at all. Corrections of previously submitted projects will be still possible.
• UPDATE April 2020: All project deadlines are postponed by exactly +1 month because of the virii everywhere.

Submission:

You must develop and submit the project using git in the corresponding MFF Gitlab group. The submission process is simplified — you just notify me that the project is ready there. Registration to Gitlab is open for all students with valid CAS UK credentials. After you register, let me know to assign you to the group.

Submission guidelines:

• Make the code portable — it should not depend on the platform unless it is, by design, tied to that platform. Windows-specific projects should work on Windows in the computer lab, UNIX projects should work on Linuxes in the computer lab.
• Do not over-engineer, avoid feature creep. The simplest project that satisfies the following conditions will do:
  • There’s a reasonable amount of C++ that shows you know what you’re doing
  • It does not crash, in particular it does not dereference invalid pointers, cause leaks, or torture the memory in any other way.
  • It does not contain any inefficiencies that could be fixed by better C++. (Repeat: const references! avoid manual allocation!)
  • It provably does what the topic says, and it can be demonstrated on an example use-case of reasonable complexity.
  • The code has sufficient comments. If you are unsure if you should add comment somewhere, try to tear the surrounding program block or function out of context, and ask yourself if anyone can still fully understand what it does (and why). If not, it needs comments.
  • If the topic is a data structure, include a comparison with a naive approach or some C++ counterpart (std::chrono provides timers). Note that your data structure does not need to “win” the comparison (that’s the topic of the HPC course). You should only provide a reasonable testing framework to assess the performance.
• Having received your program, I should be able to convince myself that it works in less than around 15 minutes. You can help it a lot:
  • Include a file INSTALL (.md) that describes how to make it work on a fitting computer configuration. (Better: How to make it work on computers in MFF’s computer lab. Best: Add a Makefile that works in the lab.)
  • Include a file DEMO or TUTORIAL that describes what should I do with the compiled program to see all the important functionality as quickly as possible. (Better: add a shell script that does it. Best: Support make demo)
  • If the DEMO requires some data for the demonstration, include it! (Advice: If I’m forced to create testing data by hand, it will take more than 15 minutes. Also, result will contain lots of hideous corner cases.)
  • If the source code is big, include INTERNALS file that describes which parts of the functionality can be found in which part/file of the code. This is sometimes also called “programmer documentation” or “hacking guide”. Imagine it as a signpost, compare with artist’s impression thereof.
  • If all documentation parts are favorably small, pack them together into one README.

Lab timeline#

Source code from the labs will be available here.

1 October 2nd#

Slight introduction into C, basic data types and a bit of pointers.

2 October 9th#

Manual memory management, linked lists, more pointers. A look on what’s happening during the compilation.

3 October 16th#

C++ introduction — references and const references, overloading, templates.

4 October 23th#

C++ objects are resources, working with strings.

Danger: the source code produced in the lab contains some mistakes (esp. regarding the empty strings as null pointers). I have added comments in several places I noticed that are obviously missing the null check. Also, you will find

5 October 30th#

Fun with STL and containers.

6 November 6th#

More STL, more iterators.

7 November 13th#

Run-time polymorphism and virtual methods; a zoological example with animals.

8 November 20th#

Using small proxy classes as helpers for creating various functionality that is not directly supported in C++, namely properties and safe references.

9 November 27th#

Parsing volume 1: Tokenization + a parser of a small language. Languages and ASTs are a nice practice for working with smart pointers and classes behind a virtual interface.

The parser we used is a recursive descent parser, which is not a very good choice for C++, but it is the simplest type of the “generic” parsers. Other choices with less straightforward representation of the grammar include e.g. Earley parser, CYK, LL or shift-reduce parsers that are used for most programming languages.

10 December 4th#

Parsing volume 2.

Bonus material#

• The Art Of UNIX Programming (online version) by E.S.Raymond is a brilliant material not only about the origins of current computing practice and the C programming language (that emerged together with UNIX and gave rise to C), but also contains almost all the most important insights about software development gained in last 50 years. Surprisingly, all of them still apply. Sometimes a bit philosophical. If you are developing a large system (or a part of some) for the first time, this book will tell you what design mistakes you are almost certainly going to make, what are they called, and how to avoid them.
• Software speed rule: more efficient programs are faster for free. Mostly because some quite well-accepted truths from theoretical computer science simply do not hold on real hardware. The most striking (and interesting) fact is sometimes described as The myth of RAM.
• Doug Lea’s Malloc — a webpage about the original default allocator of most C/C++ libraries, which makes an extremely good read about allocators. (anyway — you probably use that guy’s code several times per second just by silently watching this website)
• If you would like to create a game for the semestral project and have no idea where to start with the graphic output, try OpenGL. There are lots of ways to get an OpenGL viewport for your program, the easiest of them is probably the GLUT library. You might also want to see SDL that is traditionally used for portable games, or a newer alternative SFML. Following sites provide a good introduction to modern OpenGL: https://open.gl/ and https://learnopengl.com/.
• If you would like your game to be a bit more advanced (and save yourself a lot of coding), use a graphics/game engine like Magnum (from a former MFF student), Ogre3D or Urho3D.
• If you like template programming but the syntax seems unwieldy, use this

…