Notes on Data Structures and Programming Techniques

Why should you learn about data structures and programming techniques? For small programs, you don’t need much in the way of data structures. But as soon as you are representing reasonably complicated data, you need some place to store it. Thinking about how you want to store and organize this data can be a good framework for organizing the rest of your program. Many programming environments will give you a rich collection of built-in data structures as part of their standard library. C does not: unless you use third- party libraries, any data structure you want in C you will have to build yourself. For most data structures this will require an understanding of pointers and storage allocation, mechanisms often hidden in other languages. Understanding these concepts will give you a deeper understanding of how computers actually work, and will both let you function in minimalist environments where you don’t have a lot of support and let you understand what more convenient environments are doing under their abstraction barriers. The same applies to the various programming techniques we will discuss in this class. While some of the issues that come up are specific to C and similar low- level languages (particular issues involving disciplined management of storage), some techniques will apply no matter what kinds of programs you are writing and all will help in understanding what your computer systems are doing even if some of the details are hidden. 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