Notes on Data Structures and Programming Techniques

Course administration
Overview
License
Resources
Documentation
Questions and comments
Lecture schedule
Syllabus
On-line course information
Meeting times
Synopsis of the course
Prerequisites
Textbook
Course requirements
Staff
Instructor
Course manager
Teaching Fellow
Undergraduate Learning Assistants
Use of outside help
Clarifications for homework assignments
Late assignments
Introduction
Why should you learn to program in C?
Why should you learn about data structures and programming techniques?
The Zoo
Getting an account
Getting into the room
Remote use
Terminal access
GUI access
Developing on your own machine
Linux
OSX
Windows
How to compile and run programs
Creating the program
Compiling and running a program
Some notes on what the program does
The Linux programming environment
The shell
Getting a shell prompt in the Zoo
The Unix filesystem
Unix command-line programs
Stopping and interrupting programs
Running your own programs
Redirecting input and output
Text editors
Writing C programs with Emacs
My favorite Emacs commands
Using Vi instead of Emacs
My favorite Vim commands
Normal mode
Insert mode
Settings
Compilation tools
The GNU C compiler gcc
Make
Make gotchas
Debugging tools
Debugging in general
Assertions
The GNU debugger gdb
My favorite gdb commands
Debugging strategies
Common applications of gdb
Watching your program run
Dealing with failed assertions
Dealing with segmentation faults
Dealing with infinite loops
Mysterious variable changes
Valgrind
Compilation flags
Automated testing
Examples of some common valgrind errors
Uninitialized values
Bytes definitely lost
Invalid write or read operations
Not recommended: debugging output
Performance tuning
Timing under Linux
Profiling with valgrind
Profiling with gprof
Effect of optimization during compilation
Version control
Setting up Git
Editing files
Renaming files
Adding and removing files
Recovering files from the repository
Undoing bad commits
Looking at old versions
More information about Git
Submitting assignments
The C programming language
Structure of a C program
Numeric data types
Integer types in C
Basic integer types
Overflow and the C standards
C99 fixed-width types
size_t and ptrdiff_t
Integer constants
Naming constants
Integer operators
Arithmetic operators
Bitwise operators
Logical operators
Relational operators
Converting to and from strings
Floating-point types
Floating point basics
Floating-point constants
Operators
Conversion to and from integer types
The IEEE-754 floating-point standard
Round-off error
Reading and writing floating-point numbers
Non-finite numbers in C
The math library
Operator precedence
Programming style
Variables
Memory
Variables as names
Variable declarations
Variable names
Using variables
Initialization
Storage class qualifiers
Scope and extent
Additional qualifiers for global variables
Marking variables as constant
Pointers to const
Input and output
Character streams
Reading and writing single characters
Formatted I/O
Rolling your own I/O routines
File I/O
Statements and control structures
Simple statements
Compound statements
Conditionals
Loops
The while loop
The do..while loop
The for loop
Loops with break, continue, and goto
Choosing where to put a loop exit
Functions
Function definitions
When to write a function
Calling a function
The return statement
Function declarations and modules
Static functions
Local variables
Mechanics of function calls
Pointers
Memory and addresses
Pointer variables
Declaring a pointer variable
Assigning to pointer variables
Using a pointer
Printing pointers
The null pointer
Pointers and functions
Pointer arithmetic and arrays
Arrays
Arrays and functions
Multidimensional arrays
Using built-in C arrays
Using an array of pointers to rows
Using a one-dimensional array
Variable-length arrays
Why you shouldn't use variable-length arrays
Pointers to void
Alignment
Run-time storage allocation using malloc
Function pointers
Function pointer declarations
Callbacks
Dispatch tables
The restrict keyword
Strings
C strings
String constants
String encodings
String buffers
String buffers and the perils of gets
Operations on strings
Finding the length of a string
The strlen tarpit
Comparing strings
Formatted output to strings
Dynamic allocation of strings
Command-line arguments
Structured data types
Structs
Operations on structs
Layout in memory
Bit fields
Unions
Enums
Specifying particular values
What most people do
Using enum with union
Type aliases using typedef
Opaque structs
Macros
Macros with arguments
Multiple arguments
Perils of repeating arguments
Variable-length argument lists
Macros vs. inline functions
Macros that include other macros
More specialized macros
Multiple expressions in a macro
Non-syntactic macros
Multiple statements in one macro
String expansion
Big macros
Conditional compilation
Defining macros on the command line
The #if directive
Debugging macro expansions
Can a macro call a preprocessor command?
Data structures and programming techniques
Asymptotic notation
Two sorting algorithms
Big-O to the rescue
Asymptotic cost of programs
Other variants of asymptotic notation
Linked lists
Stacks
Building a stack out of an array
Queues
Looping over a linked list
Looping over a linked list backwards
Deques and doubly-linked lists
Alternate implementation using a ring buffer
Circular linked lists
What linked lists are and are not good for
Further reading
Abstract data types
A sequence type
Interface
Implementation
Compiling and linking
Designing abstract data types
Parnas's Principle
When to build an abstract data type
Hash tables
Dictionary data types
Basics of hashing
Resolving collisions
Chaining
Open addressing
Choosing a hash function
Division method
Multiplication method
Universal hashing
Maintaining a constant load factor
Examples
A low-overhead hash table using open addressing
A string to string dictionary using chaining
Generic containers
Generic dictionary: interface
Generic dictionary: implementation
Object-oriented programming
Recursion
Example of recursion in C
Common problems with recursion
Omitting the base case
Blowing out the stack
Failure to make progress
Tail-recursion and iteration
Binary search: recursive and iterative versions
Mergesort: a recursive sorting algorithm
Asymptotic complexity of recursive functions
Binary trees
Tree basics
Binary tree implementations
The canonical binary tree algorithm
Nodes vs leaves
Special classes of binary trees
Heaps
Priority queues
Expensive implementations of priority queues
Structure of a heap
Packed heaps
Bottom-up heapification
Heapsort
More information
Binary search trees
Searching for a node
Inserting a new node
Deleting a node
Costs
Augmented trees
Applications
Balanced trees
Tree rotations
Treaps
AVL trees
Sample implementation
2–3 trees
Red-black trees
B-trees
Splay trees
How splaying works
Analysis
Other operations
Top-down splaying
An implementation
More information
Scapegoat trees
Skip lists
Implementations
Graphs
Basic definitions
Why graphs are useful
Operations on graphs
Representations of graphs
Adjacency matrices
Adjacency lists
An implementation
Implicit representations
Searching for paths in a graph
Implementation of depth-first and breadth-first search
Combined implementation of depth-first and breadth-first search
Other variations on the basic algorithm
Dynamic programming
Memoization
Dynamic programming
More examples
Longest increasing subsequence
All-pairs shortest paths
Longest common subsequence
Randomization
Generating random values in C
The rand function from the standard library
Supplying a seed with srand
Better pseudorandom number generators
Random numbers without the pseudo
Range issues
Randomized algorithms
Randomized search
Quickselect and quicksort
Randomized data structures
Skip lists
Universal hash families
String processing
Radix search
Tries
Searching a trie
Inserting a new element into a trie
Implementation
Patricia trees
Ternary search trees
More information
Radix sort
Bucket sort
Classic LSB radix sort
MSB radix sort
Issues with recursion depth
Implementing the buckets
Further optimization
Sample implementation
Other topics
More applications of function pointers
Iterators
Option 1: Function that returns a sequence
Option 2: Iterator with first/done/next operations
Option 3: Iterator with function argument
Closures
Objects
Suffix arrays
Why do we want to do this?
String search algorithms
Suffix trees and suffix arrays
Building a suffix array
Searching a suffix array
Burrows-Wheeler transform
Suffix arrays and the Burrows-Wheeler transform
Sample implementation
C++
Hello world
References
Function overloading
Classes
Operator overloading
Templates
Exceptions
Storage allocation
Storage allocation inside objects
Standard library
Things we haven't talked about
Testing during development
Unit tests
What to put in the test code
Example
Test harnesses
Module interface
stack.h
Test code
test-stack.c
Makefile
Makefile
Stub implementation
stack.c
Bounded-space implementation
stack.c
First fix
Final version
stack.c
Moral
Appendix: Test macros
Algorithm design techniques
Basic principles of algorithm design
Specific techniques
Example: Finding the maximum
Example: Sorting
Bit manipulation
Persistence
A simple solution using text files
Using a binary file
A version that updates the file in place
An even better version using mmap
Concurrency and fault-tolerance issues: ACIDity
What next?
What's wrong with C
What C++ fixes
Other C-like languages
Scripting languages
Assignments
Assignment 1, due 2021-02-18 at 17:00 Eastern US time
Bureaucratic part
Run-length encoding
Testing your assignment
Submitting your assignment
Sample solution
Assignment 2, due 2021-02-25 at 17:00 Eastern US time
Output format
Input range
Testing your assignment
Submitting your assignment
Sample solution
Assignment 3, due 2021-03-04 at 17:00 Eastern US time
Pancake instruction set
Undefined behavior
Example
Testing your program
Submitting your assignment
Sample solution
Assignment 4, due 2021-03-11 at 17:00 Eastern US time
Details
Testing your assignment
Submitting your assignment
Sample solution
Assignment 5, due 2021-03-18 at 17:00 Eastern US time
Testing your assignment
Sample solution
Submitting your assignment
Assignment 6, due 2021-03-26 at 17:00 Eastern US time
Testing your assignment
Submitting your assignment
Sample solution
Assignment 7, due 2021-04-01 at 17:00 Eastern US time
Password files
Decryption
Hints
Submitting your assignment
Testing your assignment
Sample solution
Assignment 8, due 2021-04-07 at 23:59 Eastern US time
Compression scheme
Choice of dictionary
Decompressor (provided)
Compressor (to be submitted)
Testing your assignment
Sample solution
Assignment 9, due 2021-04-15 at 17:00 Eastern US time
The Pancake Flipper Markup Language
Your task
Submitting your assignment
Testing your assignment
Sample solution
Assignment 10, due 2021-04-22 at 17:00 Eastern US time
Behavior
Interface
Test program
Submitting your assignment
Testing your assignment
Sample solution
Assignment 11, due 2021-04-29 at 17:00 Eastern US time
The Inserter data type
Interface
Test program
Submitting your assignment
Sample solution
Assignment 12, due 2021-05-06 at 17:00 Eastern US time
Distance-2 colorings
Your task
Submitting your assignment
Testing your assignment
Implementation hints
Sample solution
Sample assignments from Spring 2018
Assignment 1, due Thursday 2018-02-08, at 11:00pm
Bureaucratic part
Pig Esperanto
Your task
Testing your assignment
Submitting your assignment
Sample solution
Assignment 2, due Thursday 2018-02-15, at 11:00pm
Your task
Submitting your assignment
Sample solution
Assignment 3, due Thursday 2018-02-22, at 11:00pm
Your task
Submitting your assignment
Clarifications added after the original assignment was posted
Sample solution
Assignment 4, due Thursday 2018-03-01, at 11:00pm
Your task
Interface
Submitting your assignment
Sample solution
Assignment 5, due Thursday 2018-03-29, at 11:00pm
Your task
List of commands and their effects
Examples
Submitting your assignment
Sample solution
Assignment 6, due Thursday 2018-04-05, at 11:00pm
Text representation of a tree
Examples
Depth
Submitting your assignment
Sample solution
Assignment 7, due Thursday 2018-04-12, at 11:00pm
Interface
Your task
Combining elements
Testing your program
Submitting your program
Sample solution
Assignment 8, due Thursday 2018-04-19, at 11:00pm
The game
Examples
Your task
Efficiency
Bad inputs
Submitting your assignment
Sample solution
Sample assignments from Spring 2015
Assignment 1, due Thursday 2015-01-29, at 11:00pm
Bureaucratic part
A rotten cipher
Your task
Hints
Testing your assignment
Submitting your assignment
Sample solution
Assignment 2, due Wednesday 2015-02-04, at 11:00pm
Opening a safe
Submitting your assignment
Valgrind
Sample solution
Assignment 3, due Wednesday 2015-02-11, at 11:00pm
Quadratic letter sequences
Your task
Submitting your assignment
Sample solution
Assignment 4, due Wednesday 2015-02-18, at 11:00pm
An ASCII art compositor
Submitting your assignment
Notes
Input
Output
General
Sample solution
Assignment 5, due Wednesday 2015-02-25, at 11:00pm
Build a Turing machine!
Example
Your task
Submitting your assignment
Sample solution
Assignment 6, due Wednesday 2015-03-25, at 11:00pm
Sinking ships
Things to watch out for
The testShips program
Submitting your assignment
Provided source files
Sample solution
Assignment 7, due Wednesday 2015-04-01, at 11:00pm
Solitaire with big cards
Explanation of the testing program
Submitting your assignment
Sample solution
Assignment 8, due Wednesday 2015-04-08, at 11:00pm
An ordered set
The testOrderedSet wrapper
Submitting your assignment
Sample solution
Assignment 9, due Wednesday 2015-04-15, at 11:00pm
Finding a cycle in a maze
Input and output format
Submitting and testing your program
Sample solution
Various student contributions
Common C coding and debugging issues
223 Office Hours Bingo