Fundamental Concepts in Computer Science & Algorithm Design

Core Learning Outcomes

  • Steps to Problem Solving: Identify and describe the four key phases required to take a problem from initial concept to a working software solution.
  • Algorithm Definition: Provide an accurate, formal definition of an algorithm, including all required properties.
  • Algorithm Design vs. Programming: Distinguish between the conceptual problem-solving phase (algorithm design) and the syntax translation phase (programming).
  • Language Levels: Contrast the characteristics and roles of natural languages, high-level programming languages, and machine languages.

Case Study: Practical Problem Solving in Automation

To illustrate how real-world computational problems are addressed, consider an administrative task in course management:

  • Background and Context:
    • A course instructor adopted a new textbook for COMP 1405 titled Automate the Boring Stuff with Python (2nd Edition): Practical Programming for Total Beginners by Al Sweigart (published by No Starch Press).

Automate the Boring Stuff with Python

*   Adopting the new textbook required updating the mandatory reading assignments and practice exercises for each lecture directly inside 40 separate presentation slide files.
*   When synchronizing course offerings with a colleague, it became necessary to extract all selected reading assignments from every presentation to share them.

  • The Problem:

    • Manually opening 40 individual PowerPoint slide decks to copy and paste reading assignments is tedious, repetitive, and time-consuming.
    • The goal was to construct a computer program capable of automatically parsing the files and extracting the relevant text.

  • Investigation and Research:

    • The first step was to locate an existing external software library capable of manipulating PowerPoint files in Python.
    • This led to the selection of the third-party library python-pptx (documented at https://python-pptx.readthedocs.io/en/latest/index.html).
    • Reviewing the library's official documentation revealed code examples showing how to iterate over slides, shapes, text frames, paragraphs, and text runs.

  • Language-Independent High-Level Design:

    1. Access every PowerPoint file present in a specific directory, processing them one at a time.
    2. Extract the text contained in the first slide (title information) and the third slide (reading assignments) of each presentation deck.
    3. Access each individual shape within a slide that possesses a text_frame to read paragraph text.
    4. Clean the extracted text by removing unnecessary static header words (e.g., stripping out recurring titles like "Mandatory Reading Assignment").

  • Code Reuse and Subproblem Solving:

    • The file traversal subproblem (finding files in target folders) was solved by reusing existing code structures utilizing standard Python modules such as os, glob, time, random, textwrap, subprocess, and itertools.

  • Implementation and Execution Iterations:

    • Syntax Errors: Initial run attempts produced syntax errors, such as incorrectly calling python-pptx functions or improper variable assignments.
    • Logical Errors: After fixing syntax, logical errors emerged—for instance, forgetting to strip out unneeded boilerplate text, causing extra unwanted headers in the generated output.
    • Final Result: Resolving these errors produced a script (extract_reading_assignments.py) that successfully processed all 40 decks via the Command Prompt, generating clean reading lists organized by lecture.

Script output in command prompt

The Four Steps to Problem Solving

Addressing any software challenge systematically involves four distinct stages:

  • 1. Understanding the Problem:

    • Involves brainstorming, research, identifying goals, defining constraints, and reviewing existing tools or documentation.

  • 2. Devising a Plan:

    • Creating a language-independent design or step-by-step logic.
    • Tools used include flowcharts, structured visual diagrams, and pseudocode.

  • 3. Carrying Out the Plan:

    • Translating the abstract design into executable source code using a specific programming language.

  • 4. Looking Back:

    • Executing the compiled or interpreted program.
    • Testing with various inputs, identifying and correcting syntax errors or logical errors, and refining performance.

Definition and Properties of an Algorithm

An Algorithm is defined formally as:

An Algorithm is a finite, ordered set of unambiguous instructions that defines a process that will eventually terminate.\text{An Algorithm is a finite, ordered set of unambiguous instructions that defines a process that will eventually terminate.}

  • Core Properties:

    • Finite Set: The total number of instructions and steps must be countable and bounded.
    • Ordered Set: Instructions are arranged in a strict, deterministic sequence.
    • Unambiguous Instructions: Every step must be completely clear and leave no room for multiple interpretations or ambiguity.
    • Defines a Process: Specifies the exact mechanics of execution to achieve a targeted goal.
    • Eventual Termination: Execution must halt after a finite number of steps; an infinite loop is not a valid algorithm.

  • Everyday Algorithms:

    • Instruction manuals, assembly guides (e.g., paper airplane folding instructions), and culinary recipes are familiar examples of algorithms.

  • Algorithm vs. Program:

    • An algorithm is the theoretical, conceptual sequence of steps designed to perform a task.
    • A program is a formal representation of an algorithm written in a code format that can be executed directly by a computer system.

Levels of Computer Languages and the Translation Pipeline

Computers and humans process information using fundamentally different categories of language:

  • Natural Languages:

    • Human-spoken languages (e.g., English, French).
    • Highly expressive, complex, context-dependent, and inherently full of ambiguities.

  • Machine Languages:

    • Low-level binary instructions (00s and 11s) executed directly by computer hardware and electronic circuitry.
    • Extremely difficult, error-prone, and tedious for humans to read, write, or maintain directly.

  • Programming Languages (High-Level):

    • Languages like Python 3 designed to bridge the gap between human thought processes and electronic circuits.
    • High-level languages resemble human natural languages and mathematical syntax, making algorithm representation structured yet readable.
    • Python 3 is a general-purpose, high-level programming language.
    • PEP 20 (The Zen of Python) Principle: "If the implementation is hard to explain, it's a bad idea. If the implementation is easy to explain, it may be a good idea."

  • The Translation Pipeline:

Natural Languages→Algorithm Design (Pseudocode / Flowchart)→Programming Languages→Compilation / Interpretation→Machine Languages\text{Natural Languages} \rightarrow \text{Algorithm Design (Pseudocode / Flowchart)} \rightarrow \text{Programming Languages} \rightarrow \text{Compilation / Interpretation} \rightarrow \text{Machine Languages}

Algorithm Design vs. Programming: The "Spotted Dog" Analogy

Humans do not naturally think in formal programming languages. Developing software requires separating problem-solving (algorithm design) from code expression (programming).

  • The "Spotted Dog" Quick Bread Recipe:
    • Category: Quick bread leavened without eggs or yeast.
    • Ingredients:
      • 4 cups4\text{ cups} all-purpose flour
      • 1 tbsp1\text{ tbsp} granulated sugar
      • 1 tsp1\text{ tsp} baking soda
      • 1 tsp1\text{ tsp} salt
      • 2 cups2\text{ cups} buttermilk
      • 1 cup1\text{ cup} raisins
    • Procedure Steps:
      1. Preheat the oven to 425∘F425^\circ\text{F} (220∘C220^\circ\text{C}).
      2. Whisk together the sugar, baking soda, and salt.
      3. Add the buttermilk, flour, and raisins.
      4. Lightly knead the dough into a single round loaf.
      5. Place loaf on a greased baking sheet.
      6. Bake for 35 minutes35\text{ minutes}.

Traditional Spotted Dog quick bread

  • Key Insight of the Analogy:
    • In this recipe, baking soda acts as the leavening agent, activated specifically by the acid in the buttermilk.
    • A human following this recipe does not need to understand chemical reactions to bake the loaf successfully. The chemical expertise has already been embedded into the design of the algorithm (the recipe).
    • Similarly, once familiar with syntax rules, the programming step is relatively mechanical. The primary intellectual challenge for a computer scientist resides in Algorithm Design—solving the problem conceptually so the execution can be carried out seamlessly.