Wiki and code repository for my CS0, CS1, and CS2 classes
This repo contains my course notes and source code for the CS0, CS1, and CS2 classes I teach at Normandale Community College, in Bloomington, MN. This is, and will probably forever remain, a work in progress.
Writing software is all about problem solving, at two different levels. The first is the real-world problem to be solved, for example:
- How can I keep track of the data for a youth baseball league?
- How can I find the outlines of objects in a photograph?
- How can I take this data representing a 3D object and create a triangular mesh for a 3D printer?
The second level is the problem of how to take that real-world problem solution and implement it in a way that allows a computer to efficiently execute it.
The CSn courses are all about that second level of problem solving.
Here is the breakdown of topics, by course. Note that this is not a hard-and-fast breakdown; there are some semesters in which I may choose to incorporate some CS1 topics into CS0 or CS2, or introduce some CS2 topics into CS1.
- Variables and Types
-
- Assignment statements
-
- Arithmetic expressions
- Selection
-
- Logical expressions
- Loops
- Arrays
- Functions
- Aggragation
- Recursion
- Some basic algorithms
- Half-open ranges
- Algorithm correctness
- Simple sorts
- Abstract Data Types and APIs
-
- Encapsulation
-
- Data hiding
-
- Class invariants
- Linked lists
-
- Basic structure
-
- Insertion and removal
-
- Performance issues
- Inheritance
-
- Implementation inheritance
-
- Interface inheritance
- Predicates
-
- Linked lists revisited
-
-
- Find min/max element
-
-
-
- Remove min/max element
-
- Some elementary ADTs
-
- Arrays vs. linked lists
-
- Stack
-
- Queue
-
- Priority queues
-
- Symbol tables
- Algorithm complexity
- Sorting
-
- Quicksort
-
-
- Partition
-
-
-
- Nth Element
-
-
-
- 3-way quicksort
-
-
- Other sorting-related algorithms
-
-
- Partial Sort
-
-
-
- Sort Subrange
-
-
-
- Partition Subrange
-
-
- Heaps
-
- Priority queues
-
- Heapsort
-
- Non-comparison sorting
-
-
- Radix sort
-
-
-
- Key-indexed counting
-
-
-
- LSD and MSD string sorts
-
- Searching
-
- Set API
-
- Symbol table API
-
- Applications
-
- Implementation
-
-
- Search trees
-
-
-
-
- Unbalanced binary trees
-
-
-
-
-
- Balanced binary trees
-
-
-
-
-
-
- 2-3 trees
-
-
-
-
-
-
-
- Red-black trees
-
-
-
-
-
-
-
- AVL trees
-
-
-
-
-
-
- KD-trees
-
-
-
-
- Hash tables
-
-
-
-
- Hash functions
-
-
-
-
-
-
- Division method
-
-
-
-
-
-
-
- Multiplilcation method
-
-
-
-
-
-
- Collision resolution
-
-
-
-
-
-
- Separate chaining
-
-
-
-
-
-
-
- Linear probing
-
-
-
-
-
-
-
- Double hashing
-
-
-
-
-
-
-
- Cuckoo hashing
-
-
-
- Graphs
-
- Separation of data structures from algorithms
-
- Union-find
-
- Undirected graphs
-
-
- Finding Paths
-
-
-
-
- API
-
-
-
-
-
- Applications
-
-
-
-
-
- Depth-first search
-
-
-
-
-
- Breadth-first search
-
-
-
-
- Connected Components
-
-
- Directed graphs
-
-
- Finding Paths
-
-
-
-
- API
-
-
-
-
-
- DFS and BFS
-
-
-
-
- Cycle detection
-
-
-
- Topological sort
-
-
-
- Strong connectivity
-
-
- Edge-weighted undirected graphs
-
-
- Minimum spanning trees
-
-
-
-
- APIs (edge and graph)
-
-
-
-
-
- Prim's algorithm
-
-
-
-
-
- Kruskal's algorithm
-
-
-
- Edge-weighted directed graphs
-
-
- Shortest path
-
-
-
-
- Dijkstra's algorithm
-
-
-
-
-
- DAG shortest path
-
-
-
-
- Job scheduling
-
-
-
- Bellman-Ford
-
-
- Non-integral vertex IDs
-
- Dynamic graphs
- Language rants
- How not to code like a n00b
- That's not a bug...
- Don't write your own date/time classes
- Practice
- Create a portfolio