Chapter 1_Introduction to Algorithms

algorithm

is a finite sequence of well-defined steps to solve a specific problem or perform a computation.

input,

output,

finiteness,

definiteness,

effectiveness

key property of algorithms (5)

input

zero or more quantities provided externally.

Output

at least one result produced.

Finiteness

terminates after a finite number of steps.

Definiteness

each step is precisely defined.

Effectiveness

steps are basic enough to be carried out

natural language description,

pseudocode,

flowchart,

programming language

4 mediums of algorithm

Natural language description

plain English

Pseudocode

structured, programming-like representation

Flowcharts

graphical representation with symbols

Programming languages

actual code, e.g., Python, C, Java

Bubble Sort,

Insertion Sort,

Merge Sort

examples of Sorting Algorithms (3)

Linear Search, Binary Search

examples of Searching Algorithms (2)

Dijkstra's Shortest Path, Breadth First Search (BFS)

examples of Graph Algorithms (2)

time, memory,

alternative solutions,

scalability,

formal analysis,

trade-offs

importance of designing and analyzing an algorithm (5)

• ensures efficiency in terms of _____ and _____,

• allows comparison between _____,

• helps identify _____ of solutions for large inputs,

• provides correctness guarantees through _____,

• balances _____ (e.g., time vs. space)

problem definition,

algorithm specification,

choose a design paradigm,

refinement

steps in designing an algorithm (4)

Problem Definition

understand input, output, and constraints.

Algorithm Specification

describe solution steps (pseudocode/flowchart).

Choose a Design Paradigm

• Divide and Conquer

• Greedy

• Dynamic Programming

• Backtracking

Refinement

simplify or optimize steps

correctness,

space complexity,

time complexity,

asymptotic analysis

analysis of an algorithm (4)

Correctness

Verify algorithm produces valid output.

Space Complexity

Measure memory usage.

Time Complexity

Count fundamental operations as function of input size.

Best Case,

Average Case,

Worst Case

Asymptotic Analysis

Big-O notation,

Omega Ω notation,

Theta Θ notation