Instructor: Luca Foschini (email: foschini@cs.ucsb.edu) (twitter: @calimagna)

Format: lecture and hands-on

Announcements:

• Lunch with Prof. Alberto Busetto (ECE) at 12noon
• Afternoon class (Introduction to Graph Algorithms) starts at 1.30pm
• Take some time at the end of hte day to take the daily survey

Goals

• Learn about complexity classes, efficient algorithms
• Learn about basic data structures
• Identify hard problems and provide approximated solutions.

Before you Begin

• Commit your code locally
• do a git pull

Intro

• Why are we where today? Computational thinking as your guiding spirit
• Supercharge your productivity! Efficiency is key
• Algorithms, Idioms of modern science

Time complexity

• Big-O notation, time complexity examples (O(1), O(logn), O(n)). The importance of constants.
• Recursion, recurrences, examples: peak finding, dynamic arrays.
• Searching: binary, hash tables, pandas indexing, bloom filters
• Top-k queries, geometric queries.
• Sorting with examples
• NP-Hardness, approximation algorithms (example: exponential bucketing).
• Mini Project

Beyond:

• Google coding interviews
• Programming contests IPSC/ACM Collegiate Programming/IOI
• Algorithmic resources: Introduction to Algorithms