### Basic Algorithms and Data Structures

• complexity
• O-notation, definition
• performance of all the basic algorithms
• lists and arrays
• hash table
• LIFO and FIFO implementations using arrays
• exponential growth
• amortized costs
• sorting
• bubble sort
• insertion sort
• quicksort
• heapsort
• mergesort
• stability
• ordered data structures
• heap, priority queue
• binary tree
• AVL, 2-3, RB trees
• B-trees
• skip lists
• treap
• other data structures
• hash tables
• tries
• union-find
• computational geometry
• triangulations
• convex polygons
• Voronoi diagrams and basic algorithms
• arrangements
• kD-trees

### Strings

• ASCII/Unicode encoding
• regular expressions
• recursive descent parsing
• string edit distance computation
• string hashing
• trie implementation
• Boyer-Moore string search
• finite state automata

### Numerical Algorithms

• numbers
• modular arithmetic
• floating point representation
• complex arithmetic
• interval arithmetic
• quaternions
• polynomial evaluation and arithmetic
• analysis
• trapezoidal integration
• numerical differentiation
• difference equations
• partial differential equations
• Taylor series expansions
• splines
• linear algebra
• matrix multiplication
• Gaussian elimination
• iterative eigenvalue computations
• optimization
• binary search for finding zeros
• Newton algorithm
• simplex algorithm for linear programming
• simplex algorithm for nonlinear optimization
• statistics
• computation of basic statistics
• pseudo-random number generation
• gaussian random number generation
• linear regression
• numerical libraries
• understand how to use numerical libraries and common algorithms in them

### Programming and Architecture

• Lisp syntax
• Prolog and Prolog syntax
• functional programming and list programming
• array programming
• assembly programming in some simple language
• lexical and dynamic scoping
• static and dynamic typing
• lexical closures
• dynamic method binding
• processor architecture
• memory hierarchy, caching
• speculative execution
• C programming, C pointers
• debugging in gdb
• garbage collection
• relational databases, formulating SQL queries, joins
• Ubuntu installation, package management
• basic TCP/IP configuration, routine, packet structure