Big-O notation

Topic 1: Algorithms

  • Course context and framing

    • Course code and title: EECS 376: Foundations of Computer Science (theoretical CS)
    • Instructors: Emily Graetz (they/them); Nicole Wein; Course Staff; GSIs: 3; IAs: 6; Graders: ~10; Admin Support: Rose, Sherry, Esti Stoian
    • Course aim: Address challenging computational problems by asking whether a computer can solve them, and if so, how to solve efficiently and correctly. If not solvable, prove impossibility; if solvable, design algorithms, analyze worst-case running time, and prove correctness.
    • Emphasis on rigorous, proof-based reasoning and comfort with discomfort/intractability as part of learning.

  • Learning objectives (summary)

    • Determine solvability of computational problems and, if solvable, design algorithms, analyze worst-case running time, and prove correctness.
    • Be comfortable with major paradigms:
    • Divide-and-conquer, greedy, dynamic programming, the power of randomness
    • Computability
    • NP-completeness and approximation algorithms
    • Cryptography
    • Approach problems in a principled, rigorous way; expect cognitive challenge and potential initial wrong ideas; use strategies to improve understanding (office hours, Piazza, study groups).

  • Why study CS foundations? (Top 7 reasons)

    • 1) Theoretical ideas underpin software and systems (hardware design, Internet routing, cryptography, search/privacy, etc.). Moore’s Law context: performance gains from algorithms can exceed hardware speedups. extMoore′sLawandalgorithmicgainsext{Moore's Law and algorithmic gains}
    • 2) Ensure code correctness and efficiency; theory helps avoid incorrect or intractable programs; quote: "For every complex problem there is an answer that is clear, simple, and wrong." — H. L. Mencken
    • 3) Some problems may be provably impossible; theoretical understanding helps recognize unsolvability.
    • 4) Help with interviews; fundamental concepts transfer to many comp-sci roles.
    • 5) Fundamentals apply to any computer system, across time.
    • 6) Computation appears in many domains (economics/game theory, collective behavior, brain/computation interfaces) – e.g., auctions, matching markets.
    • 7) Theoretical CS reveals inherent beauty and deep connections to math.

  • Course structure and topics (major blocks)

    • Algorithm design & analysis (7 lectures)
    • Computability theory (6 lectures)
    • Complexity theory (6 lectures)
    • Randomized algorithms (3 lectures)
    • Cryptography (3 lectures)
    • Special topics (1 lecture)
    • Emphasis on techniques, rigorous modeling, and proofs throughout.

  • How to succeed in 376 (advice / cheat codes)

    • Attend lectures for key ideas, frameworks, and examples; engage in discussions for reinforcement; use office hours for detailed questions; participate in Piazza.
    • Reproduce proofs from lectures, notes, and homeworks; form collaboration groups to critique each other’s thinking.
    • HWs should be “essentially done” by Tuesday; write-ups should be careful.
    • Use Piazza to ask and answer questions (search first).

  • Course logistics (where to find resources)

    • Website: eecs376.org
    • Resources: Syllabus, Schedule with shared events, Course Notes, Files (HWs, slides, worksheets), Lecture recordings, Gradescope (HW/exam submission and grading), Piazza, Admin form for accommodations, Emily’s office hours (Mon/Wed 12-1pm, location TBD), and potential after-hours questions.

  • Assignments and exams (administration)

    • 12 weekly HW assignments; due Wednesdays 8pm; submissions open until 9:59pm with 5% penalty; staff help until 8pm; two lowest HW scores dropped; solutions published after deadline.
    • HW1 posted by the Wednesday evening; due next Wednesday at 8pm.
    • Midterm: Monday, Oct 20, 7–9pm.
    • Final: Friday, Dec 12, 7–9pm.
    • Collaboration is encouraged; AI use not permitted on HW.
    • Grading reference (from syllabus): at least 45% exam average to pass; attendance in discussions can affect the 3% discussion component; other components include course evaluations; lowest 2 HW scores dropped.

  • Are we an EECS class or math class?

    • The course blends EECS and mathematics; the only way to answer questions is to define mathematical models and use rigorous proofs.
    • Why do we do proofs? To ensure correctness and to foster understanding.

  • A note on the scope of topics: Theoretical CS connects to practical CS and beyond

    • Examples of connections: hardware design, cryptography, routing, search, and modern software systems rely on deep theory.
    • The course emphasizes thinking about problems in a principled way, not just coding tricks.

  • Topic 1: Algorithms (introduction)

    • Historical context:
    • 300 BCE: Euclid describes algorithms (e.g., GCD) that endure today.
    • 825 CE: al-Khwarizmi writes On the Calculation with Hindu Numerals; origin of the term algorithm.
    • 1837: Charles Babbage designs Analytical Engine (mechanical computer, not completed).
    • 1842: Ada Lovelace writes first algorithm for computer implementation (Bernoulli numbers).
    • Today and next time: continue exploration of algorithmic ideas.

  • Key concept: Input size and running time

    • Running time expressed as a function of input size n.
    • Common interpretations of input size (space to store it):
    • size of array = narrayn_{array}
    • size of graph = ngraphn_{graph}
    • size of integer = nintn_{int}
    • Rule of thumb: size is the number of bits to represent input; often: #elements, #vertices + #edges, or #digits (or #bits)

  • Running time and asymptotic analysis

    • Different computers may take different number of steps on the same algorithm; that’s okay.
    • Worst-case running time: as a function of input size, denoted by T(n)T(n).
    • Polynomial vs exponential intuition:
    • Efficient: running time polynomial in input size, e.g., O(nk)O(n^k) for some constant k.
    • Exponential: typically of the form 2extpoly(n)2^{ ext{poly}(n)} or similar; grows much faster as n increases.
    • Big-O notation basics:
    • Formal: $$f(n) = O(g(n)) \