INFO 206B

Introduction to Data Structures and Analytics
INFO 206B
UC Berkeley
Fall 2023

Course
Time/Location: MW 2:00-4:00, Physics Building 2

Instructor: Hany Farid
Office Hours: MW 4:00-5:00, or by appointment (South Hall 203A)

Course Staff: Prashant Sharma and Drake White
Office Hours: M 3:40-5:30; T 10:30-12:30; W 10:00-2:00 & 3:40-6:30; R 12:00-3:20; F 10:00-12:00 (South Hall 110)

Description
The ability to represent, manipulate, and analyze structured data sets is foundational to the modern practice of data science. This course introduces students to the fundamentals of data structures and data analysis (in Python). Best practices for writing code are emphasized throughout the course. This course forms the second half of a sequence that begins with INFO 206A. It may also be taken as a stand-alone course by any student that has sufficient Python experience.

Structure
This course will be flipped: pre-recorded lectures will be delivered asychronously and we will use class time to answer questions, work through lecture problems and complete in-class exercises (which will be graded). You should watch each day's videos before class, and then come to class prepared to ask questions about the course material.

Prerequisite
INFO 206A or equivalent, or permission of instructor

Software
All course assignments will be done in Python using Jupyter Notebooks. Please install Python 3 and Jupyter Notebook on your computer. I found it easiest to use pip instead of conda to perform the installation. Please also install the following Python libraries: drawSvg (version 1), matplotlib, and numpy. Please install version 1.9 of drawSvg: pip install "drawSvg~=1.9".

Ed
Ed is an excellent forum for asking questions. I strongly encourage you to ask and answer questions here. Please be sensitive of the academic integrity policy and do not post your code or solutions. I and the course staff will regularly monitor piazza and answer unanswered questions in a timely manner.

Academic Integrity
All work that you submit must be your own. You may not download, copy, or reproduce, in any way, code or solutions that you find on-line or from a fellow or former student. Submitting any work that is not entirely your own is a violation of Academic Integrity. You will generate and submit sample output of your code. Altering this output in any way to be inconsistent with your code is a violation of Academic Integrity. During exams, you may not access any written or on-line information not explicitly specified in the exam instructions, and you may not discuss the contents of the exam with anyone else.

You may not use chatGPT or similar tools for writing or helping to write code.

You may not publish or post any of your assignments, exams, or course solutions onto any publicly accessible websites. Such postings only fuel violations of the academic integrity policy in future semesters.

Violations of Academic Integrity will be taken very seriously. Independent of any Univeristy consequences that may result from a violation of this code, violations may lead to a failing grade in the class.

Schedule (subject to minor change)

[10/16] Welcome
[10/18] Data analysis: searching
- linear and binary search [video]
- run-time analysis [video]
- big-O notation [video]
[10/23] Data analysis: sorting
- selection sort [video]
- selection sort, run-time analysis [video]
- insertion sort [video]
- insertion sort, run-time analysis [video]
- merge sort [video]
- merge sort, run-time analysis [video]
- quick sort [video]
[10/25] Data structures: lists
- list operations, run-time analysis [video]
- singly linked lists [video]
- drill [video] [code]
[10/30] Data structures: doubly linked lists (DLL)
- DLL [video]
- DLL insert [video]
- DLL delete [video]
- DLL find [video]
- DLL, run-time analysis [video]
[11/01] Data structures: dictionaries (hash tables)
- dictionaries [video]
- hashing [video]
- dictionaries, run-time analysis [video]
- drill [video] [code] [DOI.txt]
[11/06] Data structures: graphs
- graphs [video]
- representing graphs [video]
- breadth-first search (BFS) [video]
- queues and stacks [video]
- BFS implemented [video]
- binary search trees [video]
[11/08] Data visualization
- file I/O [video] [code] [states.txt] [us-500.csv]
- matplotlib [video] [code]
- numpy [video] [code]
- drill [video] [code] [temperatures.csv]
- images [video] [code] [mandrill.jpg]
[11/13] Data fitting: linear systems
- linear equations [video]
- linear equations (geometric picture) [video]
- vectors [video]
- linear equations (vector picture) [video]
- matrices [video]
[11/15] Data fitting: linear systems
- linear equations (matrix picture) [video]
- linear equations (degenerate solutions) [video]
- summary [video]
- ballistic motion forensics [video]
- lighting forensics [video (1/2)] [video (2/2)]
[11/20] Data fitting: least-squares
- y=ax+b (n constraints, n unknowns) [video]
- y=ax+b (n constraints, m unknowns, n > m) [video]
- y=ax (n constraints, m unknowns, n > m) [video]
- drill [video]
[11/22] Holiday
[11/27] Data fitting: least-squares
- y=ax+b (n constraints, m unknowns, n > m) [video]
- drill [video]
- y=ax+b (n constraints, m unknowns, n > m) [video]
- y=ax+b (solve for b) [video]
- y=ax+b (solve for a) [video]
- drill [video]
[11/29] Data fitting: least-squares
- y=ax+b (matrix picture, part 1) [video]
- y=ax+b (matrix picture, part 2) [video]
- drill [video] [code]
- regression [video]
- weighted least-squares (part 1) [video]
- weighted least-squares (part 2) [video]
- drill [video] [code]
[12/04] Wrap Up

Assignments (subject to minor change)
In order to increase flexibility, I will release all assignments at the beginning of the semester. I would ask, however, that you use office hours to ask only about current assignments. Assignments are due at 2:00 pm on the due date. Assignments submitted between 2:00:01 pm on the due date and 2:00 pm on the following day will be subjected to a 25% penalty; assigments submitted after this will not be accepted. Please submit all assignment to bCourses.

Assignment 1 (out: 10/23; due 10/26)
Assignment 2 (out: 10/26; due 10/30)
Assignment 3 (out: 10/30; due 11/02)
Assignment 4 (out: 11/01; due 11/08)
Assignment 5 (out: 11/08; due 11/15)
Assignment 6 (out: 11/15; due 11/21)
Assignment 7 (out: 11/27; due 11/30)
Assignment 8 (out: 11/30; due 12/04)

Grading
Your final grade will be determined from 8 assignments (65%) and 12 in-class exercises (35%). You must submit all 8 assignments. You must complete at least 9 in-class quizzes (to accomodate absences, we will drop your 3 lowest quiz scores from your final grade; these 3 lowest scores, however, will be factored in as bonus points against any lost points on your assignments). You must be in class when completing these quizzes.

Resources

Project Python [link]
Think Python [link]
Python Tutor [link]
Gilbert Strang lectures on Linear Algebra [link]