CSEN/CSIS 102 Lecture 5: Iterative Algorithms with Lists

This lecture introduces Python lists, a fundamental data structure for organizing collections of data, and explores iterative algorithms used to process their elements.


Outline

This lecture covers the following key topics:


Python Lists

A list in Python is a versatile and ordered collection of data items. Lists are denoted using square brackets `[]` and can contain items of different data types (e.g., integers, floats, strings, or even other lists).

Key Characteristics of Python Lists:

Example: Consider a list `temperatures = [22, 25, 19, 23, 20]`. Here, `temperatures[0]` is `22`, and `len(temperatures)` is `5`. If a user inputs `["apple", "banana", "cherry"]`, then `fruits = eval(input())` would store this list in `fruits`, and `len(fruits)` would be `3`.


Iteration over Lists

Iteration is the process of repeating a sequence of instructions over each item in a list. This is fundamental for processing, analyzing, or modifying data stored in lists.

Common Iterative Algorithms:

Example 1: Median

The median of a list of numbers is the middle value when the numbers are sorted in ascending order. If the list has an odd number of elements, the median is the single middle element. If it has an even number of elements, the median is typically the average of the two middle elements.

Problem: Write a Python program that takes as input a list of integers, computes the median, and prints it out.

Approach:

  1. Take the list of integers as input.
  2. Sort the list in ascending order.
  3. Find the length of the list.
  4. Check if the length is odd or even:
  5. Print the calculated median.
Example: For `[1, 5, 2, 8, 3]`, after sorting it becomes `[1, 2, 3, 5, 8]`. The length is 5 (odd), so the median is at index `5 // 2 = 2`, which is `3`. For `[10, 40, 20, 30]`, after sorting it becomes `[10, 20, 30, 40]`. The length is 4 (even), so the median is `(20 + 30) / 2 = 25`.

Example 2: Average

The average (or mean) of a list of numbers is the sum of all elements divided by the number of elements.

Problem: Write a Python program that takes as input a list of integers, computes the average of the list, and prints it out.

Approach:

  1. Take the list of integers as input.
  2. Initialize a `sum` variable to `0`.
  3. Iterate through each element in the list, adding its value to the `sum`.
  4. After iterating through all elements, divide the `sum` by the length of the list.
  5. Print the calculated average.
Example: For `[10, 20, 30, 40]`, the sum is `10+20+30+40 = 100`. The length is `4`. The average is `100 / 4 = 25`.

Example 3: Maximum and Minimum

Finding the maximum and minimum values in a list involves iterating through the elements and keeping track of the largest and smallest values encountered so far, along with their positions.

Problem: Write a Python program that takes as input a list of integers, computes the maximum and minimum of the list, and prints them out with their positions in the input list.

Approach:

  1. Take the list of integers as input.
  2. Initialize `max_value` and `min_value` with the first element of the list.
  3. Initialize `max_pos` and `min_pos` to `0`.
  4. Iterate through the list starting from the second element (index 1):
  5. Print the `max_value`, `max_pos`, `min_value`, and `min_pos`.
Example: For `[5, -6, 10, 11, -5]`: Initially, `max_value = 5`, `min_value = 5`, `max_pos = 0`, `min_pos = 0`. - When iterating to `-6` (index 1): `-6` is less than `5`, so `min_value = -6`, `min_pos = 1`. - When iterating to `10` (index 2): `10` is greater than `5`, so `max_value = 10`, `max_pos = 2`. - When iterating to `11` (index 3): `11` is greater than `10`, so `max_value = 11`, `max_pos = 3`. - When iterating to `-5` (index 4): `-5` is greater than `-6` but less than `11`. Final output: Max is 11 at position 3, Min is -6 at position 1.

Example 4: Check Sorted

To check if a list is sorted in ascending order, you need to compare adjacent elements. If any element is greater than its subsequent element, the list is not sorted.

Problem: Write a Python program that takes as input a list of integers, prints out `True` if the list is sorted in ascending order, and `False` otherwise.

Approach:

  1. Take the list of integers as input.
  2. Iterate through the list from the first element up to the second-to-last element (as you need to compare `list[i]` with `list[i+1]`).
  3. Inside the loop, check if `list[i] > list[i+1]`.
  4. If this condition is ever true, the list is not sorted, so immediately print `False` and exit.
  5. If the loop completes without finding any such condition, it means the list is sorted, so print `True`.
Example: For `[1, 5, 8, 10]`, the program would print `True`. For `[1, 8, 5, 10]`, when comparing `8` and `5`, it would find `8 > 5`, print `False`, and stop.

Example 5: Phone Book Search

This problem involves searching for a specific item (venue name) in one list and, if found, retrieving corresponding information (phone number) from another list at the same index.

Problem: Write a Python program that takes as input a list of strings of names of venues, a list of integers representing their phone numbers, and a string representing the name of a particular venue. Your program should print out the phone number of the given venue if it exists, and "Not found" otherwise.

Approach:

  1. Take two lists as input: `venue_names` (strings) and `phone_numbers` (integers).
  2. Take the `search_venue` string as input.
  3. Iterate through the `venue_names` list using an index (e.g., using `range(len(venue_names))`).
  4. Inside the loop, check if `venue_names[i]` is equal to `search_venue`.
  5. If a match is found:
  6. If the loop completes without finding a match (i.e., the `search_venue` was not in the `venue_names` list), print "Not found".
Example: If `venue_names = ["Cafe A", "Restaurant B", "Bar C"]` and `phone_numbers = [111222, 333444, 555666]`. - If `search_venue = "Restaurant B"`, the program would find it at index 1 and print `333444`. - If `search_venue = "Hotel D"`, the program would iterate through all names, not find a match, and print "Not found".