Design and Analysis of Algorithms

Class Overview

The objective of CSE 101 is to teach students the basics of the design and analysis of algorithms, and make them think algorithmically. We will cover general algorithmic techniques such as dynamic programming, divide and conquer, greedy algorithms and basic graph algorithms. We will stress on computational hardness, what is easy to solve vs what is hard, and look into modern day algorithms that go beyond traditional RAM design such as streaming algorithms, dynamic algorithms, and approximation algorithms.

Instructor: Barna Saha, barnas@ucsd.edu, Office Hours: After class on Tue (starting Jan 25th, before by appointment).

Teaching Assistants:

Shashwat Agrawal, sagrawal@ucsd.edu, Office Hours: Friday 3-5 pm (Zoom: https://ucsd.zoom.us/j/8929511298)

Daniel Kleber, dkleber@ucsd.edu, Office Hours: Wednesday 11:30 am - 1:30 pm (Zoom: https://ucsd.zoom.us/j/98058146614)

Raaghav Ravi, rravi@ucsd.edu, Office Hours: Tuesday 11:30 am - 1:30 pm (Zoom: https://ucsd.zoom.us/j/5360925097)

Minh Nhat Vo, m9vo@ucsd.edu, Office Hours: Thursday 11:30 am - 1:30 pm (Zoom: https://ucsd.zoom.us/j/7451905610)

Menghe Zhang, mez071@eng.ucsd.edu, Office Hours: Mon 10 am - 12 pm (Basement 270, Zoom: https://ucsd.zoom.us/j/99907039079)

Time & Venue: 9:30 am-11:00 am Tue/Thur. Over Zoom, at the following link.

Zoom Link: https://ucsd.zoom.us/j/99282267129

The first day of the class will be on Jan 4th.

Discussion Session: Fri 11:00 am - 11:50 am

Zoom Link: https://ucsd.zoom.us/j/94757049695

Piazza: All class related discussions will happen through piazza. Please sign up using the following link.

Piazza Sign Up Link

Gradescope: If you are not already enrolled, use the entry code N8DG8Y.

Grading:

• Homework (5) — 30%

  • Will consist of mathematical problems and programming assignments. To be done in a group of 1-4.

• Midterm 1 — 15% (January 27th), Midterm 2- 15% (February 22nd)

  • Midterms will take place in class.

• Final — 30% (March 15th)

• Weekly Quizzes — 10%. To be done individually.

Books We will use the following as text book, and use select materials from outside to cover newer developments in algorithm design.

• Algorithms by Dasgupta, Papadimitrou, and Vazirani

Prerequisite: CSE 12, CSE 21, CSE 100

Class Website: https://sites.google.com/eng.ucsd.edu/cse101-saha