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

Textbook

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)

Grading:

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.