Design and Analysis of Algorithms

CS 130B - Spring 2026


[ Home | Lectures ]

COURSE INFO


CLASS TIMES: Mon+Wed 12:30-1:45pm in ILP 2101


INSTRUCTOR:   Eric Vigoda,
TAs:   TBA
Office hours: (Check Ed Discussion)


TEXTBOOK: (required) Algorithms by Dasgupta, Papadimitriou, and Vazirani [DPV]
(Available at UCSB Bookstore or via Amazon)
(Note, exercise/section numbers may differ in unofficial online versions.)

Other good references:
Algorithms by Jeff Erickson
Algorithms Unlimited by Roughgarden
Algorithm Design by Kleinberg and Tardos
Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein
(Some of these books are available online from the library)


TOPICS COVERED:
  • Dynamic programming
  • Divide-and-conquer strategies including FFT
  • Linear programming
  • Max-flow
  • NP-completeness
  • (If time permits) RSA public-key cryptosystem

    • GRADING SCHEME:
    1. Homeworks: 15%
    2. Daily quizzes: 10% (drop lowest)
    3. 2 midterm exams: 50% (equally weighted)
    4. Final exam: 25% (see UCSB final exam schedule)
      (The final will be cumulative.)

    DAILY QUIZ: Posted on Gradescope immediately after class, due the following day. No extensions or late submissions. Drop the lowest quiz.
    EXAMS: 2 midterm exams plus a final exam, see the lecture schedule for tentative dates.
    No books, no notes, no calculators. We will provide scrap paper.

    DSP: If you have special accommodations for testing or homeworks then you should discuss it with me during the first week of classes.

    Exam Absences: If you have an institute approved absence around an exam date then notify the instructor at least 10 days in advance and email me a copy of the institute approved absence from the Dean of Students. If you are sick for an exam then you need to submit documentation to the Dean of Students and then email the instructor an excused absence letter from the Dean of Students (we cannot be privy to any medical information). There is no makeup exam; the final exam will be used to account for any excused missing exam.

    Cheating:
    Any evidence of cheating or plagarism on homeworks or exams will be immediately reported to the Office of Student Conduct.
    You will be given a zero on that aspect (total homework grade for the course or that exam) AND your overall course grade will be lowered by one letter.
    There are typically multiple versions of the exam so it is easy to identify students who copy from other students.

    HOMEWORK POLICIES:
     Submissions:
    Homeworks are submitted via Gradescope.
    No late homeworks or quizzes. Check your Gradescope submission before the deadline.

    Collaboration:
    Homework solutions must be in your own words.
    You can not consult or look at any sources (including the web or your classmates) for solutions to the homework.
    It is probably best to try the homework on your own first. For the challenging problems, it might be useful to work together with other students. However, you should redo the solution from scratch by yourself, and write it up in your own words.
    List at the top of your homework who you collaborated with.
    Note homeworks are not worth much, the point of homeworks is to practice and learn the material so copying the solutions does not serve much purpose.
    We will typically do a fast grading of the homeworks and only of a subset of the problems, so you should double-check the solutions yourself.