Introduction to Programming - Built-in Data Structures

Introduction to Programming

  • Instructor: Dr. Shounak Roychowdhury
  • Institution: School of Information, University of Texas at Austin

Lecture Overview

  • Previous Topics Covered:
    • Programming approach through Polya’s method
    • Key Techniques:
    • Decomposition
    • Identifying common patterns
    • Abstraction & hiding details
    • Programming Styles:
    • Emphasis on decomposition and modularity
    • Functions to abstract common code and avoid repetition
    • Examination of simple programming examples
    • Debugging: sourcing bugs and errors

Range Data Structure

Range Overview

  • Definition: The range type represents an immutable sequence of numbers commonly used for looping a finite number of times in for loops.
  • Variations: Can be used in two main forms:
    • Single Argument: range(stop)
    • Multiple Arguments: range(start, stop[, step])
    • start: The sequence starts at this number (inclusive)
    • stop: The sequence ends at this number (exclusive)
    • step: The increment (default is 1), can be negative
    • Example showing usage of range: range(-5, 6, 2) results in a sequence of numbers:
      print(f"[1] rngx = {list(rngx)}") # Output: [-5, -3, -1, 1, 3, 5]
    • An empty sequence can occur if start > end with a positive step.

Characteristics of Range

  • Type: class range
  • An empty sequence results if conditions are met (e.g., start > end with positive step).
  • It supports negative sequences as well, and can be visualized using the list function.

Examples of Range Usage

  • Examples showcasing range with positive steps: 
  rngx = range(0, -6, -2)
  print(f"[2] rngx = {list(rngx)}") # Output: [0] 
  rngx = range(5, -1, -1)
  print(f"[5] rngx = {list(rngx)}") # Output: [5, 4, 3, 2, 1, 0]
  • Important Note: range only accepts integers, and attempting to use floats will lead to a TypeError (e.g., for i in range(6.0)) results in:
    • Error: TypeError: 'float' object cannot be interpreted as an integer.

The Pass Statement

  • Definition: The pass statement does nothing. It is used syntactically where a statement is required, but the program should perform no action at that point.

Switch Statement Concept

Concept Overview
  • Example of switch implementations in Java: 
  int month = 8;
  switch (month) {
    case 1: monthString = "January"; break;
    case 2: monthString = "February"; break;
    case 3: monthString = "March"; break;
    // And so on...
    default: monthString = "Invalid month"; break;
  }
  • Functionality: The switch statement allows selecting among multiple alternatives based on the value of an expression. Uses case blocks for actions.

Concept of Arrays

  • Definition: An array is a data structure containing a collection of elements (values or variables) with the same memory size.
  • Access: Each element is identified by at least one array index or key.
  • Memory Storage: Arrays leverage contiguous memory locations; for instance, an array of ten 32-bit integers may be stored in memory starting from an address such as 2000, with increments of 4 bytes.
    • Base Address: The memory address of the first element is often called the first address, foundation address, or base address.
  • Applications: Used to implement mathematical vectors (1D) and matrices (2D) among other data constructs.

Built-in Data Structures in Python

  • Overview of Data Structures:
    • List
    • List comprehension
    • Tuples and sequences
    • Sets
    • Dictionaries
    • Dictionary comprehension
    • Looping techniques
    • Advanced conditions, sequences, etc.

Lists in Python

Basic List Operations

  • Definition: A list is a flexible sequence type that can hold items of different types.
  • Creating a List: A list can be created using square brackets: 
  squares = [1, 2, 4, 9, 16, 25]

  • Example Operation: Getting values from a list. 

    value_at_index_0 = squares[0]
    • Common List Operations:

  • Appending elements, extending lists, slicing, concatenating, and mutating.

List Characteristics

  • Mutable: Lists can be modified after creation (elements can be added, removed, or changed).
  • Dynamic Size: Unlike typical arrays in other languages, lists do not require a predetermined size.

List Methods

  • list.append(elem): Adds an element to the end of the list (does not return a new list).
  • list.insert(index, elem): Inserts an element at the specified index.
  • list.extend(list2): Add elements from another list.
  • list.index(elem): Returns the index of the first occurrence of an element.
  • list.remove(elem): Removes the first occurrence of a specified element.
  • list.sort(): Sorts the elements in the list.
  • list.reverse(): Reverses the order of elements.
  • list.pop(): Removes and returns the last item from the list or the item at the specified index.
  • del statement can be used to remove items with their index.

List Comprehensions in Python

Creating Lists Concisely

  • Definition: A concise way to create lists where each element is the outcome of an expression applied to each element in another iterable.
  • Syntax: 
  new_list = [expression for element in iterable (if condition)]
  • Examples:
    • Basic comprehension:
      python whole_numbers = [x for x in range(10)]
    • Comprehension with condition:
      python even_numbers = [x for x in range(10) if x % 2 == 0]
  • Nested Comprehensions: Useful for creating more complex data structures.

Summary

  • Reinforcement of conceptual understanding of programming and Python’s built-in data structures, especially lists, ranges, and their functionalities.
  • Emphasis on understanding syntax and methods for effective code structuring and problem-solving strategies.