Design and Analysis of Algorithms

Announcements

• (June 11) Welcome to the course! As stated in canvas, this will be the place where most content will be hosted. I will post material that is relevant to this summer session in the Canvas page, and this will be announced as it happens.
• (June 25) The first set of notes have been posted! Be sure to bring some writing utensils or have it downloaded on a tablet before class begins.

Key Documents and Pages for the Course

• Make sure to read through the syllabus. I have outlined the expectations for myself and for you for this quarter amongst other things.

Teaching Staff and Contact Info

Instructor:

• Shion Fukuzawa
  • fukuzaws at uci dot edu
  • Office hours:
    • Friday 12-1pm, SSL140 (same room as lecture, right after Friday lecture)
    • Tuesday 1-2pm, Zoom. Link will be shared on Ed.

TAs:

• Ryuto Kitagawa
  • Office hours: Wednesday 2-3pm, SSL140 (same room as lecture, right after second discussion)
• Kourosh Mirsohi
  • Office hours: Monday 2-3pm, SSL140 (same room as lecture, right after second discussion)

Course Outline

The following is the breakdown of the three modules we will divide the class into.

• Module 1: Foundations/Divide and Conquer
  • [Done!] Big-Oh Notation and mathematical preliminaries
  • [Done!] Sorting Algorithms
  • [Done!] Proving the run time of merge sort and quicksort
• Module 2: Dynamic Programming:
  • Sorting lowerbounds
  • Optimal substructure property
  • Analyzing the size of the search space
  • Top-down (memoization) vs. Bottom-up
• Module 3: Greedy Algorithms:
  • Greedy choice property
  • Optimal substructure property
  • When can we use a greedy algorithm instead of a dynamic programming approach?

Lecture notes

• The following are digital copies of the lecture notes. I will post annotated versions as we progress through the course as well.

• Module 0: Preparation and Preliminaries

  • (unannotated notes, annotated notes)

• Module 1: Divide and Conquer

  • (unannotated notes, annotated notes)

• Module 2: Dynamic Programming

  • Week 1 (unannotated notes, annotated notes)
  • Week 2 (unannotated notes, annotated notes)
  • Week 3 (unannotated notes, annotated notes)

• Module 3: Greedy Algorithms + Graph Algorithms

(Note, these are two different topics though there are instance where they overlap.)

• Greedy Algorithms (unannotated notes, annotated notes)
• Graph Algorithms (unannotated notes, annotated notes)
• NP-Completeness (unannotated notes, annotated notes)

Problem Sets

Please submit your problem sets to gradescope. If you do not have access to gradescope, let me know ASAP. Solutions will be posted to Canvas.

Assignments will not be accepted after the due date. If you cannot solve a problem, please write down what you tried and where you are stuck.

• Homework 1: Due Monday July 8 11:59pm.
• Homework 2: Due Wednesday July 10 11:00am.
• Homework 3: Due Monday July 22 11:00am.
• Homework 4: Due Monday July 29 11:00am.
• Homework 5: Due Monday August 12 11:00am (Extended to 11:59pm).
• Homework 6: Due Tuesday August 20 11:59pm.

Midterm Information

• Midterm 1: Module 1 (Jul 12)
• Midterm 2: Module 2 (Jul 31)
• Midterm 3: Module 3 (Aug 23)