======Programming I - Labs 2018/2019====== 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 2018/2019 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?tid=2&gl=18aNPRG030x09&fak=11320&skr=2018&sem=1|group]], concretely, by [[http://gamedev.cuni.cz/contacts/|Jakub Gemrot]] Permalink: [[http://bit.ly/mff-uk-prg1-labs-2018]] ---------------------- ======Dates====== Tuesday's labs, 14:00, SW2, Jakub Gemrot: [[mailto:jakub.gemrot@gmail.com|jakub.gemrot@gmail.com]] ---------------------- ======Interesting====== [[https://visualgo.net|VisuAlgo]] - visualization of algorithms including AVL trees! ---------------------- ======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: **18. 12. 2018 / 8. 1. 2019** * **Come up** with an individual **semester project** * Project idea deadline: **3.12.2018** * 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: **17.12.2018** * Use (copy-and-update) the following [[https://drive.google.com/open?id=1ImYy5oSpeOJqeGweRxZb2MgxwvO_cDno4W3UEP5XkEg|template]] * Ideas can be get from Martin Mareš's [[http://mj.ucw.cz/vyuka/zap/|topic examples]] * **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 - 2018 - L[lab number] - [homework name] 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. ---------------------- ======Lab Tests====== * **25.1.2019**, SW2 * [[https://docs.google.com/document/d/1wZR99VlUrhHQnbZnuQx_9JG4Z5sbKeXUdRzVvt4aKds/edit?usp=sharing|Add/Remove in linked lists]] * **18.1.2019**, SW2 * [[https://docs.google.com/document/d/1MqgaNNpdd75YyFFYWcTcYxhEdfIb1bED9AVDqNzk3TM/|Sorting in dynamic structures]] ======Labs History====== ==== Lab 10 ==== * **8.1.2019** * Dynamic Trees, Binary Search Trees, definitions and implications * **PRG1 - 2018 - L10 - BST** * Create a program that will load integer numbers into the binary search tree dynamic structure * Pretty print the result binary tree ==== Lab 09 ==== * **19.12.2018** * Recursion * Fibonacci numbers, Factorial, Tower of Ha-noi, Quicksort * No homework ==== Lab 08 ==== * **12.12.2018** * Dynamic variables, new/dispose, linked lists * Homework in the ReCodEx group (Big Numbers / Fakt dlouhá čísla) ==== Lab 07 ==== * **4.12.2018** * Arrays in Pascal, user types, record, passing the data via value and reference (var) * Homework in the ReCodEx group (Train and the Bridge / Po mostě má přejet vlak) ==== Lab 06 ==== * **27.11.2018** * We have been talking about functions building chain of functions and reusing them, showing the result of function signature changes and how to work around it * Tasks we have been working on, using only functions chr(x) and ord(x) - Is this input a natural number (0 included)? - Does this string contain a natural number (0 included)? - Does this string a whole number? * Homework * **PRG2 - 2018 - L06 - Strings** - 4 programs; deliver them as functions - How many digits this whole number stored in a string is containing? Return -1 if the string does not contain a whole number. - What is the sum of digits in this whole number stored in a string? Return -1 if the string does not contain a whole number. - You are given a string that should contain a whole number; return the number without its first digit. Return 0 if the string does not contain a whole number or the number contains only single digit. - You are given a string, return the same string but convert all lower-case characters into their upper-case variants. * **This exercise has been experimentally assigned to your group in ReCodEx, try to solve this by submitting your solution through ReCodEx!** ==== Lab 05 ==== * **20.11.2018** * We've been going through the 22 small programs and then we will be talking about string handling, procedures and functions * We touched string functions and procedures in Pascal * Examples here: [[https://drive.google.com/open?id=1q5Xw8TtJ-5m0ZujVqhgViyIqhZo3q21J|stringy.pas]] ==== Lab 04 ==== * **23.10.2018** * So we have presented correct lower-estimate for sorting algorithms based on comparison of two numbers, yep O(N log N) is the best we can hope for * But only for a given assumptions, see [[https://cs.wikipedia.org/wiki/Counting_sort|Counting Sort]], for small range of natural numbers, you can have sort with time complexity O(N)! But it's not working in-place, what a pity. * Then I've been showing Pascal language, some bits of Lazarus, and we have a homework! * **PRG1 - 2018 - L04 - Small Programs** * Solve the following [[https://drive.google.com/open?id=0B49ID9s3-zhTbFE2S005N3ZpdEk|22 problems (programs) with a Pascal program]] * If you are an expert, try to solve them with the least number of variables possible ;) * Deadline: next lab... we need to decide when that is going to be * WARNING: 30.10. - immatriculation, 6.11. - Dean's day, 13.11. - I'm in Canada ;( ==== Lab 03 ==== * **16.10.2018** * We talked about time complexity of algorithms, we touched Big-O notation ([[https://cs.wikipedia.org/wiki/Landauova_notace|Landau Notation]]) * I've failed to show you the correct computation of the lower bound for sorting, which we will fix next week * No homeworks folks! Yay! Finish the ones from previous weeks :-) ==== Lab 02 ==== * **9.10.2018** * We did some mind-troubling puzzles again :) * Homeworks - **PRG1 - 2018 - L02 - Install Pascal** - If on Win/Linux - install Free Pascal, compile and run the following [[http://bit.ly/mff-uk-prg1-sumthing|code]] and send me a screenshot - If on Win - install [[http://www.contexteditor.org/index.php|ConTEXT]] and [[http://www.pascalgamedevelopment.com/showthread.php?2376-I-found-the-perfect-IDE-for-Freepascal|configure it]] so you can compile and run the code above from it as well, send me a screenshot (instead of ConTEXT, you can try also PSPad, Notepad++ or Sublime, etc.) - If on Mac - try following [[https://docs.google.com/document/d/1XlP3FcoG1umScLF0s-J-4SexRh6Jn7uHWqkURyRaZkc/edit#heading=h.obhx68nfjgnt|these steps]], compile and run the code above as well, send me a screenshot - **PRG2 - 2018 - L02 - Glasses** * Solve the following problem [[https://docs.google.com/document/d/1ZTuZ6-bdp7djapbhVTvejMlym99FNHec-VuxPb2prS0/|Wizard & Prisoner - Glasses problem]] and send me the solution - **PRG2 - 2018 - L02 - River** * Solve the following problem [[https://docs.google.com/document/d/10BrUuL-JVfHomlnKcKYcOM0P_hm2Cc1l5Yo8S6JBnSw/edit?usp=sharing|River in the park]] and send me the solution * Deadline: 15.10.2018 23:59 ==== Lab 01 ==== * **2.10.2018** * Welcome to Programming! * Some introductory formal / informal info * First batch of homeworks :) - **PRG1 - 2018 - L01 - Login** - Go to [[http://www.ms.mff.cuni.cz/acad/sisal/sisal.html.cz|SISAL]] and create an account for the lab - NEW: test that you can login to some computer in Rotunda using your CAS (SIS) credentials - 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]] - Send me an email with you CUNI number and login to ReCodEx - **PRG1 - 2018 - 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 - 2018 - 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: 8.10.2018 23:59