CSBP119: Algorithms & Problem Solving PDF

# CSBP119: Algorithms & Problem Solving ## Introduction to Computers and Programming ### Introduction * **Computer Can be programmed:** * Designed to do any job that a program tells them to do. * A means that computers can be given specific instructions to perform tasks ### Program * Set...

# CSBP119: Algorithms & Problem Solving ## Introduction to Computers and Programming ### Introduction * **Computer Can be programmed:** * Designed to do any job that a program tells them to do. * A means that computers can be given specific instructions to perform tasks ### Program * Set of instructions that a computer follows to perform a task * Commonly referred to as software ### Programmer * Person who can design, create, and test computer programs * Also known as Software developer ### Hardware * The physical devices that make up a computer * Computer is a system composed of several components that all work together #### Typical major Components: * Central processing unit * Main memory * Secondary storage devices * Input and output devices ## CPU (Central Processing Unit) * The brain of a computer that carries out instructions and processes data to perform tasks. * The part of the computer that actually runs programs. * Most important component - without it, software cannot run. ### Microprocessors * Cpu located on small chips ## Main Functions of CPU * **Processing Data:** Executes instructions from programs to complete tasks. * **Perform Calculations:** Handles mathematical and logical operations. * **Controlling operations:** Directs how data moves between different parts of the Computer. ## Key Part of CPU * **(ALU) = Arithmetic Logic Unit:** Performs calculations including mathematical and logical comparisons. * **(CU) = Control Unit:** Manages and coordinates activities within the computer by directing data flow. * **Registers:** Small, fast storage units inside the cpu that holds temporary data and instructions. ## Main Memory * Known as: primary memory or RAM (Random Access memory) * Part of the computer that temporarily stores data and instructions that the cpu needs while performing tasks. ### Key Features of Main Memory * **Temporary storage:** Stores data only while the computer is on. Once the system is turned off, all data on main memory will be lost. * **Fast Access:** Provides quick access to data for the cpu, making the computer run fast * **Volatile:** Data is erased when the computer shuts down. ## Types of Main Memory * **RAM = Random Access memory:** Stores data and instructions that the cpu uses during operations. It can be read and written but volatile memory (data is lost when the power is off). * **ROM = Read-only memory:** Contains permanent instructions needed for booting up the computer. It can only be read but not written to. * **Non-volatile:** Data is retained/saved even when the computer is off. ## Why Main Memory is Important * **Speeds up performance:** More RAM allows more programs to run smoothly at the same time. * **Temporary workspace:** Holds active data and programs for quick access by the cpu. ## Secondary Storage Devices * A type of computer memory used to store data and files permanently, even when the computer is turned off. It holds programs, documents, and other files that are not actively being used by the cpu. ### Key Features of Secondary Storage * **Permanent storage:** * **Large Capacity:** * **Slower than RAM:** * **Non-volatile:** Data is not lost when the system shuts down. ### Types of Secondary Storage Devices * **HDD = Hard disk drive:** A magnetic storage device with large storage capacity. Common in desktops and laptops for storing OS, programs, files. * **Solid State Drive = SSD:** Faster and more reliable than HDD because it has no moving parts. It used flash memory to store data. ## Optical Discs Includes CDs, DVD / Blu-ray discs used for media storage. ## USB flash drives Portable and easy to use flash memory devices for transferring data. ## Memory cards (SD cards) Used in cameras, smartphones, and tablet for extra storage. ## External Hard drive Portable devices for backup and extra storage. ## Cloud Storage Online storage services (eg. google drive, dropbox) that saves data over the internet. ## Why secondary storage is so important * **Data backup:** Keeps important files safe and secure. * **Software Storage:** Stores operating systems, applications, and games. * **Large file Storage:** Holds videos, images, large datasets. ## Input devices * Hardware components that allow users to enter data and instructions into a computer for processing. They act as a bridge between the user and the computer system. ### Common input devices * **Keyboard:** Used to type text, numbers, and commands. Includes special keys like function keys, control keys, and navigation keys. * **Mouse:** Used to move the cursor, click, drag, and drop items on the screen. It has a scroll wheel for easy navigation. * **Touchscreen:** Allows users to interact directly with the screen by touching it. Common in smartphones, tablets, and some laptops. * **Scanner:** Converts physical documents or images into digital formats. ## Input devices cont. * **Microphone:** Captures sound and voice input for communication or recording. * **Trackpad/Touch pad:** A flat surface on laptops that responds to finger movements for cursor control. * **Webcam:** Captures live video and images for video calls or recordings. * **Joystick:** Used mainly for gaming and controlling simulations. * **Light pen:** A pen-like device used to draw or select items directly on a screen. * **Barcode scanner:** Reads barcodes on products and converts the information into data. * **Biometric devices:** Used for security by scanning fingerprints, facial features, or retina patterns. ## What is the Purpose of Input Devices * To enter data (text, image, audio etc.) into the computer. * To control software and applications through commands and interactions. * To communicate with the computer for a specific task. ## Output devices * Hardware components that display, project, or deliver the results of a computer's processing to the user. They convert digital information into a form that humans can understand, such as text, images, sound, or physical objects. ### Common output devices * **Monitor (screen/display):** Displays text, images, videos, and graphics. Types include LCD, LED, and OLED screens. * **Printer:** Produces physical (hard copy) text and images on paper. Types: Inkjet printer, Laser printer, 3D printer - creates 3D objects from digital designs. * **Speakers:** Convert digital audio signals into sound. Used for music, videos, games, and system alerts. * **Headphones/Ear Phones:** Personal audio output devices for private listening. ## Output devices cont. * **Projector:** Projects visual output onto a larger screen or surface, often used for presentations and movies. * **Plotter:** Used for printing large designs, like architectural blueprints or engineering drawings. * **Virtual Reality (VR) Headsets:** Provide immersive visual and audio output for virtual environments. * **Haptic devices:** Provide physical feedback (vibrations or motions) for touch-based interactions, common in gaming controllers and smartphones. ## What is the purpose of output devices? * **Display information:** Show text, images, and videos for users to view. * **Produces hard copies:** Print documents and images for physical use. * **Provide Sound:** Output music, voice, and system sounds. * **Enhance interaction:** Improve user experience through visuals, sound, and touch. ## Chapter 2: Software * The intangible set of instructions, programs, and rules that tells a computer what to do - it’s the brain behind the hardware, enabling a computer to perform specific tasks and interact with the user. ### Types of software * **System Software:** This software manages the computer's hardware and resources, such as operating systems. * **Application software:** Designed to perform specific tasks for end-users and make the computer easy for everyday life. #### Some common application software types: * **Productivity Software:** Word processors, spreadsheets, presentation software, email, etc. * **Multimedia Software:** Media players, image editors, and video editors. * **Educational Software:** Programs designed for learning and teaching. * **Specialized Software:** Programs designed for specific industries or tasks, such as medical software or accounting software. ## How Computers Store Data * All data in a computer is stored in sequences of os and 1s (binary representation). * The binary system is the foundation of all computer data storage. ### Byte * The basic unit for measuring computer storage capacity. It provides enough memory to store a letter or a small number. * A group of 8 bits is called a byte ### Bit * A single binary digit (0 or 1) and is called a bit that can hold a positive or negative value/charge (ex. on/off switch). * The on/off pattern of bits in a byte represents data stored in the byte. ## Storing Numbers * **Bit:** Represents two values, 0 and 1. * **Computers use binary numbering system:** * Position of digit j is assigned the value 2^j-1. * The rightmost position (j=1) has a weight of 2^(1-1) = 2^0 = 1. * The next position to the left (j=2) has a weight of 2^(2-1) = 2^1 = 2, and so on. * **Byte:** Size limits are 0 and 255. * 0 = all bits off; 255 = all bits on * **To store larger numbers, use several bytes.** ## Storing Characters * **Data must be stored in a computer as binary numbers.** Characters are converted to numeric code, and numeric code is stored in memory. * **To store text in a computer, each character (letters, numbers, symbols) is converted into numerical code, then stored in computer memory as a sequence of bits (0s and 1s).** It represents two values, 0 and 1. ### ASCII (American Standard Code for Information Interchange) * Widely used standard for encoding characters. * **Unique 7-bit binary code to each character, allowing for a total of 128 possible characters.** * **Unicode coding scheme is becoming standard.** * *Unicode supports a vast range of characters including those from different languages, scripts, and symbols, making it suitable for global communication and data exchange.* * *Compatible with ASCII* * Can represent characters for other languages, scripts, and symbols, making it suitable for global communication and data exchange. * Can represent characters for other languages. * **Ex: The ASCII values for "Hello" are 72, 101, 108, 108, 111 and 32.** ## How a program works * The CPU is designed to perform simple operations on pieces of data: reading data, adding, subtracting, multiplying, and dividing numbers. * The cpu understands instructions in machine language and includes its instruction set. Each brand of cpu has its own instruction set. * A program must be copied from secondary to main (RAM) each time the cpu executes it. * The CPU executes a program in cycles: * **Fetch:** Read the next instruction from memory into the cpu. * **Decode:** The CPU decodes the fetched instruction to determine which operation to perform. * **Execute:** Perform the operation. ## Machine Language and Assembly Language * It's impractical for people to write in machine language. ### Machine Language and Assembly Language * **Machine language:** Consists of raw binary code (0s and 1s). It's extremely difficult for humans to read, write, and understand. Writing programs directly in machine language would be tedious, error-prone, and time-consuming. * **Assembly language:** Uses short words (mnemonics) for instructions instead of binary numbers. It's a low-level programming language that uses short, human-readable codes to represent machine instructions. It's easier for programmers to work with compared to machine language, making the programming process more manageable and less prone to errors. *The Assembler* translates assembly language to machine language for execution by the CPU. ## High-level Languages * **Low-level language:** Close in nature to machine language. Ex: Assembly language * **High-level language:** Allows simple creation of powerful and complex programs. It removes the need to know how a cpu works or write large numbers of instructions. It's human-understandable. ## Keywords: * Predefined words used to write programs in high-level languages. *Example: print* (a keyword that tells the program to display something on the screen.) ## Operators * Perform operations on data. *Example: Math operators* to perform arithmetic. *(+) operator:* The addition operator, used to combine two numbers. ## Syntax * Set of rules to be followed when writing a program. *Example: The specific arrangement of elements in the code is crucial. The keyword "print" must come before the parentheses. The values to be added must be enclosed within parentheses.* ## Statement * Individual instruction used in high-level languages. *Example: print(5 + 3)* ## Compilers and Interpreters * Programs written in high-level languages must be translated into machine language to be executed. ### Compiler * Translates a high-level language program into separate machine language. * *A machine language program can be executed at any time.* ### Interpreter * Translates and executes instructions of a high-level language program. * It uses computer language, interprets one instruction at a time and does not have a separate machine language program. ## Source code * Statements written by a programmer. ## Syntax error * Prevents code from being translated. ## Compilers and Interpreters (cont'd.) * The interpreter translates each high-level instruction to its equivalent machine language instructions and immediately executes them. This process is repeated for each high-level instruction. ## Programming Language: Python * Python must be installed and configured prior to use. One of the items installed is the Python interpreter. * **Interactive mode:** Enter statements on a keyboard. * **Script mode:** Save statements in a Python script. ### Interactive Mode * When you start Python in interactive mode, you will see a prompt. It indicates that the interpreter is waiting for a Python statement to be typed. The prompt reappears from previous statements once they are executed. * Error messages are displayed if you incorrectly type a statement. This is a good way to learn new parts of Python. ### Script Mode * Statements entered in interactive mode are not saved as a program, you need to have a script mode to be saved. * Save a set of Python statements in a file. The filename should have the ".py" extension. * To run the file or script, type “python filename" at the operating system command line. ## Designing a Program * Programs must be designed before they are written. * **Program development cycle:** * Design the program * Write the code * Correct syntax errors * Test the program * Correct logic errors ## Designing a Program * **Determine the steps that must be taken to perform the task.** This is the first step in the problem-solving process. This involves understanding what the desired outcome is and what inputs or data are needed to achieve that outcome. * **Break down the required task into a series of steps.** Once you have a clear understanding of the task, you need to break it down into smaller, more manageable steps. This involves identifying the individual actions or sub-tasks that need to be performed to complete the overall task. ## Algorithm * A set of well-defined logical steps that must be taken to perform a task. ## Pseudocode * **Pseudocode:** Fake code, a set of rules to be followed by writing programs. It's an informal language that has no syntax rules. It is not meant to be compiled or executed; it’s used to create model programs. You don’t need to worry about syntax errors — focus on program design! It can be translated directly into actual code in any *programming language.* ## Flowcharts * A diagram that graphically depicts the steps in a program. * **Ovals:** Are terminal symbols. * **Parallelograms:** Input and output symbols. * **Rectangle:** Processing symbols. * **Symbols are connected by arrows that represent the flow of the program.** ## Input, Processing, and Output * A computer typically performs a three-step process: * **Receive:** Input (any data that a program receives while it is running). * **Perform:** Some processing on the input (ex. mathematical calculation). * **Produce:** Output. * *Example: input:* hours worked and hourly pay rate. *Process:* Multiply hours worked by hourly pay rate. *Output:* Gross pay. ## Functions * A piece of pre-written code that performs a specific task or operation. ### Purpose * **Organize code:** Break down large programs into smaller, reusable units. * **Improve readability:** Make code easier to understand by giving meaningful names to specific operations. * **Reduce redundancy:** Avoid writing the same code multiple times by using a function that can be called repeatedly. * **Increase modularity:** Create more flexible and maintainable code. ## Argument * Data given to a function. An Argument is a piece of data that is passed to a function when it is called. * *Example: If you have a function named "add numbers," you might pass two numbers as arguments: add_numbers(5, 3). The function would then add these numbers together.* ## Statement * In a program, a statement is executed in the order that they appear, from top to bottom. ## Example: Displaying Output with the Print Function * **print('Hello World')** * **Argument:** Data that is printed to the screen. * **print function:** Displays output on the screen. * **String:** A sequence of characters that is used as data. * **String literal:** A string that appears in the actual code of a program. ## String Literal * Must be enclosed in single (‘) or double (") quote marks. * A string literal can be enclosed in triple quotes (''' or """) * An enclosed string can contain both single and double quotes and can have multiple lines. ## Comments * Notes of explanation within a program. * Ignored by Python interpreter. * Intended for a person reading the program's code * Begin with a # character ### End-line Comment * Appears at the end of a line of code and typically explains the purpose of that line. ## Variable * A name that represents a value stored in computer memory. * Used to access and manipulate data stored in memory. * A variable references the value it represents. ## Assignment statement * Used to create a variable and make it reference data. * The general format is variable = expression. * Example: *age = 29*. * The *assignment operator* is the equal sign (=). It performs an operation on data. ## Rules * **Variable receiving value must be on the left side.** * **A variable can be passed as an argument to a function.** * **Variable name should not be enclosed in quote marks.** * **Use a variable if a value is assigned to it.** ## Variable Naming Rules * **Variable name cannot be a Python key word.** * **Variable name cannot contain spaces.** * **First character must be a letter or an underscore.** * **After the first character, you can use letters, digits, or underscores.** * **Variable names are case sensitive.** * **Variable name should reflect its use.** ## Displaying Multiple Items with the Print Function * Python allows someone to display multiple items with a single call to "print". * **Items are separated by commas when passed as arguments.** * **Arguments are displayed in the order they are passed to the function.** * **Items are automatically separated by a space when displayed on the screen.** ## Variable Reassignment * Variables can reference different values while a program is running. ### Garbage collection: * The removal of values that are no longer referenced by variables. It is carried out by the Python interpreter. * A variable can refer to an item of any type. A variable that has been assigned to one type can be reassigned to another type. ## Data types * Categorize values in memory. * **Ex:** * **int:** For an integer. * **float:** For a real number. * **str:** For storing string memory. ## Numeric Literal * A number written in a program. **No decimal point is considered "int". If it has a decimal point, it will be "float".** ## Example * **x = 99** * **print(x)** * **x = 'Take me to your leader'** * **print(x)** * **Output:** * *99* * *Take me to your leader*