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)
- 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 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.
Week | Date | Content | Material | Assignment |
---|---|---|---|---|
1 | 2015-03-30 |
|
|
|
2015-04-1 |
|
|||
2 | 2015-04-06 |
|
||
2015-04-08 |
|
|||
3 | 2015-04-13 |
|
||
2015-04-15 |
|
HW1 due. | ||
2015-04-17 |
|
|
|
|
4 | 2015-04-20 |
|
||
2015-04-22 |
|
|
||
5 | 2015-04-27 |
|
||
2015-04-29 |
|
HW2 due | ||
6 | 2015-05-04 |
|
||
2015-05-06 |
|
|
||
2015-05-08 |
|
|
PA1 due on Friday | |
7 | 2015-05-11 |
|
|
|
2015-05-13 |
|
|||
8 | 2015-05-18 |
|
HW3 due | |
2015-05-20 |
|
|
||
9 | 2015-05-25 |
|
|
|
2015-05-27 |
|
|
||
10 | 2015-06-01 |
|
HW4 due | |
2015-06-03 |
|
|
||
2015-06-05 |
|
|
PA2 due at 12:00pm Friday | |
11 | 2015-06-12 |
|