# COMP 110/L: Introduction to Algorithms & Programming
This document provides a comprehensive set of lecture notes for COMP 110/L, an introductory
course on algorithms and programming. These notes are designed to be a complete resource for
students, covering all fundamental concepts from the ground up.
## Table of Contents
1. **Course Introduction and Overview**
* What is Computer Science?
* What is Programming?
* Course Goals and Objectives
* Introduction to the Programming Environment
2. **Fundamentals of Programming**
* Basic Syntax and Data Types
* Variables and Assignment
* Operators
* Input and Output
3. **Control Structures**
* Conditional Statements (`if`, `else if`, `else`)
* Loops (`for`, `while`)
* Boolean Logic
4. **Functions**
* Defining and Calling Functions
* Parameters and Arguments
* Return Values
* Scope
5. **Data Structures I: Collections**
* Lists (Arrays)
* Strings
* Tuples
* Dictionaries (Hash Maps)
6. **Object-Oriented Programming (OOP)**
* Objects and Classes
* Methods and Attributes
* Encapsulation
* Inheritance
* Polymorphism
7. **Algorithms**
* Introduction to Algorithms
* Searching Algorithms (Linear Search, Binary Search)
* Sorting Algorithms (Bubble Sort, Selection Sort, Insertion Sort)
* Algorithm Complexity (Big O Notation)
8. **File I/O**
* Reading from Files
* Writing to Files
* Working with Different File Formats (e.g., CSV)
9. **Recursion**
* Introduction to Recursion
* Recursive Functions
* Base Cases and Recursive Steps
10. **Modules and Libraries**
* Using External Code
* Standard Libraries
* Installing and Importing Packages
11. **Testing and Debugging**
* Types of Errors
* Debugging Techniques
* Writing Test Cases
12. **Lab Exercises**
* Weekly lab assignments to reinforce concepts.
-----
## 1\. Course Introduction and Overview
### What is Computer Science?
Computer Science is the study of computation, information, and automation. It encompasses
theoretical disciplines (such as algorithms, theory of computation, and information theory) and
applied disciplines (such as the design and implementation of hardware and software).
### What is Programming?
Programming is the process of creating a set of instructions that tell a computer how to perform
a task. These instructions are written in a programming language, which is a formal language that
can be understood by a computer.
### Course Goals and Objectives
By the end of this course, you will be able to:
* Understand the fundamental concepts of programming.
* Design and implement algorithms to solve problems.
* Use a programming language (such as Python) to create simple applications.
* Understand the basics of object-oriented programming.
* Be able to debug and test your code.
### Introduction to the Programming Environment
To write and run code, you will need a programming environment. This typically consists of:
* **A text editor:** To write your code.
* **A compiler or interpreter:** To translate your code into a language the computer can
understand.
* **A terminal or command prompt:** To run your code and see the output.
For this course, we will be using Python. You will need to install Python and a text editor such as
Visual Studio Code, Sublime Text, or Atom.
-----
## 2\. Fundamentals of Programming
### Basic Syntax and Data Types
Every programming language has a set of rules that govern how programs are written. This is
known as the **syntax** of the language.
In Python, some of the basic **data types** include:
* **Integers (`int`):** Whole numbers, such as `10`, `-5`, `0`.
* **Floating-point numbers (`float`):** Numbers with a decimal point, such as `3.14`, `-0.001`.
* **Strings (`str`):** Sequences of characters, enclosed in single or double quotes, such as
`"Hello, World!"`.
* **Booleans (`bool`):** Represent truth values, either `True` or `False`.
### Variables and Assignment
A **variable** is a name that refers to a value. In Python, you can create a variable and assign it
a value using the assignment operator (`=`).
```python
x = 10 # x is an integer
pi = 3.14 # pi is a float
name = "Alice" # name is a string
is_student = True # is_student is a boolean
```
### Operators
Operators are special symbols that perform operations on variables and values.
* **Arithmetic Operators:** `+` (addition), `-` (subtraction), `*` (multiplication), `/` (division), `%`
(modulus), `**` (exponentiation), `//` (floor division).
* **Comparison Operators:** `==` (equal to), `!=` (not equal to), `>` (greater than), `<` (less
than), `>=` (greater than or equal to), `<=` (less than or equal to).
* **Logical Operators:** `and`, `or`, `not`.
### Input and Output
You can get input from the user using the `input()` function and display output using the `print()`
function.
```python
name = input("Enter your name: ")
print("Hello, " + name + "!")
```
-----
## 3\. Control Structures
### Conditional Statements (`if`, `else if`, `else`)
Conditional statements allow you to execute different blocks of code based on whether a certain
condition is true or false.
```python
age = 20
if age >= 18:
print("You are an adult.")
else:
print("You are a minor.")
```
### Loops (`for`, `while`)
Loops are used to execute a block of code repeatedly.
* **`for` loop:** Iterates over a sequence (such as a list or a string).
<!-- end list -->
```python
for i in range(5):
print(i) # Prints numbers from 0 to 4
```
* **`while` loop:** Executes as long as a certain condition is true.
<!-- end list -->
```python
count = 0
while count < 5:
print(count)
count += 1
```
### Boolean Logic
Boolean logic is a system of logic based on two truth values: `True` and `False`. It is used in
conditional statements and loops to make decisions.
-----
## 4\. Functions
### Defining and Calling Functions
A **function** is a reusable block of code that performs a specific task. You can define a function
using the `def` keyword and call it by its name.
```python
def greet():
print("Hello, World!")
greet() # Calls the function
```
### Parameters and Arguments
You can pass data to a function through **parameters**. When you call the function, you
provide **arguments** for those parameters.
```python
def greet(name):
print("Hello, " + name + "!")
greet("Alice") # "Alice" is the argument
```
### Return Values
A function can return a value using the `return` statement.
```python
def add(a, b):
return a + b
result = add(5, 3)
print(result) # Prints 8
```
### Scope
The **scope** of a variable is the part of the program where it is accessible. Variables defined
inside a function have local scope, meaning they can only be accessed within that function.
-----
## 5\. Data Structures I: Collections
### Lists (Arrays)
A **list** is an ordered collection of items. You can create a list by placing the items inside
square brackets, separated by commas.
```python
my_list = [1, 2, 3, "apple", "banana"]
```
### Strings
A **string** is a sequence of characters. You can access individual characters using indexing.
```python
my_string = "Hello"
print(my_string[0]) # Prints 'H'
```
### Tuples
A **tuple** is similar to a list, but it is immutable, meaning its elements cannot be changed after
it is created.
```python
my_tuple = (1, 2, 3)
```
### Dictionaries (Hash Maps)
A **dictionary** is an unordered collection of key-value pairs.
```python
my_dict = {"name": "Alice", "age": 25}
```
-----
## 6\. Object-Oriented Programming (OOP)
### Objects and Classes
**Object-Oriented Programming (OOP)** is a programming paradigm based on the concept of
"objects", which can contain data in the form of fields (often known as attributes or properties),
and code, in the form of procedures (often known as methods).
A **class** is a blueprint for creating objects.
```python
class Dog:
def __init__(self, name, age):
self.name = name
self.age = age
def bark(self):
print("Woof!")
```
### Methods and Attributes
* **Attributes:** Variables that belong to an object.
* **Methods:** Functions that belong to an object.
### Encapsulation
Encapsulation is the bundling of data with the methods that operate on that data.
### Inheritance
Inheritance is a mechanism in which one class acquires the property of another class.
### Polymorphism
Polymorphism is the ability of an object to take on many forms.
-----
## 7\. Algorithms
### Introduction to Algorithms
An **algorithm** is a step-by-step procedure for solving a problem.
### Searching Algorithms
* **Linear Search:** A simple search algorithm that checks every element in a list until the
target element is found.
* **Binary Search:** An efficient search algorithm that works on sorted lists. It repeatedly
divides the search interval in half.
### Sorting Algorithms
* **Bubble Sort:** A simple sorting algorithm that repeatedly steps through the list, compares
adjacent elements and swaps them if they are in the wrong order.
* **Selection Sort:** A simple sorting algorithm that divides the input list into two parts: a
sorted sublist and an unsorted sublist.
* **Insertion Sort:** A simple sorting algorithm that builds the final sorted array one item at a
time.
### Algorithm Complexity (Big O Notation)
**Big O notation** is a mathematical notation that describes the limiting behavior of a function
when the argument tends towards a particular value or infinity. It is used to classify algorithms
according to how their run time or space requirements grow as the input size grows.
-----
## 8\. File I/O
### Reading from Files
You can read data from a file using the `open()` function and the `read()` or `readlines()` methods.
```python
with open("my_file.txt", "r") as f:
content = f.read()
print(content)
```
### Writing to Files
You can write data to a file using the `open()` function and the `write()` method.
```python
with open("my_file.txt", "w") as f:
f.write("Hello, World!")
```
### Working with Different File Formats (e.g., CSV)
You can use libraries like `csv` to work with CSV (Comma-Separated Values) files.
-----
## 9\. Recursion
### Introduction to Recursion
**Recursion** is a method of solving a problem where the solution depends on solutions to
smaller instances of the same problem.
### Recursive Functions
A **recursive function** is a function that calls itself.
```python
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
```
### Base Cases and Recursive Steps
A recursive function must have a **base case** that stops the recursion and a **recursive step**
that moves the problem closer to the base case.
-----
## 10\. Modules and Libraries
### Using External Code
You can use code from other files by importing it as a **module**.
### Standard Libraries
Python has a rich **standard library** with modules for a wide range of tasks.
### Installing and Importing Packages
You can use a package manager like `pip` to install third-party packages.
-----
## 11\. Testing and Debugging
### Types of Errors
* **Syntax Errors:** Errors in the code that violate the rules of the programming language.
* **Runtime Errors:** Errors that occur while the program is running.
* **Logic Errors:** Errors that cause the program to produce incorrect results.
### Debugging Techniques
* **Print statements:** Use `print()` to display the values of variables at different points in your
code.
* **Debugger:** A tool that allows you to step through your code line by line and inspect the
values of variables.
### Writing Test Cases
**Test cases** are sets of inputs and expected outputs that you can use to test your code and
ensure that it is working correctly.
-----
## 12\. Lab Exercises
This section would typically contain a series of weekly lab exercises that correspond to the topics
covered in the lectures. These labs would provide hands-on experience with the concepts and
allow students to practice their programming skills.
**Example Lab Exercise (for Functions):**
1. Write a function called `calculate_area` that takes the radius of a circle as a parameter and
returns the area of the circle.
2. Write a function called `is_prime` that takes an integer as a parameter and returns `True` if the
number is prime and `False` otherwise.
3. Write a program that uses these functions to calculate the area of a circle with a radius
entered by the user and to check if a number entered by the user is prime.
