Intro

CS 161 Design and Analysis of Algorithms #

About the course #

Course goals #

  • The design and analysis of algorithms
    • These go hand in hand
  • In this course
    • Learn to think analytically about algorithms
    • Flesh out an “algorithmic toolkit”
    • Learn to communicate clearly about algorithms

Guiding questions #

  • Does it work?
  • Is it fast?
  • Can I do better?
  • Should it work?
  • Should it be fast?

Logistics #

Lectures

  • Mon/Wed 9:45 - 11:15
  • First two weeks: On Zoom (link on Canvas)
  • Later: In person (NVIDIA auditorium)

Resources

  • Slides
  • Videos
  • Notes
  • IPython Notebooks
  • Concept check questions

Homework

  • Weekly, assigned Wednesdays at 12:30 pm and due the next Wednesday at 11:59 pm
  • Two parts: exercises and problems
    • Do exercises individually
    • Try the problems individually before discussing them
    • Can exchange ideas with classmates, but must write up solutions individually
    • Cite all collaborators as well as sources used

Exams

  • Midterm: Feb 7-8 (48 hr window)
  • Final: Wed Mar 16, 3:30pm-6:30pm

Grading:

  • Weighting: HW (50%), Midterm (20%), Final (30%)
  • Lowest of 8 homework scores dropped

Interaction with course staff

  • Ed discussion forum
  • Office hours (on Nooks)
  • Sections (on Zoom)
    • Thursdays and Fridays
    • Optional but recommended

Why algorithms? #

Algorithms are fundamental #

Applications:

  • Operating systems (CS140)
  • Machine learning (CS229)
  • Cryptography (CS255)
  • Compilers (CS143)
  • Networking (CS144)
  • Computational biology (CS262)

Algorithms are useful #

  • As inputs get bigger and bigger, have good algorithms becomes more and more important

Integer multiplication #

  • Problem: take two n-digit numbers and multiply them
  • Grade-school multiplication: takes roughly n2 one-digit operations
    • Scales the same whether by hand or implemented in code
  • Wizard’s algorithm: O(n1.6)

Divide and Conquer #

  • Ex. 1234 x 5678
  • = (12x100 + 34)(56x100 + 78)
  • = (12x56)10000 + (34x56 + 12x78)100 + (34x78)
  • = …

Algorithm Multiply(x, y)

  • if n == 1:
    • return xy
  • Write x = a(10n/2 + b)
  • Write y = c(10n/2 + d)
  • Recursively compute ac, ad, bc, bd
    • ac = Multiply(a, c) etc…
  • Add them up to get xy:
    • xy = ac(10n) + (ad + bc)(10n/2) + bd

Runtime: at each recursion step, we break a 2n-digit problem into 4 n-digit problems. This results in O(n2) performance.

Karatsuba multiplication #

  • Recursively compute:
    • ac
    • bd
    • (a+b)(c+d) = ac + bd + bc + ad
  • Subtract off ac and bd from (a+b)(c+d) we get (ad + bc) and can get the product
  • Runtime: 3log2 n ~= n1.6