CS 130b: Data Structures and Algorithms (Spring 2015)

General Information

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

TAs:

  • Anh Van Dong Nguyen, email: donganh (at) cs (dot) ucsb (dot) edu
  • Jonathan Sun, email: jsun (at) cs (dot) ucsb (dot) edu

Time and location:

  • Class: Mon/Wed 8:00 am - 9:15 am, Phelp 3526
  • Session 1: Friday 11:00-11:50am, GIRV 1116
  • Session 2: Friday 12:00-12:50pm, Phelp 1445

Office hours:

  • Anh Van Dong Nguyen: Tuesday 4-6pm, GSL
  • Jonathan Sun: Thursday 2-4pm, TA trailer
  • Rachel Lin: Monday 4-5pm, HFH 1153

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

Announcements

  • May. 20th. Homework 4 is posted. See link below. It is due at 12:00pm (noon) June 1st. You can either hand in the homework at the beginning of the class, or to the homework box for CS 130b at the CS mailroom.
  • May. 11th. Programming Assignement 2 is posted. See link below. It is due at 12:00pm June 5th. The pseudo-code should be submitted to the homework box in the CS mailroom. The implementation should be submitted to the submit@cs system.
  • May. 6th. Homework 3 is posted. See link below. It is due at 12:00pm May 18th. You can either hand in the homework at the beginning of the class, or to the homework box for CS 130b at the CS mailroom.
  • Apr. 27th. This week, you can pick up your homework from the office hours.
  • Apr. 27th. The first-batch test cases have been uploaded to the submission site. The second-batch test cases will be uploaded this week.
  • Apr. 20th. Homework 2 is posted. See link below. It is due at 12:00pm Apr. 29th. You can either hand in the homework at the beginning of the class, or to the homework box for CS 130b at the CS mailroom.
  • Apr. 17th. Programing assignment 1 is posted. To help you get familiar with the submit@cs system, we created a dummy project (it is only there to help you and is not graded.
  • Apr. 15th. Every student handing in homework 1 by the deadline (noon Apr 15th) will be in the class. If you are one of them and have not left your name to me. Please send an email to me and the TAs.
  • Apr. 13th. The posting of programming assignment 1 is delayed to Apr. 17th.
  • Apr. 6th. Some small adjustment to the schedule of assignments and midterm has been made.
  • Apr. 6th. Homework 1 is out. It is due at 12:00pm Wednesday Apr. 15th. You can either hand in the homework at the beginning of the class, or to the homework box for CS 130b at the CS mailroom. Please note that the new rule on "skipping problems" in the class policy section.
  • Apr. 1st Homework 1 will be out on Monday, you will have a week and half to complete it. This is an announcement to make sure that you know it's coming. More details later.

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

Textbook

The class roughly follows the following textbook:
  • Mark Allen Weiss. Data Structures and Algorithms Analysis (in C++, or any other edition)
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)

Grading:

There will be four homework assignments, couting 40%, two programming assignments, counting 20%, and one midterm exams, counting 15%, and one final, couting 25%. 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. The weighted sum is then adjusted according to the following rule on skipping problems. Finally, the letter grade of each student is determinied according to the distribution the weighted sums of the entire class.
  • Skipping problem in the homework and programming assignments has a non-linear effect the final weighted sum.
    • Skipping one problem leads to minus 1/2^16 in the weighted sum.
    • Skipping two problems leads to minus 1/2^8 in the weighted sum
    • Skipping three problems leads to minus 1/2^4 in the weighted sum
    • Skipping four problems leads to minus 1/4 in the weighted sum
    • So on and so forth
    Note: As long as you attempt to solve every problem, and write down your earnest attempts, it does not count as skipping problem, even if your solution is incorrect.
  • Class Policy:

    • For homework and programming assignements, no late submissions are accepted, unless with the consent of the intrusctor before the due time. You might be asked for documents as evidence to justify the need of late days. No exception will be made.
    • You may discuss about homework with your classmates, 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. If additional material is allowed, the instructor will communicate before the exams.

    Class Content

    I will update the class content after each class.

    WeekDateContentMaterialAssignment
    1 2015-03-30
    • Welcome to class
    • Administration details
    • Introduction
    • Review of asymptotic
    2015-04-1
    • Introduction to Greedy Algorithm
    • MakeChangeGreedy Algorithm
    • Analysis of MakeChangeGreedy Algorithm
    • Intro to Activity Selection
    2 2015-04-06
    • Greedy Algorithm for Activity Selection
    • Greedy always stays ahead
    2015-04-08
    • Greedy Algorithm for Activity Selection
    • Exchange Argument
    3 2015-04-13
    • Huffman Code
    2015-04-15
    • Huffman Code Cont'd
    HW1 due.
    2015-04-17
  • PA1
  • Dummy Project
  • 4 2015-04-20
    • Divide and Conquer
    • Solving Recurrence Relation
    2015-04-22
    • Divide and Conquer cont'd
    • Integer Multiplication
    • Closest Points
    5 2015-04-27
    • Divide and Conquer cont'd
    • Selection Problem
    2015-04-29
    • Divide and Conquer, Selection Problem
    • Dynamic Programming
    HW2 due
    6 2015-05-04
    • midterm
    2015-05-06
    • Dynamic Programming
    • Matrix Order
  • HW3
  • 2015-05-08
    PA1 due on Friday
    7 2015-05-11
    • Dynamic Programming
    • Longest Common Subsequence
  • PA2
  • 2015-05-13
    • Dynamic Programming
    • Longest Common Subsequence, second stab
    8 2015-05-18
    • All-Pair Shortest Paths
    • NP-Completeness
    HW3 due
    2015-05-20
    • NP-Completeness
    • Circuit Satisfiability
  • HW4
  • 9 2015-05-25
    • Holiday
    2015-05-27
    • NP Completeness
    • 3-SAT is NPC
    10 2015-06-01
    • NP Completeness
    • Approximation Algorithm
    HW4 due
    2015-06-03
    2015-06-05
    PA2 due at 12:00pm Friday
    11 2015-06-12
    • Final 8:00-10:30am