Introduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "## Topics\n",
    "- computer science fundamentals\n",
    "- problems, algorithms and programs\n",
    "- programming languages\n",
    "- C++ language and C++ program development steps\n",
    "- setting up development and learning environments\n",
    "- the first program and its anatomy\n",
    "- errors and debugging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Computer science (CS) fundamentals\n",
    "- the core is a disciplined ability to be logical and creative in a pragmatic way to solve problems in varieties of disciplines\n",
    "- CS is a newer discipline that burrows from Mathematics, Engineering, and Natural Science\n",
    "- like mathematicians, computer scientist use formal languages to denote ideas (esp. computation)\n",
    "- like engineers, they design things, assemble components into systems and evaluate tradeoffs among alternatives\n",
    "- like scientists, they observe the behavior of complex systems, form hypothesis, and test predictions\n",
    "\n",
    "- **the single most important skill for a computer scientist is problem-solving mostly writing computer programs**\n",
    "- the goal of this course is to teach you how to think like a computer scientist\n",
    "- computer scientists primary job revolves around problems, algorithms and programs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems, Algorithms and Programs\n",
    "\n",
    "### Problem\n",
    "- we deal with and solve a lot of problems in every walk of lives\n",
    "- problem is a question raised for inquiry that someone needs to answer or find solution to\n",
    "- computer scientists typically deal with computational problems\n",
    "- can be as simple as: \n",
    "    - what is the sum of 9 and 999?\n",
    "- or can be as complicated as:\n",
    "    - what is the shortest path from San Francisco, California to New York City, New York?\n",
    "- one must understand the problem, analyze the requirements, constrains and assumptions in order to correctly solve the problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm\n",
    "- once the problem is formulated and well analyzed, computer scientists work on algorithm\n",
    "- step by step process/task to solve a given problem\n",
    "    - like a recipe for a food menu\n",
    "- typically written in human language or pseduo-code (in between)\n",
    "- e.g. problem: How can your martian friend buy grocery on earth?\n",
    "- you should be able to help solve this problem given you live on earth and shopped groceries many times\n",
    "    - in other words, you're the domain expert\n",
    "- algorithm steps:\n",
    "    1. Make a shopping list\n",
    "    2. Drive to a grocery store\n",
    "    3. Park your car\n",
    "    4. Find items in the list\n",
    "    5. Checkout\n",
    "    6. Load grocery\n",
    "    7. Drive home\n",
    "- there's a lot of details missing from these steps\n",
    "    - it's a good start and can be refined by drilling each step further down"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Program\n",
    "- once the algorithm steps are finalized, programmers can convert them into computer instructions\n",
    "- sequence of instructions that specifies how to perform a computation using computers\n",
    "    - computation can be mathematical (solving system of equations), symbolic computation (searching and replacing text in a document, scientific simulations), etc.\n",
    "- the instructions (or commands or statements) look different in differnt programming languages, but the basic fundamental concepts are the same\n",
    "- some fundamental concepts that make up a computer program regardless of the language are:\n",
    "    1. data/values and variables\n",
    "    2. input\n",
    "    3. output\n",
    "    4. math\n",
    "    5. conditional (logical) execution\n",
    "    6. repitition\n",
    "\n",
    "![](resources/BuildingBlocks.png)\n",
    "\n",
    "### data and variables\n",
    "- program works with data (called values) which must be stored in computer memory; variables are names given to memory locations to store values\n",
    "\n",
    "### input\n",
    "- get data from keyboard, a file, or some device\n",
    "\n",
    "### output\n",
    "- display data/answer on screen, or save it to file or to a device\n",
    "\n",
    "### math\n",
    "- basic mathematical operations such as addition, subtraction, multiplication, etc.\n",
    "\n",
    "### conditionals\n",
    "- test for certain conditions or logics and execute appropriate sequence of statements\n",
    "\n",
    "### loops\n",
    "- perform some action repeatedly, usually with some variation every time\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Programming languages\n",
    "- programming langugage is a formal language used to create computer program\n",
    "- there are dozens of programming languages\n",
    "\n",
    "### Types of programming languages\n",
    "### High-level languages\n",
    "- languages that are disigned to be programmer friendly hiding all the details\n",
    "    - C++, Java, C, FORTRAN, Python, PhP, JavaScript, Rust, etc.\n",
    "- advantages: \n",
    "    - simpler; easier to learn and write\n",
    "    - shorter and easier to read\n",
    "    - programs are portable; can run in differnet machines with a few or no modifications\n",
    "- disadvantages:\n",
    "    - translation to machine code can take some time\n",
    "    - slower to run if the translation is not optimal\n",
    "\n",
    "\n",
    "### Low-level languages\n",
    "- machine language e.g., Assembly language\n",
    "- loosely speaking: computers can only execute programs written in low-level languages\n",
    "- programs written in a high-level languages must be translated before they can run\n",
    "- advantage: \n",
    "    - prgrams run faster\n",
    "- disadvantages:\n",
    "    - harder to learn and write code (need to know very low level details about computers)\n",
    "    - programs are not portable; usually need to rewrite for each kind of machine architecture\n",
    " \n",
    "\n",
    "## Ways to translate high level programs\n",
    "- there are two ways to translate high level programs: **intrepreting** and **compiling**\n",
    "\n",
    "### intrepreting\n",
    "- an interpreter reads a high-level program and does what it says\n",
    "- it translates the program line-by-line alternately reading lines and carriying out commands\n",
    "- Python, PhP, JavaScript are intrepreted languages\n",
    "\n",
    "![](resources/Intrepreter.png)\n",
    "\n",
    "### compiling\n",
    "- a compiler reads a high-level program and translates it all at once into byte code before executing any of the commands\n",
    "- compilers check for syntax/grammers of languages\n",
    "- the byte code or binary program must be then loaded into memory to execute\n",
    "- C++, C, Rust, Java, FORTRAN are compiled programming languages\n",
    "\n",
    "![](resources/Compiler.png)\n",
    "\n",
    "## C++ Programming language\n",
    "- C++ is one of the most popular general pupurpose programming languages - see [tiobe index](https://www.tiobe.com/tiobe-index/)\n",
    "- high level, compiled language\n",
    "- extension of C programming language\n",
    "    - same syntax; burrows all C libraries and supports class (object oriented programming, OOP)\n",
    "- you can use all the C libraries and features in C++\n",
    "- designed for system programming and embedded, resource-constrained software and large systems with performance, efficiency, and flexibility\n",
    "- see Wikipedia entry for history and other details: - https://en.wikipedia.org/wiki/C%2B%2B\n",
    "- official C++ reference site https://en.cppreference.com/w/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem solving using C++\n",
    "- C++ is one of many tools computer scientists use to solve problems\n",
    "- learning and being proficient using your tools are important\n",
    "- ultimate goal is to learn problem solving like comupter scientists\n",
    "    - writing code, though important, is a small part of problem solving\n",
    "    - programmers spend about 20% of their time developing code\n",
    "- program design and development requires many steps \n",
    "    - a major part of software engineering process\n",
    "    \n",
    "### C++ development steps\n",
    "- a simple high-level approach to developing C++ programs is depicted in the following figure\n",
    "![](resources/CPPDevelopment.png)\n",
    "\n",
    "#### Step 1: Define problem\n",
    "- figure out what problem you are trying to solve\n",
    "- it may be be just an idea or a fully researched problem statement\n",
    "    1. write a program to find the average temperatures in the USA over the last decade\n",
    "    - write a program that checks if a given string is a palindrome\n",
    "    - write a program that finds the shortest path from New York City to San Francisco\n",
    "    - design and develop a system for Mars rover\n",
    "    \n",
    "#### Step 2: Analyze problem\n",
    "- really understand the scope and all the parameters of the problem\n",
    "- gather all the requirements, outline any assumptions, input and output constraints, etc.\n",
    "    - let's say you want to solve the temperature problem #1 defined in step 1\n",
    "    - how'd you get the temperatures data? would you include all 50 states?\n",
    "    - what if there's no temperature data for some states? are you going to average out the states and then find the average of the average?\n",
    "    - are there any outliers, how'd you handle those?\n",
    "\n",
    "#### Step 3: Design solution\n",
    "- determine \"how\" you'd actually solve the problem\n",
    "- many ways to solve a problem; look into tradeoffs e.g. efficiency vs cost, etc.\n",
    "    - often simple and straight forward solutions are better ones\n",
    "- break the problem into smaller modules or sub problems\n",
    "    - write algorithm steps for each sub problem\n",
    "    - modular solution is easier to update, expand, and reuse without affecting other parts\n",
    "- design mockups; draw system design\n",
    "    - explain how various modules and components interact with each other\n",
    "    - helps address any assumptions made or limitations\n",
    "\n",
    "#### Step 4: Implement solution\n",
    "- write the program using a programming language \n",
    "    - use C++ in this course\n",
    "- programmers spend only about 20% of their time writing code\n",
    "- need a computer with a text editor or an Integrated Development Environment (IDE)\n",
    "    - depends on the system: Windows, Linux, Mac, etc.\n",
    "- a good code editor or IDE typically provides\n",
    "    - way to organize project with multiple files and resources\n",
    "    - syntax highlighting, color coding, line numbers, easy way to compile, run and debug code\n",
    "\n",
    "#### Step 5: Build program\n",
    "- this is tpically a two-step process:\n",
    "    1. compile C++ code in object or byte code\n",
    "        - a project/program may contain many c++ files and header files (.cpp, .cc, .h file extensions)\n",
    "        - each C++ source file gets converted into object file (typically have .o extension)\n",
    "    2. link object files and libraries\n",
    "        - program called linker combines or links together all the object files and C++ standard library and any other libraries used into one single executable program\n",
    "- modern compilers (e.g. g++) can do both the steps at once\n",
    "- **Makefile** is a better way to build C/C++ programs\n",
    "    - a bash like script that simplifies a lot of step for building programs over and again\n",
    "    - learn about makefile from these tutorials:\n",
    "        - https://makefiletutorial.com/\n",
    "        - https://www.cs.bu.edu/teaching/cpp/writing-makefiles/\n",
    "\n",
    "#### Step 6, 7, and 8: Execute, Test, and Debug Program\n",
    "- you must execute or run the program to test it\n",
    "- a program called loader loads the executable into main memory RAM (Random Access Memory)\n",
    "    - CPU (Central Processing Unit) does the actual computation\n",
    "- testing ensures you're getting right results under all the assumptions\n",
    "- programmers may spend a lot of time testing their own programs or others'\n",
    "    - counter intuitively, you try to break your own program!\n",
    "- if bug or error exists, you need to pin point it and correct it\n",
    "    - build the program again repeating from step 5 as many times as required\n",
    "- two common ways to test your program for correctness; learn both in this course!\n",
    "    1. manually run and feed input data and compare the results with the expected answers\n",
    "    - write test cases and test your program automatically using code\n",
    "    \n",
    "\n",
    "#### Step 9: Deploy program\n",
    "- deliver or deploy your program in production environment\n",
    "    - given your program meets all the requirements, passes rigorous testing, etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A C++ Program\n",
    "- following is a complete C++ program that compiles and runs but doesn't produce any results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "int main()\n",
    "{\n",
    "    // C++ code goes here...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The First Program\n",
    "\n",
    "- traditionally, \"hello world\" is the first program one writes to learn coding in any given language"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "/*=================================================\n",
    "  Hello World program\n",
    "  Author: Ram Basnet\n",
    "  Date: June 24, 2020\n",
    "  Copyright: MIT License\n",
    "  \n",
    "  The program prints \"Hello World!\" on the console\n",
    "===================================================*/\n",
    "\n",
    "// include required libraries/header files\n",
    "#include <iostream>\n",
    "\n",
    "// one main function is always required in a C++ program\n",
    "int main() // main entry to the program \n",
    "{\n",
    "    // output Hello World!\n",
    "    std::cout << \"Hello World!\" << std::endl;\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Structure of a C++ program\n",
    "- C++ program may constitute one or many plain-text files \n",
    "    - typically header and source files\n",
    "- each C++ file contains various C++ statements, instructions and codes\n",
    "- C++ source file typically has these extensions: `filename.cpp` or `filename.cc`\n",
    "    - avoid spaces in file and folder names\n",
    "- C++ program must have one file with the **main( )** function\n",
    "    - **int main()** is the main entry of the program\n",
    "    - computer starts executing instructions top to bottom starting from **main()**\n",
    "    \n",
    "- C++ file typically contains:\n",
    "    - **program description**\n",
    "        - brief information about the program and prorammer, copyright info\n",
    "        - these are comments meant for programmers/readers\n",
    "        \n",
    "    - **libraries**\n",
    "        - include the librabires (header files) that are only required\n",
    "        - libraries provide built-in codes that programmers can use\n",
    "        - programmers don't have to write all the basic, details and common tasks\n",
    "            - so, they can focus on solving problems\n",
    "        - libraries are mandatory for many common tasks such as input and output\n",
    "        \n",
    "    - **comments**\n",
    "        - comments are ingnored by the C++ compiler\n",
    "        - comments are for programmers to explain the thought process, subtle code blocks\n",
    "        - it's best practice to write adequate notes as comments, esp. when learning\n",
    "        - makes it easy to read and understand code without actually having to run and decode the code\n",
    "        - *write code for others to read*\n",
    "        - `//` - double forward slashes is used for single line comment\n",
    "        - `/*` everything within are comments; used for multi-line comments `*/`\n",
    "        \n",
    "    - **instruction codes**\n",
    "        - tells computer what to do!\n",
    "        - code composed of keywords, identifiers, symbols, literal values, etc.\n",
    "            - when put together following the language's grammer solves the problem\n",
    "        - block of codes appear within squiggly-braces `{ }`\n",
    "        - statements end with a semi-colon ( `;` )\n",
    "        \n",
    "    - **white spaces**\n",
    "        - indentations, extra spaces and blank lines are typically ignored by the compiler unless necessary\n",
    "        - adequate white spaces are required as a best practice for readability of code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Setting up C++ development environment\n",
    "\n",
    "- setting up a good development environment and getting familiar with it can make you an efficient learner and problem solver\n",
    "- dev environment may depend on various factors: personal preference, available resources, project, etc.\n",
    "- see [this note](./DevEnvironmentSetup.ipynb) for recommended C++ Dev Environment\n",
    "\n",
    "### Compiling C++ programs using g++ and Makefile\n",
    "- modern integrated development environemt (IDE) makes it very easy to compile, build and deploy C++ programs\n",
    "- however, the abstraction and easyness they provide may hide some of the important steps beginner programmer should know\n",
    "- the compilation process using Makefile is highly recommended for both beginners and the professionals in the field\n",
    "- see the basic tutorial and examples on how to create and use Makefile [here](Mailefile.ipynb)\n",
    "\n",
    "### Compile and run hello world program\n",
    "- write a program that prints \"Hello World!\"\n",
    "- compile and run the program on your system\n",
    "- see the example `helloworld.cpp` program found in [demos/intro/](demos/intro/)\n",
    "- run the provided Makefile using a terminal assuming you're using g++ and Makefile\n",
    "    - must `cd` into the folder that contains the Makefile\n",
    "\n",
    "```bash\n",
    "make\n",
    "make run\n",
    "make clean\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using Jupyter Notebook as Teaching and Learning Environment\n",
    "- setting up Jupyter Notebook program is only required if you're teaching/learning C++ interactively\n",
    "- all these notes and corresponding pdfs are created using Jupyter Notebook program\n",
    "- see [this page](JupyterNotebookSetup.ipynb) for setting up and using Jupyter Notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Kattis Online Problem Bank and Judge\n",
    "- throughout the chapters provided in these notebooks, you'll find Kattis Problems section \n",
    "- you can use the knowledge and skills learned to challenge and solve myriad of problems as exercises\n",
    "- see [this notebook](Kattis.ipynb) for more on Kattis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Testing and debugging\n",
    "- programs often contains many types of errors called bugs\n",
    "- programmers spend majority of their time in testing their programs, finding bugs and getting rid of them\n",
    "- the process of finding and correting bugs is called debugging\n",
    "- many IDEs provide a way to step through the code and examine memory as the program executes\n",
    "- the key to finding and fixing bugs is testing \n",
    "    - exhaustive testing makes sure program provides correct output for all sets of input\n",
    "\n",
    "### Types of errors\n",
    "- there are three major types of bugs: syntax, run-time and semantic\n",
    "\n",
    "#### Compile-time errors\n",
    "- also called syntax errors or grammatical errors\n",
    "- computer languages are formal languages with strict grammer to a semicolon\n",
    "    - Natural languages (English, e.g.) are full of ambiguity, redundancy and literalness (idioms and metaphors)\n",
    "- compiler parses the C++ code; provides a list of errors if any\n",
    "- fails to compile a program to byte code if program has compiler error\n",
    "\n",
    "#### Run-time errors\n",
    "- also called run-time exceptions\n",
    "- these errors appear while program is running\n",
    "- can be handled to certain extent\n",
    "\n",
    "#### Semantic errors\n",
    "- also called logical errors\n",
    "    - errors in thought process, may arise due to misunderstanding of problem, wrong solution/answer, language quirks\n",
    "- program runs fine but gives wrong answer\n",
    "    - e.g., adding instead of multiplying to solve an equation (e.g., $2+2$ is same as $2\\times2$)\n",
    "- can be identified and removed by doing adequate testing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Labs\n",
    "\n",
    "1. Standard Output Lab \n",
    "    - write a C++ program that produces the following output on console\n",
    "    - use the partial solution provided in [labs/intro/main.cpp](labs/intro/main.cpp)\n",
    "    - observe and note how the special symbols such as single quote, double quotes and black slashes\n",
    "    - run the program as it is using the provided make file in the stdio folder\n",
    "    - complete the rest of the ASCII Art by fixing all the FIXMEs\n",
    "    - write #FIXED next to each fixme\n",
    "    \n",
    "    ```text\n",
    "        |\\_/|       *******************************     (\\_/)\n",
    "       / @ @ \\      *      ASCII Art              *    (='.'=)\n",
    "      ( > 0 < )     *      Author: <Your Name>    *  ( \" )_( \" )\n",
    "        >>x<<       *      CS Foundation Course   *\n",
    "        / O \\       *******************************\n",
    "   ```\n",
    "   \n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Setup Developement Environment\n",
    "    - setup your personal development environment\n",
    "    - download and install tools that are typically used by programmers: C++ Editor, C++ Compiler, git client, etc.\n",
    "    - you can follow the steps provided [here](https://github.com/rambasnet/DevEnvSetup)\n",
    "  \n",
    "  \n",
    "2. Hello World\n",
    "    - write a C++ program that prints \"Hello World!\" as an output to the console\n",
    "    - see complete solution in [exercises/intro/helloworld/main.cpp](exercises/intro/helloworld/main.cpp)\n",
    "    - write Makefile and use make to build the program\n",
    "    - see Makefile solution here: [exercises/intro/helloworld/Makefile](exercises/intro/helloworld/)\n",
    "\n",
    "\n",
    "3. ASCII Art\n",
    "    - google images made using ASCII arts\n",
    "    - print some ASCII arts, texts and pictures of your choice\n",
    "    - can use ASCII Art generator: [http://patorjk.com/software/taag/#p=display&f=Graffiti&t=Type%20Something%20](http://patorjk.com/software/taag/#p=display&f=Graffiti&t=Type%20Something%20)\n",
    "\n",
    "    \n",
    "4. The Game of Hangman\n",
    "    - write a C++ program that prints various stages of the hangman game\n",
    "    - game description: [https://en.wikipedia.org/wiki/Hangman_(game)](https://en.wikipedia.org/wiki/Hangman_(game))\n",
    "    - produce the output seen in Example game section of the Wikipedia page\n",
    "    - game will not have any logic to actually play, unless you know how to implement it!\n",
    "    \n",
    "### Kattis problems\n",
    "\n",
    "1. Hello World!\n",
    "    - login and solve the Hello World! problem: [hello](https://open.kattis.com/problems/hello)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "- this chapter covered:\n",
    "- the basics of Compter Science and programming\n",
    "- different types of programming languages\n",
    "- C++ basics, the first program and the basic structure of a C++ program\n",
    "    - how to print data to standard output\n",
    "- C++ editor and compiler\n",
    "- exercises and sample solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}