Design and Analysis of Algorithms, Summer 2023

Welcome to CS 161: Design and Analysis of Algorithms! Have you ever wondered why Google Maps, Apple Maps, and Waze all have different routes between places? How the Google search button works so quickly? In this class, we will look at the fundamental building blocks behind the above questions and how to solve them efficiently. Our goal is for you to come out of here a better problem solver: we’ve seen first hand that algorithmic problem solving skills can translate to real life.

Although this course is all about the theoretical design of algorithms, there will be plenty of practice problems (for all of you technical interview aficionados)! On the note of technical interviews, it seems that recent interviews have been venturing further into the “competitive programming data structures” realm. We will be exploring a little bit into this area in the course, which we hope will be a fun experience for all of you!

Quick Links

<aside> 🔊 Please fill out the accommodations form!

</aside>

<aside> 📣 Please fill out the feedback form!

</aside>

<aside> 📜 Syllabus

</aside>

<aside> <img src="https://i.imgur.com/IDr6yqp.png" alt="https://i.imgur.com/IDr6yqp.png" width="40px" /> Gradescope

</aside>

<aside> <img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/5f289d26-19c2-40b2-b98d-95adc357e8be/Screenshot_2023-06-20_at_03.27.03.png" alt="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/5f289d26-19c2-40b2-b98d-95adc357e8be/Screenshot_2023-06-20_at_03.27.03.png" width="40px" /> EdStem

</aside>

<aside> 🔊 Lectures

</aside>

<aside> 🚄 Sections

</aside>

<aside> <img src="https://emojis.slackmojis.com/emojis/images/1567179639/6288/zoom.png?1567179639" alt="https://emojis.slackmojis.com/emojis/images/1567179639/6288/zoom.png?1567179639" width="40px" /> Zoom (link on Canvas)

</aside>

<aside> <img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/8f879630-87a6-47ed-bc54-af639175e09a/canvas.png" alt="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/8f879630-87a6-47ed-bc54-af639175e09a/canvas.png" width="40px" /> Canvas

</aside>

<aside> ✍️ Homeworks

</aside>

Schedule

Week Monday Wednesday Friday
Week 1 (6/26 - 7/2) Introduction & Karatsuba’s Algorithm (Homework 1 Released Tuesday) Asymptotics, Worst-Case Analysis, and MergeSort More recurrences, the master theorem, and the substitution method
Week 2 (7/3 - 7/9) More substitution method and the selection problem Randomized Algorithms and QuickSort (Homework 1 Due) Quiz 1
Week 3 (7/10 - 7/16) BucketSort, RadixSort, and Sorting Lower Bounds (Homework 2 Released Tuesday) Binary and Ternary Search Heaps, Binary Search Trees, and Treaps
Week 4 (7/17 - 7/23) Segment Trees (Homework 2 Due Tuesday) Hashing! (Homework 3 Released) Quiz 2
Week 5 (7/24 - 7/30) Graphs, BFS, and DFS (Homework 4 Released Tuesday) Finding Strongly Connected Components (Homework 3 Due) Shortest Paths 1: Dijkstra’s Algorithm
Week 6 (7/31 - 8/6) Shortest Paths 2: Bellman-Ford and Floyd-Warshall (Homework 4 Due Tuesday) (Homework 5 Released Tuesday) More Dynamic Programming Quiz 3
Week 7 (8/7 - 8/13) Greedy Algorithms (Homework 5 Due Tuesday) (Homework 6 Released Tuesday) Minimum Spanning Trees Max Flow and the Ford-Fulkerson Algorithm
Week 8 (8/14 - 8/20) Global Min-Cut (Homework 6 Due Tuesday) Review! (Saturday) Final, Quiz 4

Daily Schedule

https://calendar.google.com/calendar/embed?src=10d062d9e207aff209f5bbcb94337766540ffd1010648a44e28e320f688641e8%40group.calendar.google.com&ctz=America%2FLos_Angeles