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:0011:50am, GIRV 1116
 Session 2: Friday 12:0012:50pm, Phelp 1445
Office hours:
 Anh Van Dong Nguyen: Tuesday 46pm, GSL
 Jonathan Sun: Thursday 24pm, TA trailer
 Rachel Lin: Monday 45pm, HFH 1153
Piazza: We will be using Piazza for classrelated 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 pseudocode 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 firstbatch test cases have been uploaded to the submission site. The secondbatch 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. NPcompleteness.
Prerequisite: CS130a
Textbook
The class roughly follows the following textbook: Mark Allen Weiss. Data Structures and Algorithms Analysis (in C++, or any other edition)
 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 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
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 handwritten notes. If additional material is allowed, the instructor will communicate before the exams.
Class Content
I will update the class content after each class.
Week  Date  Content  Material  Assignment 

1  20150330 



2015041 


2  20150406 


20150408 


3  20150413 


20150415 

HW1 due.  
20150417 




4  20150420 


20150422 



5  20150427 


20150429 

HW2 due  
6  20150504 


20150506 



20150508 


PA1 due on Friday  
7  20150511 



20150513 


8  20150518 

HW3 due  
20150520 



9  20150525 



20150527 



10  20150601 

HW4 due  
20150603 



20150605 


PA2 due at 12:00pm Friday  
11  20150612 
