CS 130b: Data Structures and Algorithms (Winter 2018)

General Information

Instructor: Huijia (Rachel) Lin, rachel.lin(at)cs(dot)ucsb(dot)edu

TAs and Reader:

  • TA: Adam Ibrahim, email: ai (at) cs (dot) ucsb (dot) edu
  • TA: Burak Kadron, email: kadron (at) cs (dot) ucsb (dot) edu
  • Reader: Santha Meena Ramamoorthy, santhameena (at) ucsb (dot) edu

Time and location:

  • Class: Mon/Wed 11:00 am - 12:15 pm, PSYCH 1902
  • Session 1: Thursday 5:00-5:50pm, GIRV 2112
  • Session 2: Thursday 6:00-6:50pm, GIRV 2115

Office hours:

  • Adam Ibrahim: TBA
  • Burak Kadron: TBA
  • Rachel Lin: Monday 4:30-5:30pm, HFH 1153

Piazza: We will be using Piazza for class-related discussions. The Piazza page for this class is available HERE.

Course Description

Design and analysis of computer algorithms. Correctness proofs and solution of recurrance relations. Design techniques; divide and conquer, greedy strategies, dynamic programming. Applications of techniques to problems from several disciplines. NP-completeness.

Prerequisite: CS130a


The class roughly follows the following textbook:
  • Jon Kleinberg and Eva Tardos. Algorithm Design
Additional great resources that will help you to learn are:
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms (third edition)
  • Mark Allen Weiss. Data Structures and Algorithms Analysis (in C++, or any other edition)


There will be four homework assignments, couting 40%, one programming assignments, counting 10%, and one midterm exams, counting 20%, and one final, couting 30%. At the end of the class, a weighted sum between 0 and 1 will be calculated for each student according to his/her grades in each part above. Finally, the letter grade of each student is determinied according to the distribution the weighted sums of the entire class.

Class Policy:

  • For homework and programming assignements, no late submissions are accepted, unless with the consent of the intrusctor before the due time, or evidence of emergency is presented after the due time.
  • You may discuss about homework with your classmates in teams of at most 3 students, but you must write down your own solution and acknowledge your collaborators.
  • The midterm and final exams must be completed independently. The only material allowed during the exam are 2 pages of hand-written notes.

Class Content

Tentative Syllabus.

1 2018-01-15
  • Holiday
1 2018-01-17
  • Welcome to class
  • Administration details
  • Introduction
  • Greedy Algorithm
2 2018-01-22
  • Greedy Algorithm
2 2018-01-24
  • Greedy Algorithm
  • HW1 out, Wed
3 2018-01-29
  • Greedy Algorithm
3 2018-01-31
  • Divide and Conquer
  • HW1 due on 5:00pm Friday
4 2018-02-05
  • Divide and Conquer
  • HW2 out, Mon
4 2018-02-07
  • Divide and Conquer
5 2018-02-12
  • Dynamic Programing
5 2018-02-14
  • Dynamic Programing
  • HW2 due at 5:00pm on Wednesday
  • PA out on Friday
6 2018-02-19
  • Holiday
6 2018-02-21
  • Midterm, in class
  • Dynamic Programming
  • HW3 out, Mon
7 2018-02-28
  • Dynamic Programming
8 2018-03-05
  • NP Completeness
8 2018-03-07
  • NP Completeness
  • HW3 due on 5:00pm Wednesday
  • HW4 out Wednesday
9 2018-03-12
  • NP Completeness
9 2018-03-14
  • Approximation Algorithm
  • PA due on 11:59pm Wednesday
  • HW4 due on 5:00pm Friday
10 2018-02-22 Final 12:00pm -- 3:00pm