Intro

# CS 161 Design and Analysis of Algorithms #

### 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

• 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