CSCI046: Data Structures and Algorithms

About the Instructor

Name	Mike Izbicki (you can call me Mike)
Email	mizbicki@cmc.edu
Office	Adams 216
Office Hours	Monday 9:00-10:00AM, Tuesday/Thursday 2:30-3:30PM, or by appointment (see my schedule); if my door is open, feel free to come in
Webpage	izbicki.me
Research	Machine Learning (see izbicki.me/research.html for some past projects)
Fun Facts	grew up in San Clemente, 7 years in the navy, phd/postdoc at UC Riverside, taught in DPRK

About the Course

This is a second semester course in computer science designed for students who have previously taken either CS40 at CMC or CS5 at Mudd.

This course is required for the computer science sequence, and optional for the data science sequence. It will be required for the data science major (if/when it gets approved).

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
3. There is no lab section

Textbook:

1. Problem Solving with Algorithms and Data Structures using Python by Brad Miller and David Ranum
2. Algorithms by Dasgupta, Papadimitriou, and Vazirani

Optional Readings:

Advice on how to be a good programmer:

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)

How to make money/get a good job:

1. Yes, the median salary at facebook is $240k
2. A detailed analysis of FAANG salaries, with raw data from levels.fyi
3. The high-tech employee antitrust litigation
4. Get jobs from GitHub/HackerNews
5. /r/cscareerquestions

Other technical articles:

1. Command-line tools can be faster than a hadoop cluster
2. intermediate vim
3. Mike's dotfiles
4. The missing semester of CS education
5. Larry Wall's three virtures of a programmer
6. accidentally quadratic blog and a windows bug caused by an O(n^2) algorithm
7. the history of git
8. timsort -- Tim's Zen of Python
9. stackoverflow - why processing sorted arrays is faster even in linear search

Library documentation:

1. timeit
2. collections
3. copy
4. traceback

Cheat sheets:

1. bash
2. vim
3. git

Programming games:

1. https://vim-adventures.com/
2. The git game and git game v2
3. typespeed (type this command on the lambda server)

Schedule

Lecture

Week	Date	Topic	Reading
1	Tues, 21 Jan	Intro to shell / vim / git / travis
1	Thur, 23 Jan	Intro to shell / vim / git / travis
2	Tues, 28 Jan	Intro to shell / vim / git / travis
2	Thur, 30 Jan	Python features	MR 1-2
3	Tues, 04 Feb	Analysis I	MR 3, DPV 0.3
3	Thur, 06 Feb	Analysis II	PythonWiki
4	Tues, 11 Feb	Basic data structures: stack	MR 4.1-4.9
4	Thur, 13 Feb	Basic data structures: queue	MR 4.10-4.23
5	Tues, 18 Feb	Recursion I	MR 5.1-5.10
5	Thur, 20 Feb	Recursion II
6	Tues, 25 Feb	Sorting: binary search	MR 6.3-6.4
6	Thur, 27 Feb	Sorting: algorithms I	MR 6.6-6.12
7	Tues, 03 Mar	Sorting: algorithms II
7	Thur, 05 Mar	Sorting: hash functions	MR 6.5
8	Tues, 10 Mar	Recursion: divide and conquer
8	Thur, 12 Mar	Recursion: divide and conquer
9	Tues, 17 Mar	NO CLASS: Spring Break
9	Thur, 19 Mar	NO CLASS: Spring Break
10	Tues, 24 Mar	Trees I	MR 7.1-7.7
10	Thur, 26 Mar	Trees II
11	Tues, 31 Mar	Trees: BST	MR 7.11-7.14
11	Thur, 02 Apr	Trees: AVL	MR 7.15-7.17
12	Tues, 07 Apr	Trees: Heaps	MR 7.8-7.10
12	Thur, 09 Apr	Graphs: representations	MR 8.1-8.6
13	Tues, 14 Apr	Graphs: traversals	MR 8.7-8.18
13	Thur, 16 Apr	Graphs: Dijkstra	MR 8.20-8.21
14	Tues, 21 Apr	Graphs: Prim	MR 8.22
14	Thur, 23 Apr	Graphs: Kruskal
15	Tues, 28 Apr	Recursion: dynamic programming (matrix mul)	DPV 6.5
15	Thur, 30 Apr	Recursion: dynamic programming (knapsack)	DPV 6.4
16	Thur, 05 May	P vs NP	DPV 8.1, 8.2
16	Thur, 07 May	NO CLASS: Reading Day

Assignments

We will have approximately 1 assignment per week in this course according to the following schedule.

Assignment	Type	Points	Topic
1	project	10	Unix/Git tutorial
2	math	10	Analysis/Big-O
3	project	10	HTML validator
4	project	10	word ladders
5	math	10	memory management
6	project	10	binary search
7	project	10	twitter data analysis
8	test	20	midterm
9	project	10	BST
10	project	10	AVL tree
11	project	10	Heaps
12	math	10	Graphs
13	project	10	Dijkstra
14	project	10	Knapsack
15	test	20	Final

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.

Collaboration Policy:

For project/math assignments: you may use any resources you like and discuss with whomever you like. Learning the material in this course is your responsibility, and I don't want to put any artificial restrictions on any of the assignments that will get in your way.

Tests will be take home and open notes. The only restriction is you are not allowed to talk to other students in the class about the contents.

Technology Policy:

You must use either vim or emacs to complete all programming assignments.

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

Extra credit:

If you submit a pull request to this repo that gets accepted (e.g. you fix a typo), then you will get extra credit. The first time you do this, you will get 1 point of extra credit; subsequent times you will get less.

If you make a contribution to an open source project during the course, you will get extra credit depending on the magnitude of your contribution. See https://up-for-grabs.net for some projects that are looking for new contributors.

Notes

Accommodations for Disabilities

I want you to succeed and I'll make every effort to ensure that you can. If you need any accommodations, please ask.

If you have already established accommodations with Disability Services at CMC, please communicate your approved accommodations to me at your earliest convenience so we can discuss your needs in this course. You can start this conversation by forwarding me your accommodation letter. If you have not yet established accommodations through Disability Services, but have a temporary health condition or permanent disability (conditions include but are not limited to: mental health, attention-related, learning, vision, hearing, physical or health), you are encouraged to contact Assistant Dean for Disability Services & Academic Success, Kari Rood, at disabilityservices@cmc.edu to ask questions and/or begin the process. General information and the Request for Accommodations form can be found at the CMC DOS Disability Service’s website. Please note that arrangements must be made with advance notice in order to access the reasonable accommodations. You are able to request accommodations from CMC Disability Services at any point in the semester. Be mindful that this process may take some time to complete and accommodations are not retroactive. It is important to Claremont McKenna College to create inclusive and accessible learning environments consistent with federal and state law. If you are not a CMC student, please connect with the Disability Services Coordinator on your campus regarding a similar process.