COS 102: exhaustive Guide to Problem Solving and Python Programming

Problems and Problem-Solving

A problem is defined as a situation or question that requires a solution. It may present as a challenge, obstacle, or difficulty that must be overcome to reach a specific goal.
Problems are inherent to life, making problem-solving skills essential for success in career, academic, and personal settings.

Types of Problems

Routine Problems
- These are well-defined problems with a clear solution path.
- They are typically solved using established procedures, algorithms, or formulas.
- Examples include:
  - Mathematical calculations, such as solving an algebraic equation.
  - Technical troubleshooting, such as resolving a computer error.
  - Everyday tasks, such as following a recipe to cook a meal.
- Approaches to Routine Problems:
  - Following a step-by-step process.
  - Applying known rules or formulas.
  - Utilizing specialized tools or resources designed for that specific problem.
Non-Routine Problems
- These are poorly defined problems that lack a clear path to a solution.
- Solving them requires critical analysis, creative thinking, and innovative solutions.
- Examples include:
  - Designing a marketing campaign for a brand-new product.
  - Resolving a complex ethical dilemma.
  - Writing a persuasive essay.
- Approaches to Non-Routine Problems:
  - Breaking the problem into smaller, manageable sub-parts.
  - Brainstorming to generate multiple potential solutions.
  - Evaluating and refining those ideas.
  - Collaborating with others to obtain diverse perspectives.

The Problem-Solving Process

i. Identify the Problem: Clearly define the specific issue or challenge being faced.
ii. Gather Information: Research and collect all relevant knowledge or data.
iii. Generate Possible Solutions: Brainstorm a variety of different approaches or options.
iv. Evaluate Solutions: Perform an analysis of the pros and cons of every potential solution.
v. Choose the Best Solution: Select the option that is most feasible and effective.
vi. Implement the Solution: Put the chosen strategy into action.
vii. Review the Results: Assess the outcomes of the implementation and make adjustments if needed.

Methods of Solving Computing Problems: Algorithms and Heuristics

Algorithms
- An algorithm is a step-by-step procedure or set of rules for solving a specific problem or completing a task.
- Properties and Characteristics:
  - Well-defined: Every step is clear and unambiguous.
  - Finite: The process must terminate after a finite number of steps.
  - Correct: It must produce the correct output for all valid inputs.
  - General: It should be applicable to a whole class of similar problems.
- Examples of Algorithms:
  - Sorting algorithms (e.g., bubble sort, merge sort, quicksort).
  - Searching algorithms (e.g., linear search, binary search).
  - Graph algorithms (e.g., shortest path, minimum spanning tree).
  - Numerical algorithms (e.g., finding roots of equations, numerical integration).
- Applications: Essential in software development, artificial intelligence, data processing, and scientific computing.
Heuristics
- A heuristic is a rule of thumb, shortcut, or educated guess used to find a solution. It does not guarantee that the solution will be optimal or correct.
- Properties and Characteristics:
  - Approximate: It provides a "good enough" solution within a reasonable timeframe.
  - Flexible: It is adaptable to variations in the problem.
  - Intuitive: It is often based on common sense, experience, or intuition.
- Examples of Heuristics:
  - Greedy algorithms: Making locally optimal choices at each step with the hope of reaching a global optimum.
  - Hill climbing: Iteratively making small changes to a solution to improve it.
  - Simulated annealing: Allowing occasional "bad" moves to escape local optima.
  - Genetic algorithms: Mimicking natural selection to evolve solutions over time.
- Applications: Used when finding an optimal solution is too computationally expensive, infeasible, or when problems are ill-defined and complex.

Algorithms vs. Heuristics: A Comparison

Guarantee: Algorithms always produce a correct or optimal solution (if one exists), while heuristics may or may not produce the best solution.
Computational Cost: Algorithms can be expensive, especially for complex problems; heuristics are generally faster and less demanding.
Scope: Algorithms are for well-defined problems with clear objectives; heuristics are for ill-defined or complex problems.
Optimality: Algorithms focus on the best possible solution; heuristics focus on a "good enough" solution in reasonable time.

Solvable and Unsolvable Problems

Solvable Problems
- Defined as problems with a definite solution or set of solutions reachable within a finite time using available resources.
- Characteristics:
  - Well-defined goals, constraints, and success criteria.
  - Sufficient information available to understand the problem.
  - Access to necessary tools, knowledge, and expertise.
  - Feasibility within practical limitations of cost and time.
- Examples:
  - Finding the roots of a quadratic equation using mathematical formulas.
  - Determining drug effects through scientific experiments.
  - Designing a bridge to withstand specific loads.
  - Planning a daily schedule or budget.
Unsolvable Problems
- These have no solution or have solutions impossible to reach due to contradictions, inherent limitations, or resource lack.
- Characteristics:
  - Ill-defined or paradoxical (vague or logically impossible).
  - Insufficient or contradictory information.
  - Lack of necessary expertise or tools.
  - Inherent constraints from social norms, ethical principles, or physical laws.
- Examples:
  - Mathematical paradoxes like the "halting problem" (determining if a program halts or runs forever).
  - Philosophical questions about free will or the meaning of life.
  - Complex social issues like eliminating poverty or world peace.
  - Scientific limitations like reversing the arrow of time or traveling faster thanlight.

Strategies for Dealing with Unsolvable Problems

i. Reframe the problem: Redefine it to make aspects solvable or focus on manageable parts.
ii. Set realistic goals: Aim for incremental improvements or partial solutions rather than a complete one.
iii. Manage the consequences: Develop strategies to cope with and mitigate negative effects.
iv. Accept limitations: Recognize current capability boundaries and learn to live with ambiguity.

Solution Techniques for Effective Problem Solving

1. Abstraction: Focusing on essential features while ignoring irrelevant details (e.g., using a diagram to represent a system).
2. Analogy: Applying a solution strategy from a previously solved similar problem (e.g., comparing computer malware to a biological virus).
3. Brainstorming: Generating many solutions without judgment before refining them (e.g., mind maps).
4. Trial and Error: Testing different solutions until one works (e.g., experimenting with recipe ingredients).
5. Hypothesis Testing: Formulating and testing a cause-of-problem theory (e.g., consumer surveys).
6. Reduction: Breaking a complex problem into smaller sub-problems (e.g., dividing a research project into tasks).
7. Lateral Thinking: Approaching a problem from unexpected perspectives (e.g., solving puzzles using riddles).
8. Means-End Analysis: Identifying a goal and working backward to determine steps (e.g., mapping a route from the destination).
9. Method of Focal Objects: Combining features of different objects for innovation (e.g., inventing a product by merging existing features).
1. Morphological Analysis: Exploring all combinations of parameters (e.g., designing vehicles by combining engine, body, and fuel types).
1. Research: Gathering relevant information (e.g., a literature review).
1. Root Cause Analysis: Identifying the underlying cause rather than just symptoms (e.g., investigating why a machine breaks repeatedly).
1. Proof: Using logic and evidence to validate a solution (e.g., mathematical theorems).
1. Divide and Conquer: Solving independent sub-problems and combining them (e.g., sorting sub-lists in a large list of numbers).

General Problem-Solving Process and Solution Formulation

1. Problem Definition: Stating the problem, desired outcome, and constraints. Identifying inputs (known info) and outputs (desired results).
2. Information Gathering: Researching data, identifying assumptions/limitations, and considering multiple perspectives.
3. Solution Generation: Brainstorming options, considering feasibility, and breaking solutions into steps.
4. Solution Evaluation: Analyzing pros and cons, required resources, and impact to choose the most promising solution.
5. Solution Implementation: Developing a detailed plan, testing, refining, monitoring, and adjusting results.

Solution Formulation & Design Techniques

1. Flowcharts: Graphical representations using symbols (input/output, decisions, processes).
- Advantages: Visual clarity, easy to follow, identifies logic errors.
- Disadvantages: Can become complex for large problems; poor for detailed data manipulation.
2. Pseudocode: High-level informal description using natural language and programming constructs.
- Advantages: More expressive than flowcharts, focuses on logic without syntax constraints, bridges human thought and code.
- Disadvantages: Can be ambiguous; not executable.
3. Decision Tables: Tabular representation of complex logic showing conditions and actions.
- Advantages: Concise for multiple conditions; great for debugging and testing.
- Disadvantages: Hard to read if large; less intuitive for sequential processes.
4. Decision Trees: Tree-like diagrams showing decisions and consequences.
- Advantages: Visualizes hierarchical decision-making and outcomes/probabilities.
- Disadvantages: Can become unwieldy; might miss situational nuances.

Implementation, Evaluation, and Refinement

Implementation: The process of converting a program design into actual code.
Translating Algorithms to Code (5 Steps):
- 1. Understanding the Algorithm: Analyzing the problem, logic, inputs, and outputs.
- 2. Choosing a Programming Language: Based on the problem nature, platform, and programmer familiarity (e.g., Python for data science, JavaScript for web).
- 3. Translating the Algorithm: Writing instructions in the language syntax using good practices (meaningful names and comments).
- 4. Testing: Running the program with different inputs to check outputs.
- 5. Debugging: Identifying and fixing errors.
Evaluation: Process of ensuring code works correctly.
- Types of Testing:
  - Unit Testing: Testing individual functions in isolation.
  - Integration Testing: Testing how components work together.
  - System Testing: Testing the entire program as a whole.
- Debugging Techniques:
  - Print Statements/Logging: Tracking variable values (e.g., print() in C or the logging module in Python).
  - Debuggers: Using IDE tools like breakpoints and variable inspection.
  - Code Review: Peer review to find errors.
Refinement (Optimization and Improvement):
- Code Readability:
  - C: Consistent indentation, meaningful names, comments.
  - Python: Following the PEP 8 style guide.
- Code Maintainability: Achieved via modular design, clear documentation, and well-structured code.
- Code Efficiency:
  - C: Algorithm optimization, efficient data structures, minimizing computations.
  - Python: Using built-in functions/libraries and avoiding inefficient loops.
- Profiling Tools: Used to identify performance bottlenecks.

Python Programming Language

Introduction: Released by Guido van Rossum in 1991 (version $0.9.0$ ). It is currently the most popular language due to tech industry demand.
Features of Python:
- Easy to use and read: Clear syntax reduces development time and errors.
- Dynamically Typed: Variable types are determined during run-time; no need to specify them in code.
- High-level: Human-readable code.
- Compiled and Interpreted: Compiled to bytecode then interpreted line by line. The default implementation is CPython.
- Garbage Collected: Automatic memory management.
- Purely Object-Oriented: Everything, including strings and numbers, is an object.
- Cross-platform: Runs on Windows, macOS, and Linux.
- Rich Standard Library: Provides ready-to-use modules for machine learning, networking, etc.
- Open Source: Cost-free and widely utilized.
Applications of Python:
- Data Science: Uses NumPy, Pandas, and Matplotlib.
- Desktop/Console Apps: Uses PyQt, Tkinter; supports input/output redirection.
- Mobile: Kivy and BeeWare frameworks for cross-platform apps.
- AI/Machine Learning: TensorFlow, Keras, PyTorch, and Scikit-learn.
- Web Development: Backend (Django, Flask) and Frontend (JavaScript, HTML, CSS).
- 3D CAD: Blender.
- Computer Vision: OpenCV and Scikit-image.
- Others: Scientific computing (SciPy), Game development (Pygame), IoT (Raspberry Pi/Arduino), DevOps (automation), Finance (Statsmodels), Audio (Music21).

Why Python?

Works on various platforms.
Simple syntax similar to English.
Allows developers to write fewer lines of code.
Uses an interpreter system, allowing for quick prototyping.
Supports procedural, object-oriented, and functional programming styles.
Versions: Python 3 is the most recent major version; Python 2 is still popular for security legacy reasons. Common IDEs include Thonny, Pycharm, Netbeans, and Eclipse.

Python Basic Syntax

General Rules:
- No curly braces or semicolons are used.
- Indentation (whitespace) defines blocks of code. Typically four whitespaces are used.
- Statements end with a NewLine character.
- Case-sensitive (e.g., name and Name are different variables).
- Comments: Use the # symbol.
- Keywords: Reserved words like if, for, while, try, except cannot be used as variables.
Indentation Examples:
- $if 5 > 2:$
- $\quad print("Five is greater than two!")$
- Skipping indentation results in a Syntax Error.

Python Variables and Constants

Variables:
- Containers for storing data values. They act as addresses in memory.
- Created upon assignment (e.g., $x = 5$ ). No declaration command.
- Dynamic typing: A variable can change type (e.g., $x = 4$ then $x = "Sally"$ ).
- Casting: Specifying type using str(), int(), or float().
- Naming: Must start with a letter or underscore; no numbers or special characters (, $, %, *); case-sensitive.
- Patterns: Camel case ( $kmPerHour$ ), Pascal case ( $KmPerHour$ ), Snake case ( $km\_per\_hour$ ).
Variable Scope:
- Global Variables: Created outside a function; usable by everyone.
- Local Variables: defined inside a function; cannot be accessed outside.
Constants:
- Not formally defined in Python.
- Indicated by "screaming snake case" (all-caps with underscores), e.g., $PI\_VALUE$ .

Python Data Types

Standard Data Types:
- 1. Numbers: Int (whole numbers), Float (decimal point, accurate to $15$ places), Complex (real + imaginary, e.g., $2.0 + 2.3j$ ).
- 2. Sequence Type:
  - String: Characters in single, double, or triple quotes.
  - Lists: Ordered collection, square brackets $[]$ , can contain different types.
  - Tuple: Like lists but immutable, enclosed in parentheses $()$ .
- 3. Boolean: True and False ( $1$ and $0$ ).
- 4. Set: Unordered, non-indexed collection in curly braces ${}$ ; items cannot repeat.
- 5. Dictionary: Key-value pairs in curly braces (e.g., $\{1:\text{'one'}\}$ ).

Python Operators

1. Arithmetic Operators:
- Addition: $+$ (e.g., $5 + 2 = 7$ )
- Subtraction: $-$ (e.g., $4 - 2 = 2$ )
- Multiplication: $*$ (e.g., $2 \times 3 = 6$ )
- Division: $/$ (e.g., $10 / 3 = 3.3$ )
- Floor Division: $//$ (e.g., $10 // 3 = 3$ )
- Modulo: $\%$ (e.g., $5 \% 2 = 1$ )
- Power: $**$ (e.g., $4 ^{2} = 16$ )
2. Assignment Operators:
- $=, +=, -=, *=, /=, \%=, **=$
3. Comparison Operators (Return Boolean):
- $==, !=, >, <, >=, <=$
4. Logical Operators:
- and: True if both operands are True.
- or: True if at least one operand is True.
- not: Reverses the boolean state.
5. Bitwise Operators:
- $\&$ (AND), $|$ (OR), $\sim$ (NOT), $\wedge$ (XOR), $>>$ (Right shift), $<<$ (Left shift).
- Example: $10$ is $0000 1010$ , $4$ is $0000 0100$ . $10 \& 4 = 0$ .
6. Special Operators:
- Identity: is, is not (check if values occupy the same memory location).
- Membership: in, not in (test if value exists in a sequence or dictionary key).

Python Control Structures

Sequential: Statements execute in default linear order.
Selection (Decision/Branching):
- if: Executes block if condition is True.
- if-else: Executes if body if True, else body if False.
- nested if: An if statement inside another.
- if-elif-else: Checks multiple conditions; executes the first True block or the final else if all are False.
Repetition (Looping):
- for loop: Iterates over a sequence (list, tuple, dict, set).
- while loop: Repeatedly executes a block while a condition remains True.

Python Modules and Libraries

Modular Programming: Breaking large tasks into shorter, logical subtasks.
Modules:
- Files with a $.py$ extension containing definitions and statements.
- Built-in Modules: math (constants/trig), datetime (time manipulation), os (OS interaction), random (random integers), json (API data), re (regular expressions), collections, numpy, pandas, requests.
- User-defined Modules: Custom codes saved as $.py$ files.
- External Modules: Downloaded via pip install module_name.
Libraries:
- Umbrella term for collections of modules grouped under one name.
- Examples: Django/Flask (web), Tkinter (GUI), TensorFlow/Scikit-learn (ML), Pygame (gaming), Kivy (multi-touch), BeautifulSoup (scraping), NLTK (language processing).
Key Differences:
- Module: Single file; used for code readability and DRY (Don't Repeat Yourself) principle.
- Library: Collection of modules/packages; usually installed via pip.
- dir() function: Returns a sorted list of strings containing names defined in a module.
- help() function: Used to get information about libraries.

Python Basic Input and Output

Output:
- Uses print() function.
- Syntax: print(object, sep, end, file, flush).
- sep: Separator between items (default is space).
- end: Value at the end of the print (default is newline \n).
Input:
- Uses input(prompt) function.
- Returns input as a string; must use int() or float() for numerical conversion.
- Example: $Num = int(input("Enter a number: "))$ converts string input to an integer.