CS 130A Data Structures and Algorithms 1

CS 130A Data Structures and Algorithms 1

Department of Computer Science
University of California Santa Barbara
http://koclab.cs.ucsb.edu/teaching/cs130a

Announcements

  • Instructor: Professor Koç         → Koç is pronounced as "Coach"  

  • Class Schedule: Tuesdays, Thursdays 12:30-1:45pm
  • Classroom: LSB (Life Sciences Building) 1001

  • Instructor's Office hours: Tuesday 2:30-4:00pm
  • Instructor's Office: Phelps 1408 (Koç Lab - map)

  • The TAs are
    Krishna Gudipati - krishnachaitanya@ucsb.edu
    Peter Gartland - petergartland@ucsb.edu
    Zhening (Sirius) Zhang - zhening@ucsb.edu

    The Reader: Jinglei Yang - jingleiyang@ucsb.edu

  • TA Office Hours and Offices are
    Wednesday 11:00am-1:00pm Peter (Trailer 936)
    Thursday 2:00-4:00pm Sirius (Harold Frank Hall 5110)
    Friday 2:00-4:00pm Krishna (Trailer 936)

  • Discussion Schedule and Room:
    Thursday 4:00-4:50pm; Phelps 2510 (Krishna)
    Thursday 5:00-5:50pm; Phelps 2510 (Sirius)
    Thursday 6:00-6:50pm; Phelps 2510 (Peter)

  • Please join the cs130a Piazza page for class discussions.   ←
  • Check the class website, the Piazza page, and/or your email once a day.
  • Course material is in the folder docx   ←
  • The grades:   cs130a.htm   Code = 2047*StudentPerm mod 9973   ←

Homework Assignments

There will be 4 or 5 homework assignments during the term, and they are to be uploaded via Gradescope.
No late homework is accepted.   ←
  • Homework Assignment 1: hw1.pdf - due 5pm Wed Jan 22
  • Homework Assignment 2: hw2.pdf - due 11pm Fri Feb 7
  • Homework Assignment 3: hw3.pdf - due 11pm Fri Feb 21
  • Homework Assignment 4: hw4.pdf - due 11pm Fri Mar 6
  • Homework Assignment 5: hw5.pdf - due 11pm Sat Mar 14

Programming Assignments

There will be 4 programming assignments during the term, and they are to be uploaded via Gradescope. Carefully read the assignment specs for instructions.

Midterm Exam

The Midterm exam will be during the 8th week of classes, Tuesday Feb 25   ←

No final exam   ←

Weekly Course Plan

  • Week 1: Introduction, Analysis, Max Subsequence Algorithms
  • Week 2: Big-Oh Notation, Asymptotics,
  • Week 3: ADT, Lists, Queues, Introduction to hashing
  • Week 4: Hash functions, Analysis of Hashing
  • Week 5: Universal Hashing, Perfect Hashing
  • Week 6: Heaps, d-Heaps, Leftist Heaps, Heapsort, Binomial Queues
  • Week 7: Binary Search Trees, Balanced Search Trees (AVL)
  • Week 8: Splay Trees, B-Trees, Midterm
  • Week 9: Bloom Filters, Union Find Data Structure
  • Week 10: Graph Algorithms

Other Course Material

  • AVL Tree Visualization:   url
  • Binary Heap Visualization:   url
  • Heapsort Audibilization:   url
  • 15 Sorting Algorithms in 6 Minutes:   url
  • Sorting Algorithms:   url

  • Inside a Google Onsite Interview:   url
  • How NOT to Hire an Engineer:   url
  • Why the New Guy Can't Code:   url

Textbook

Grading Rules

  • Homework Assignments: 30 %
  • Programming Assignments: 30 %
  • Midterm Exam: 40 %

Course (Catalog) Description

The study of data structures and their applications. Correctness proofs and techniques for the design of correct programs. Internal and external searching. Hashing and height balanced trees. Analysis of sorting algorithms. Memory management. Graph traversal techniques and their applications.

Prerequisites

CS 40; CS 32 or CS 20 and CS 60; PSTAT 120A or ECE 139; open to computer science, computer engineering, and electrical engineering majors only. Students in other majors need to petition.
Academic Integrity   ←

Çetin Kaya Koç