CSCI046: Data Structures and Algorithms

About the Instructor

Name	Mike Izbicki (call me Mike)
Email	[email protected]
Office	Adams 216
Office Hours	MW 2pm-3pm, or by appointment
Webpage	izbicki.me
Research	Machine Learning (see izbicki.me/research.html for some past projects)

Fun facts:

1. grew up in San Clemente
2. 7 years in the navy
3. phd/postdoc at UC Riverside
4. taught in DPRK
5. My wife is pregnant and due to have a baby early April. This may result in a class session being rescheduled, depending on when the baby decides to come.

About the Course

Data structures is the most important course in computer science, and many of the "classic" CS interview questions come from this course. Mastering this material is the first step towards getting a high paying CS job. See:

1. https://www.levels.fyi
2. tech employers illegally collude to reduce salaries

Who should take this course?

1. This is a second semester course in computer science designed for students who have previously taken either CS40 (CMC), CS5 (Mudd), or CS51 (Pomona).

2. You cannot take this course if you've already taken a data structures course (e.g. Pomona: CS62; HMC: CS60, CS70).

3. This course is required for CMC's data science major and the computer science sequence. It is optional for the data science sequence. You cannot take this course if you are a computer science major.

Learning Objectives:

Primary objectives:

1. Learn basic devops and how open source software is developed
2. Be able to answer the following three questions about an algorithm:
   1. Is it correct?
   2. How much resources does it consume? (time, memory, money, etc.)
   3. Can we do better?

Secondary objectives:

1. Learn basic shell programming
2. More experience with python programming
3. Solve the questions asked in programming interviews and contests
4. Introduction to the mathematics of programming (overlap with discrete math)
5. Introduction to the hacker culture

Differences between this course and HMC's CSCI060HM/CSCI070HM:

1. This course does not cover low-level memory management (C/C++ programming languages)
2. This course is more practical

This course is NOT an algorithms course. Algorithms courses form the "other half" of classic CS interview questions, and you should consider taking CS148 - Graph Algorithms after this course.

Textbook:

All of our textbooks are both free as in beer and free as in speech:

1. Problem Solving with Algorithms and Data Structures using Python by Brad Miller and David Ranum

2. Official Python Documentation

Grades:

You will have:

1. Weekly labs (worth 2pts each)
2. Weekly homeworks (worth 10-25 points each)
3. No midterms, 1 open book final (worth approx. 30 points)
4. In total, there will be about 250 points in the class.

Historically, the average student needs to spend about 10 hours per week (including class time) to get an A. About 25% of students will either: spend 15-20 hours per week and get an A, or spend 10 hours per week and get a B/C.

Your final grade will be computed according to the following table, with one caveat.

If your grade satisfies	then you earn
95 ≤ grade	A
90 ≤ grade < 95	A-
87 ≤ grade < 90	B+
83 ≤ grade < 87	B
80 ≤ grade < 83	B-
77 ≤ grade < 80	C+
73 ≤ grade < 77	C
70 ≤ grade < 73	C-
67 ≤ grade < 70	D+
63 ≤ grade < 67	D
60 ≤ grade < 63	D-
60 > grade	F

CAVEAT: In order to get an A/A- in this course, you must also complete one of the following two tasks to learn about the history of unix programming:

1. watch the following two documentaries about open source:

   1. RevolutionOS (from 2001)

   2. The Internet's Own Boy: The Story of Aaron Swartz (from 2014)

2. read chapters 1-3 of The Art of Unix Programming by ESR

I also strongly recommend that you read through the following advice from famous programmers, but it's not required:

1. Peter Norvig (AI researcher and senior engineer at Google)
2. Paul Graham (Founder of YCombinator startup incubator); being a noob
3. Jeff Atwood (Founder of stackoverflow.com)
4. Eric Steven Raymond, better known as ESR (a famous hacker)

Late Work Policy:

You lose 10% on the assignment for each day late. If you have extenuating circumstances, contact me in advance of the due date and I may extend the due date for you.

It is usually better to submit a correct assignment late than an incorrect one on time.

Schedule

Lecture

Week	Date	Topic
0	M, 25 Jan	Unix + open source workflow
0	W, 27 Jan	Unix + open source workflow
1	M, 01 Feb	Intermediate Python Features
1	W, 03 Feb	Intermediate Python Features
2	M, 08 Feb	Stacks + Algorithm Analysis
2	W, 10 Feb	Stacks + Algorithm Analysis
3	M, 15 Feb	Queues + Algorithm Analysis
3	W, 17 Feb	Queues + Algorithm Analysis
4	M, 22 Feb	Recursion
4	W, 24 Feb	Recursion
5	M, 01 Mar	Sorting
5	W, 03 Mar	Sorting
6	M, 08 Mar	Spring Break
6	W, 10 Mar	Spring Break
7	M, 15 Mar	Parallel Algorithms
7	W, 17 Mar	Parallel Algorithms
8	M, 22 Mar	Trees
8	W, 24 Mar	Trees
9	M, 29 Mar	BST Trees
9	W, 31 Mar	BST Trees
10	M, 05 Apr	AVL Trees
10	W, 07 Apr	AVL Trees
11	M, 12 Apr	Heap Trees
11	W, 14 Apr	Heap Trees
12	M, 19 Apr	Generators
12	W, 21 Apr	Generators
13	M, 26 Apr	Graphs
13	W, 28 Apr	Graphs
14	M, 03 May	Graphs
14	W, 05 May	Graphs

Technology Policy

1. You must complete all programming assignments on the lambda server.

2. You must use either vim or emacs to complete all programming assignments. In particular, you may not use the GitHub text editor, VSCode, IDLE, or PyCharm for any reason.

3. You must not share your lambda-server password with anyone else.

Violations of any of these policies will be treated as academic integrity violations.

Collaboration Policy

You are encouraged to discuss all labs and homeworks with other students, subject to the following constraints:

1. you must be the person typing in all code for your assignments, and
2. you must not copy another student's code.

You may use any online resources you like as references.

WARNING: All material in this class is cumulative. If you work "too closely" with another student on an assignment, you won't understand how to complete subsequent assignments, and you will quickly fall behind. You should view collaboration as a way to improve your understanding, not as a way to do less work.

You are ultimately responsible for ensuring you learn the material!

Accommodations for Disabilities

I've tried to design the course to be as accessible as possible for people with disabilities. (We'll talk a bit about how to design accessible software in class too!) If you need any further accommodations, please ask.

I want you to succeed and I'll make every effort to ensure that you can.