======Programming I - Labs 2019/2020====== This page contains materials for the practice lessons of the [[https://is.cuni.cz/studium/predmety/index.php?tid=&do=predmet&kod=NPRG030|Programming I (NPRG030)]] course that is being/has been taught during winter semester 2019/2020 at [[http://www.mff.cuni.cz/|Charles University]] in [[http://www.praha.eu/jnp/cz/home/magistrat/index.html|Prague]], Czech Republic. The course official web page is/was to be found at Tomáš Holan's [[http://ksvi.mff.cuni.cz/~holan/|webpage]]. The practice lessons (labs) are/were backed by many, for this [[https://is.cuni.cz/studium/rozvrhng/roz_predmet_gl.php?gl=19aNPRG030x09&fak=11320&skr=2019&sem=1|group]], concretely, by [[http://gamedev.cuni.cz/contacts/|Jakub Gemrot]] Permalink: [[http://bit.ly/mff-uk-prg1-labs-2019]] ---------------------- ======Dates====== Monday's labs, 15:40, SW2, Jakub Gemrot: [[mailto:jakub.gemrot@gmail.com|jakub.gemrot@gmail.com]] ---------------------- ======Interesting====== [[https://visualgo.net|VisuAlgo]] - visualization of algorithms including AVL trees! [[https://www.puzzleprime.com|Puzzle Prime]] - great box of puzzles (kudos to Simon Williams who brought this up) ---------------------- ======How to pass the labs====== * Max **TWO absences** * Do **ALL homeworks** I give you * Almost no excuses here, it has very good motivation I('ll) share during the first lab * Pass a **lab exam** * Two dates: **16. 12. 2019 / 6. 1. 2020** * **Come up** with an individual **semester project** * Project idea deadline: **2.12.2019** * Describe what you would like to create in 3-10 sentences and send it to [[mailto:jakub.gemrot@gmail.com|jakub.gemrot@gmail.com]] * Description deadline: **16.12.2019** * Use (copy-and-update) the following [[https://drive.google.com/open?id=1ImYy5oSpeOJqeGweRxZb2MgxwvO_cDno4W3UEP5XkEg|template]] * You can get inspired at web pages of my colleagues: * [[https://www.ms.mff.cuni.cz/~forstova/pgmZ/Zapoctaky.html|Lenka Forstová]] * [[https://www.ms.mff.cuni.cz/~dvoram30/zapoctak.html|Martin Dvořák]] * [[http://mj.ucw.cz/vyuka/zap/|Martin Mareš]] * [[http://www.ms.mff.cuni.cz/~zemlicka/vyuka/NMIN101/namety/|Michal Žemlička]] * **Deliver a semester project** * Delivery deadline: "up-to-you" = to be negotiated :) * Apart from the implementation you will also have to create user's manual and programmer's manual * [[https://drive.google.com/open?id=1dkn6TmHeqm37TeEXAJ_0CipW3ThnWRVa-f9aGq5EzlM|User's manual guidelines]] * [[https://drive.google.com/open?id=1PeRXbtEoPiDQpm291ol9iMMc_0of2FxSdVaD8EeU3og|Programmer's manual guidelines]] * Follow [[https://drive.google.com/open?id=1sraaknvWJtWYsTrSFyw7whwtxRtRspY1q-iHaf89ttg|delivery guidelines]] when submitting your work ---------------------- ======Submitting homeworks====== Send me an email ([[mailto:jakub.gemrot@gmail.com|jakub.gemrot@gmail.com]]) containing a link where I can download your homework / project. Ideally use [[https://www.dropbox.com/|DropBox]] or [[https://onedrive.live.com/about/cs-cz/|One Drive]] or [[https://wetransfer.com|WeTransfer]]; from time to time I have problems downloading files from GDrive (they are having wild JavaScripting that gets blocked by my filters occasionally). Always use subject: PRG1 - 2019 - L[lab number] - [homework name] Example: PRG1 - 2019 - L01 - Recodex The subject is crucial! My mailbox is often overflowing and I have to process emails in batches - at these times, I'm searching for your homeworks via subject names. ---------------------- ======Labs History====== ==== Lab 09 ==== * **16.12.2019** * As promised, this lab will be about fun stuff! * [[https://github.com/pyglet/pyglet|Pyglet]] - Python layer over [[https://www.libsdl.org/|SDL]], uses OpenGL for rendering * Example game: [[https://drive.google.com/open?id=1bbnqBkGEOn9EQPT3Dd1MlWlyYuvaJOc6|Paddle]] * [[https://drive.google.com/open?id=1jLK4JA1kGL20SgpXIf5xFpXlGgcFvKfo|Paddle Reloaded]] * This is advanced version of Paddle that contains sounds, moving brick, ball that is getting faster every brick hit and it is also changing a color for a bit every hit * Beware, you have to change paths into sounds.py in order to run it in your context! * You will need Pyglet installed: pip install --upgrade pyglet --user * [[https://pyglet.readthedocs.io/|Pyglet documentation]] * Stuff we are going to use: * [[https://pyglet.readthedocs.io/en/stable/programming_guide/graphics.html#drawing-primitives|Drawing in OpenGL]] * [[https://pyglet.readthedocs.io/en/stable/programming_guide/time.html#guide-calling-functions-periodically|Game loop tick]] * [[https://pyglet.readthedocs.io/en/stable/programming_guide/keyboard.html|Reading the keyboard]] * [[https://pyglet.readthedocs.io/en/stable/programming_guide/text.html|Displaying text]] * [[https://easings.net/en|Easing functions]] * [[https://gamedev.stackexchange.com/questions/73920/what-are-easing-functions|More in this thread on stackexchange]] * Homework * **PRG1 - 2019 - L09 - Paddle** * Do at least one thing from the following: - Implement (at least one) power-up(s), e.g.: bigger ball, faster ball, bigger paddle, faster paddle, etc. - Implement 3 different level layouts: level 1 - checkerboard, level 2 - circle, level 3 - full brick wall (standard) - Implement (at least one additional) brick type, e.g.: non-destroyable, needs-to-be-hit-twice, ball-slowing, ball-fasting, random direction bounce, etc. ==== Lab 08 ==== * **9.12.2019** * [[https://docs.google.com/document/d/1MtFmYcgQU70m_rdXXQF6RsTJ1cYtLqsOZmUoWDWwyVk/edit|Python Q&A]], Algorithmization * Homeworks * **PRG1 - 2019 - L08 - Train crossing the bridge** * [[https://docs.google.com/document/d/1ZawfjIM881pHPWRuNb6Uku3Am9rT1K1P43GVmsKT2aM/edit?usp=sharing|Assignment]] * We will need a [[https://en.wikipedia.org/wiki/Circular_buffer|circle buffer]] (a.k.a. circular queue) for that * **PRG1 - 2019 - L08 - Reusable ids** * [[https://docs.google.com/document/d/1zKVEAQg8EB1ZFSaa77wgqWgTIe42rJ2Zy4fNrUjwtBo/edit?usp=sharing|Assignment]] * You will need to know what [[https://en.wikipedia.org/wiki/Linked_list|linked lists]] are in order to solve this ==== Lab 07 ==== * **25.11.2019** * Leftovers! * [[https://docs.python.org/3/reference/datamodel.html#object.__radd__|Reversed operands]] * E.g.: if __add__ fails for the left operand, __radd__ is tried on the right one * [[https://docs.python.org/3/tutorial/errors.html|Exceptions, raising, trying, catching]] * [[https://www.programiz.com/python-programming/inheritance|Class inheritance]] * [[https://docs.python.org/3/tutorial/classes.html#private-variables|Private class variables]] * "Private methods" are not correct in Python context, these are just scrambled names, [[https://stackoverflow.com/questions/70528/why-are-pythons-private-methods-not-actually-private|stackoverflow discussion]] * [[https://www.programiz.com/python-programming/methods/built-in/staticmethod|staticmethod]], [[https://www.programiz.com/python-programming/methods/built-in/classmethod|classmethod]] * [[https://drive.google.com/open?id=1Hi6ljyEJ1Vh7IvleYqRZNeW0EPxShkHs|Some Vector.py example]] * [[https://realpython.com/primer-on-python-decorators/|What are those decorators anyway?]] * [[https://www.programiz.com/python-programming/function-argument|Default argument values and keyword arguments]] * [[https://realpython.com/python-kwargs-and-args/|Arbitrary arguments and keyword arguments]] * [[https://packaging.python.org/tutorials/installing-packages/|Packages in Python (pip)]] * Example: [[https://python-graph-gallery.com/132-basic-connected-scatterplot/|plots]] * Just open command line ([[https://www.howtogeek.com/235101/10-ways-to-open-the-command-prompt-in-windows-10/|in Win]]), navigate ([[https://www.digitalcitizen.life/command-prompt-how-use-basic-commands|in Win]]) to folder of your Python installation, into its Script directory, and then type: pip install * E.g.: pip install matplotlib * Python OOP "Example" File * [[https://drive.google.com/open?id=10b4QelybQNriESu3IHoMO9lS_fLeumrt|Python OOP Fun]] * Homework * **PRG1 - 2019 - L07 - Sorts** * Implement BubbleSort, HeapSort and QuickSort * Implement timing decorator (or use one) * Gather running time of sorting algorithms for arrays of size 1 ~ 10.000.000 (step: *2 ... 1, 2, 4, 8, ...) * Use [[https://docs.python.org/3/library/random.html|random number generator]] for that * Plot running times using scatter plot ==== Lab 06 ==== * **18.11.2019** * Revisiting modules again (finishing the Lab 05 story) * Classes and Objects! * Excellent [[https://realpython.com/python3-object-oriented-programming|Intro to Classes and Objects]] on realpython.com * Important built-in methods: [[https://docs.python.org/3/library/functions.html#isinstance|isinstance]] and [[https://docs.python.org/3/library/functions.html#issubclass|issubclass]] * Another tutorial, which is mentioning important [[https://www.tutorialspoint.com/python/python_classes_objects.htm|built-in class attributes]] as well as getatts(), setattr(), delattr() functions, member hiding and others * [[https://www.geeksforgeeks.org/operator-overloading-in-python/|Operator overloading]] on geeksforgeeks.com * Homework * **PRG1 - 2019 - L06 - ImLib** * Create your own class for holding value of a complex number * Implement add, sub, mul operators * Implement greater/less then relations (compare real component first, then imaginary) * Implement negation operator * Provide interoperability with Python number types (int and float) wrt. to operators/relations above ==== Lab 05 ==== * **11.11.2019** * Modules and packages * [[https://www.learnpython.org/en/Modules_and_Packages|on learnpython.org]] * [[https://docs.python.org/3/tutorial/modules.html|official docmentation]] * I highly recommend you to read this through completely * List of [[https://docs.python.org/3/py-modindex.html|Python built-in modules]] * Recursion! * What it is, how to use it * [[https://docs.python.org/3/library/os.html#module-os|os module]] * Homework * **PRG1 - 2019 - L05 - Compute dir size** * create a program that will recursively sum the size of all files within a given folder and its subfolders * [[https://www.tutorialspoint.com/python/os_fstat.htm|Quick intro to os]] and os.fstat ==== Lab 04 ==== * **4.11.2019** * More from [[https://www.learnpython.org]] * [[https://www.learnpython.org/en/List_Comprehensions|List Comprehensions]] * [[https://www.pythonforbeginners.com/basics/list-comprehensions-in-python|List comprehensions explained]], I prefer this one as it starts with the semantics first * [[https://www.learnpython.org/en/Dictionaries|Dictionaries]] * [[https://www.guru99.com/python-dictionary-beginners-tutorial.html|Exhaustive dictionary tutorial]] * .keys() and .items() are important! * [[https://stackoverflow.com/questions/1602934/check-if-a-given-key-already-exists-in-a-dictionary|How to check if some key is already defined within a dictionary]] * [[https://www.learnpython.org/en/Map%2C_Filter%2C_Reduce|Map, Filter, Reduce, lambdas]] * [[https://realpython.com/python-lambda/|More on lambda functions here]], again this is more thorough explanations what lambda functions are (including theoretical background!) * [[https://www.programiz.com/python-programming/anonymous-function|Using lambda with map()]] * [[https://www.python-course.eu/python3_lambda.php|More lambdas with map, filter, reduce]] * Here is the official documetation on [[https://docs.python.org/3/library/functions.html|Python built-in functions]] * More topics * [[https://data-flair.training/blogs/python-data-structures-tutorial/|Lists vs. Tuples]] * Reading and writing files - [[https://www.guru99.com/reading-and-writing-files-in-python.html|source 1]], [[https://www.digitalocean.com/community/tutorials/how-to-handle-plain-text-files-in-python-3|source 2]] * [[https://docs.python.org/3/howto/sorting.html|Sorting]] * [[https://www.geeksforgeeks.org/python-sort-python-dictionaries-by-key-or-value/|Sorting dictionaries]] * Homework * **PRG1 - 2019 - L04 - File stats** * Ask user for a path to a some text file * As an example files you can use the following [[https://www.gutenberg.org/ebooks/84|book]] * Read the file and: - Print the number of words within the file * a word is a sequence of non-whitespace symbols - Find and print the most frequent word(s) - Print average frequency of words - Find and print the words of frequency nearest to the word frequency median - Find and print the least frequent word(s) * Deadline: 10.11.2019 23:59 * Optional fun * Try to revisit homeworks from 02 and rewrite them with at least number of lines possible ==== Lab 03 ==== * **21.10.2019** * Intro continues :-) * We will be playing with * [[https://www.programiz.com/python-programming/methods/built-in/ord|ord]] and [[https://www.programiz.com/python-programming/methods/built-in/chr|chr]] functions * Custom [[https://www.learnpython.org/en/Functions|function definitions]] * We will need some [[https://docs.python.org/3/library/stdtypes.html#string-methods|string built-in methods]] * **Homework is in Recodex!** * There are following assignments in order, which is advised to implement them in - 5P 0.2 Hello World 2 - Caesar cipher - Is a number symmetric in Python? - Prime factorization - Součet řady celých čísel - Maximum value in a sequence (with occurrences) in Python - Bases ==== Lab 02 ==== * **14.10.2019** * Intro to Python! * How to install Python + Visual Studio Code + Run the first program ([[https://drive.google.com/open?id=1DpVDlIzgf5Fq7lqwpbXfXCyzrauiKUnl|PDF]]) * We are using [[https://www.learnpython.org]] * [[https://www.learnpython.org/en/Hello%2C_World%21|Hello World]] * [[https://www.learnpython.org/en/Variables_and_Types|Variables and Types]] * Note [[https://www.programiz.com/python-programming/methods/built-in/isinstance|isinstance]] * Note [[https://www.geeksforgeeks.org/difference-operator-python/|'is' operator]] * [[https://www.learnpython.org/en/Lists|Lists]] * Plus [[https://www.learnpython.org/en/Basic_String_Operations|slicing]] (exemplified on strings) * Plus some [[https://www.tutorialspoint.com/python3/python_lists.htm|extra list methods]] * [[https://www.learnpython.org/en/Basic_Operators|Basic Operators]] * [[https://www.learnpython.org/en/String_Formatting|String formatting]] * [[https://www.learnpython.org/en/Conditions|Conditions]] * [[https://www.learnpython.org/en/Loops|Loops]] * And how to read [[https://www.geeksforgeeks.org/taking-input-in-python/|input from console]] * Note that input is always string, so you have to cast it to, e.g., int if you want a number * In hope user has actually typed a number ... but that's another story * Second batch of homeworks :) - **PRG1 - 2019 - L02 - First Pythons** * Do the first [[https://drive.google.com/open?id=1_D7eDLBhiG0TepmHfFPveEs5l41zZ9IP|22 programs in Python]] * Deadline: 20.10.2019 23:59 ==== Lab 01 ==== * **7.10.2019** * Welcome to Programming! * Some introductory formal / informal info * First batch of homeworks :) - **PRG1 - 2019 - L01 - Recodex** - Create an account in [[recodex.mff.cuni.cz|ReCodEx]]; this can be done **IF AND ONLY IF** you have entered your email adress into the [[https://ldap1.cuni.cz/|CAS]] * [[http://www.ms.mff.cuni.cz/ReCodEx/NewUserDoc.pdf|Recodex for New Comers]] * [[http://www.ms.mff.cuni.cz/ReCodEx/StudentDoc.pdf|Recodex Cookbook for Students]] - Send me an email with you CUNI number and login to ReCodEx - **PRG1 - 2019 - L01 - Prisoners** * Solve the following problem, [[https://docs.google.com/document/d/1a6aQPVg6SSwLWC-q6ua3FKNKGSlNyHdS1l3Et7KMl5o/edit?usp=sharing|Prisoners]], and ideally (but optionally) prove that your solution is working - **PRG1 - 2019 - L01 - Coins** * Solve the following problem, [[https://docs.google.com/document/d/1NnabyT3LzNw6wfskJ6C2kjjlITzmGFZyyVzWY8bgh9s/edit?usp=sharing|Wizard & Prisoner - Coins]], in a way that the description also serves as a proof that your algorithm is working * Deadline: 13.10.2019 23:59