Essential PHP security

Essential PHP security. By Chris Shflett. 2006.

Nice book. Basic rules can apply to sites built in other languages.

ADO.NET 4 Database Programming 2010

Murach's ADO.NET 4 Database Programming with VB 2010, 4th Edition. By Anne Boehm, Ged Mead.

- ADO.NET connection types: sql, ole, odbc
- ADO.NET objects: Connection --> command --> 1) data reader, 2) data adaptor --> dataset, binding.
- Stored procedures and parameters
- Transaction. Begin, Commit, Rollback, Savepoint
- GridView/DetailsView: add/edit/delete, select/multi-select, paging. Can implement these myself.
- XML
- LINQ: to: xml/sql/entity/dataset/objects
- Entity Framework

Visual C# 2008/2012. By John Sharp

p.151. Nullable type.
   int i = null; // wrong
   int? i = null; // right

p.152. ref, out (must assign value in method).
   Need to declare variable as ref/out at both calling site and function definition.

p.176. Class & Struct
                                                                          struct                    class
type                                                                    value                    reference
live on                                                                 stack                   heap
can declare default ctor?                                      no                       yes
after declare ctor, default ctor auto-created?        yes                      no
automatic initialize fields?                                     no                       yes
can initialize instance fields at declaration?            no                       yes

- Collection:
   - Hashtable
   - SortedList - sorted hash table (RB tree?)

p.207. Parameter Arrays. - variable param list.
    - void func(params int[] a) {...}

p.217. CH 12. Inheritance
   - new, virtual, override, hiding/overriding, protected.
   - extension methods?
   - public, protected, private, internal, protected internal 
   - internal: Internal types or members are accessible only within files in the same assembly,
   - protected v.s. protected internal:
      - protected; derived types may access the member.
      - protected internal; only derived types or types within the same assembly can access that member,
        so they need to be in the same Dynamic Link Library or an executable file.

p.239. Interface, Abstract class, Sealed class.
   - interface => virtual => override => sealed

p.274. Property, get/set

p.295. CH 16. Indexer?

p.311. delegate, event

p.333. CH 18. Generics.
    Queue myQ = new Queue();

p.371. LINQ. Language Integrated Query
   - LINQ, DLINQ, XLINQ.
     - Linq is a programming model that introduces queries as a first-class concept into any Microsoft .NET language
     - DLinq (Linq to SQL) is an extension to Linq that allows querying a database and do object-relational mapping.
     - XLinq (Linq to XML) is an extension to Linq that allows querying/creating/transforming XML documents.
   - After ASP.NET 4.0, emphasis is on Entity Framework, which replaces LINQ.

   - Linq v.s. Entity Framework. (some explanation)
     - LINQ to SQL only supports 1 to 1 mapping of database tables, views, sprocs and functions available in Microsoft SQL Server. It's a great API to use for quick data access construction to relatively well designed SQL Server databases. LINQ2SQL was first released with C# 3.0 and .Net Framework 3.5.
    - LINQ to Entities (ADO.Net Entity Framework) is an ORM (Object Relational Mapper) API which allows for a broad definition of object domain models and their relationships to many different ADO.Net data providers. As such, you can mix and match a number of different database vendors, application servers or protocols to design an aggregated mash-up of objects which are constructed from a variety of tables, sources, services, etc. ADO.Net Framework was released with the .Net Framework 3.5 SP1.

p.420. XAML. Extensible Application Markup Language.
    - WPF - XAML - define interface by XML(XAML), independent from application logic.

p.523. DLINQ. Based on ADO.NET. Data LINQ.

p.557. PART VI. Build web app.
   - ASP.NET server control
   - HTML control (runat="server")
   - theme
   - web forms validation controls.

p.623. Web service
   - REST: request by specifically formatted URL
   - SOAP: request by XML message.

Sams Teach Yourself SQL in 24 hours

CH 4. p.61.
   Normalization - reduce redundancy (will reduce performance due to more JOINs, will use more CPU/mem/IO).
   Denormalization. Combines tables, controlled redundancy. Increased performance.

CH 6. Transaction.
   Commit, Rollback, Savepoint

CH 8. All, Some, Any

CH 9. Aggregate functions.

CH 10. Sorting and Grouping.
   Group by.
   - rollup - get subtotal
   - cube - crosstab reports
   - having - GROUP BY/HAVING is similar to SELECT/WHERE
   - p. 243. UNION (no duplicate rows), UNION ALL (including duplicate rows).
   - INTERSECT
   - EXCEPT

CH 16. p. 256. Indexes.
   - When to avoid using indexes.. p. 261

CH 17. Improve DB performance
   - DB tuning / SQL tuning
   - To avoid full table scan, then use Index

CH 18. Manage DB Users
   - Schema - a collection of DB objects that a user owns.
   - DB user - aschema owner
   - Default schema - dbo (db owner)

CH 19. p. 299. Manage DB security.
   - Privilege
   - Control user access. GRANT, REVOKE, ROLE

CH 20. View, Synonym

CH 21. System Catalog

CH 22. Advanced SQL

MSSQL Server 2008

p.103. CH 7. Partitioning

p.219. CH 15. DB snapshots. CREATE database AS Snapshot

p.375. Part VII. Business Intelligence.
CH24. SSIS - SQL Server Integration Services
CH25. SSRS - SQL Server Reporting Services
CH26. SSAS - SQL Server Analysis Services

SSMS - SQL Server Management Studio

Big Data for Dummies

- Part I. Big Data. 3 characteristics: volume, velocity, variety
   - technology: MapReduce, BigTable, Hadoop (started at Yahoo)
- Part II. Tech foundations. p. 68. Hypervisor
   - cloud: Amazon (EC2, 2006), Google (Big Data), MS (Azure), Rackspace, NASA (OpenStack).
- Part III. Management
   - CH 7. Relational Database. CRUD, ACID.
                Non-relational Database.
   - CH 8. MapReduce
   - CH 9. Hadoop
- Part IV. Analytics & Big Data
   - p.145. Data Mining: classfication, log regression, NN, clustering (k-means etc).

Some C#, ASP.NET and SQL books

Browsed some C#, ASP.NET and SQL books. Quickly get through large amount of material, to review and refresh old knowledge, and gain an understanding of new advancement. Most of these books are written for beginners. However, each more or less covers things I did not notice in the past.

- ASP.NET 2.0 in C# 2005
- Learn Microsoft Visual C# 2010. By John Paul Mueller
- murach's ASP.NET web programming with C# 2010, 4th Edition.
- Visual C# 2008. By John Sharp
- Visual C# 2012. By John Sharp. (This book is a minor update from the 2008 version)
- Sams Teach Yourself SQL in 24 hours
- MS SQL Server 2008, by Mike Hotek.
- Big Data for Dummies

Long words short, ASP.NET evolution (see wiki page on ASP.NET):

- 2002.1   1.0  OO, based on windows programming, can use DLL. ADO.NET. VS.NET
- 2003.4   1.1  Automatic input validation; mobile controls. Bug fix, performance increase. VS.NET 2003.
- 2005.11  2.0 Major updates: Partial class, Generics, Anonymous methods, Iterators, master page, theme, navigation, Grid/Form/DetailsView, Login, skin etc. VS.NET 2005
- 2006.11  3.0 WCF, WPF, WFF,
- 2007.11  3.5 MVC (easier to test and for plugable IoC containers etc.), Silverlight, LINQ, Ajax, ADO.NET Entity Framework, ListView, DataPager etc. VS.NET 2008. Windows Server 2008.
- 2012.4    4.0 Parallel extensions.
- 2012.8    4.5 VS.NET 2012. Windows Server 2012. Window 8.

Some more books read recently

编程之美.
数学之美. 吴军著.
Big Data (大数据时代, 2013). Viktor Mayer-Schonberger, Kenneth Cukier.
晓说2. 高晓松著.

Book: Apache Jakarta and Beyond

Book: Apache Jakarta and Beyond - A Java programmer's introduction. By Larne Pekowsky. ISBN 0-321-23771-4 QA76.73.J38P44 2004. 2005.

This book introduces a series of Jakarta tools to be used by Java programmers. Including:

- Ant
- Eclipse
- Testing with JUnit
- Testing web sites with HTTPUnit
- Further web testing with Jakarta Cactus
- Stress Testing with Jakarta JMeter
- Simplifying Bean Development with BeanUtils
- Traversing Hierarchical Data with JXPath
- Database tools: 
  Hsqldb, DBCP, OJB
- Logging
  - Java.util.logging
  - Log4j
- Configuring program options
  - Jakarta CLI (Command-Line Interface)
  - Jakarta Digester (XML-based: object stack, element matching patterns, processing rules)
- Working with Text 1: Regular Expressions
- Working with Text 2: Searching  
- Creating office documents with POI
- Scripting
- Tomcat
- The standard tag library
- Struts: application toolkit/web application framework
- Cocoon: provides a complete XML-based publishing suite, for the generation, manipulation and rendering of XML.

Design Patterns

Design Patterns - Elements of Reusable Object-Oriented Software. This is a classical book. The authors won ACM 2010 SIGSOFT outstanding research award for their contribution to software engineering for. The four authors are classed the GoF (Gang of Four). The design patterns in their book is called the GoF patterns.

Design patterns are solutions abstracted from repeatedly occurring design problems and can be reused in similar situations. Each has a pattern name, associated problem, solution and consequence.

Some design patterns are bounded to languages features, so is easier to implement in some languages than the others. For example, the Template pattern is easy to do in C++ and Java, since C++ provides template and Java provides generics.

In this book, designed patterns are divided into 3 categories based on purpose. The following notes are extracted from the book.

A. Creational

Class:

1. Factory method
Define an interface for creating an object, but let subclasses decide which class to instantiate. It lets a class defer instantiation to subclasses.

Object:

2. Abstract Factory
Provide an interface for creating families of related or dependent objects w/o specifying their concrete classes.

Isn't this the interface concept in C++/Java? Obviously it's related to polymorphism.

3. Builder
Separate the construction of a complex object from its representation so that the same construction process can create different representations.

4. Prototype
Specify the kinds of objects to create using a prototypical instance, and create new objects by copying this prototype.

5. Singleton
Ensure a class only has one instance, and provide a global point of access to it.

B. Structural

Class:

6. Adapter (class)
Convert the interface of a class into another interface clients expect. It lets classes work together that couldn't otherwise because of incompatible interfaces.

Object:

7. Adapter (object)

8. Bridge
Decouple an abstraction from its implementation so that the two can vary independently.

This is the abstraction and encapsulation principles of OOP.

9. Composite
Compose objects into tree structures to represent part-whole hierarchies. It lets clients treat individual objects and compositions of objects uniformly.

OOP uses inheritance for IS-A relationship, and uses composition for HAS-A relationship.

10. Decorator
Attach additional responsibilities to an object dynamically. It provides a flexible alternative to subclassing for extending functionality.

11. Facade
Provide a unified interface to a set of interfaces in a subsystem. Facade defines a higher-level interface that makes the subsystem easier to use.

12. Flyweight
Use sharing to support large numbers of fine-grained objects efficiently.

13. Proxy
Provide a surrogate or placeholder for another object to control access to it.

C. Behavioral

Class:

14. Interpreter
Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

Sounds related to compiler/interpreter.

15. Template method
Define the skeleton of an algorithm in an operation, deferring some steps to subclasses. Template method lets subclasses redefine certain steps of an algorithm w/o changing the algorithm's structure.

Object:

16. Chain of Responsibility
Avoid coupling the sender of a request to its receiver by giving more than one object a chance to handle the request. Chain the receiving objects and pass the request along the chain until an object handles it.

One example to this is to catch a series of exceptions in C++/Java.

17. Command
Encapsulate a request as an object, thereby letting you parameterize clients with different requests, queue or log requests, and support undoable operations.

18. Iterator
Provide a way to access the elements of an aggregate object sequentially w/o exposing its underlying representation.

This occurs abundantly in C++/Java.

19. Mediator
Define an object that encapsulates how a set of objects interact. It promotes loose coupling by keeping objects from referring to each other explicitly, and it lets you vary their interaction independently.

20. Memento
W/o violating encapsulation, capture and externalize an object's internal state so that the object can be restored to this state later.

21. Observer
Define a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.

For example, Java uses wait(), notify() and notifyAll() methods for threads communication.

22. State
Allow an object to alter its behavior when its internal state changes. It will appear to change it class.

One example for this is the workflow state management as in my work.

23. Strategy
Define a family of algorithms, encapsulate each one, and make them interchangeable. It lets the algorithm vary independently from clients that use it.

24. Visitor
Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation w/o changing the classes of the elements on which it operates.

The famous MVC is not included in list because it's a combination of multiple patterns. Use Smalltalk MVC as an example. The VC relationship uses the Strategy pattern. MVC also uses Factory method to specify the default controller class for a view, and Decorator pattern to add scrolling to a view.

A new comer at OOD can start with the simplest and most common patterns:
Creational: Abstract Factory, Factory
Structural: Adapter, Composite, Decorator
Behavioral: Observer, Strategy, Template(! Yeah, this is behavioral, not structural)

Seems like I already had experience with at least these design patterns:
Creational: Singleton, Factory
Structural: Adapter, Bridge, Composite
Behavioral: Interpreter, Template, Chain of Responsibility, Iterator, Observer, State

[1] Amazon: Design patterns. By Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. QA 76.64 .D47 1994.
[2] Wiki - design patterns. Short but comprehensive list of design patterns from different sources.
[3] Design pattern implementation in C# and VB.NET. Good link with real code examples. E.g., load balancer using the Singleton pattern.

Computer Systems: A Programmer’s Perspective

Computer Systems: A Programmer’s Perspective. 1st edition (August 23, 2002). 2nd edition (February 14, 2010). By R. E. Bryant, D. R. O’Hallaron.

This books introduces computer systems in a broad way, including operating system, architecture, compiler, network and more. It is a good reference for system programmers to improve their understanding on computer systems and improve programming skills.

Chapter 1. Introduction

- Compilation
- Processors Read and Interpret Instructions Stored in Memory
  Hardware Organization of a System.
- Cache
  - cache hierarchy (registers, on-chip L1 cache, off-chip L2 cache, memory, local disk, remote storage)
- OS: process, thread, virtual memory, files
- Inter system communication by network.

Part I Program Structure and Execution

Chapter 2 Representing and Manipulating Information
Chapter 3 Machine-Level Representation of C Programs
Chapter 4 Processor Architecture 

Chapter 5 Optimizing Program Performance

5.1 Capabilities and Limitations of Optimizing Compilers
5.2 Expressing Program Performance
5.3 Program Example
5.4 Eliminating Loop Inefficiencies
5.5 Reducing Procedure Calls
5.6 Eliminating Unneeded Memory References
5.7 Understanding Modern Processors
5.7.1 Overall Operation
5.7.2 Functional Unit Performance
5.7.3 A Closer Look at Processor Operation
- Translating Instructions into Operations
- Processing of Operations by the Execution Unit
- Scheduling of Operations with Unlimited Resources
- Scheduling of Operations with Resource Constraints
5.8 Reducing Loop Overhead
5.9 Converting to Pointer Code
5.10 Enhancing Parallelism
5.10.1 Loop Splitting
5.10.2 Register Spilling
5.10.3 Limits to Parallelism
5.11 Putting it Together: Summary of Results for Optimizing Combining Code
5.11.1 Floating-Point Performance Anomaly
5.11.2 Changing Platforms
5.12 Branch Prediction and Misprediction Penalties
5.13 Understanding Memory Performance
5.13.1 Load Latency
5.13.2 Store Latency
5.14 Life in the Real World: Performance Improvement Techniques
5.15 Identifying and Eliminating Performance Bottlenecks
5.15.1 Program Profiling
5.15.2 Using a Profiler to Guide Optimization
5.15.3 Amdahl’s Law
5.16 Summary

Chapter 6 The Memory Hierarchy

- A memory system is a hierarchy of storage devices with different capacities, costs, and access times.
- SRAM, DRAM, disk. 
- Storage technologies
  - Random-access memory
    - SRAM - bistable memory cell.
    - DRAM - capacitors.
    - Nonvolatile memory: ROM, PROM, EPROM, EEPROM.
    - Accessing main memory.
  - Disk storage
    - geometry, capacity, operation (seek time, rotational latency, transfer time),
      logical disk blocks, accessing disks
  - Storage technology trends.
    - price/performance trade-off
- Locality: temporal/spatial locality.
  - Locality of references to program data.
  - Locality of Instruction Fetches.
  - Summary
- The memory hierarchy
  + Different storage technologies have widely different access times.
  + Well-written programs tend to exhibit good locality.
  - Caching in the Memory Hierarchy
    - Cache hits
    - Cache misses
    - Cache Management
  - Summary of Memory Hierarchy Concepts
    - Exploiting temporal/spatial locality
- Cache Memories
  - CPU registers, L1 cache, L2 cache, main DRAM memory, and disk storage
- Writing Cache-friendly Code
  + Make the common case go fast.
  + Minimize the number of cache misses in each inner loop.
- Putting it Together: The Impact of Caches on Program Performance
  - The Memory Mountain
  - Rearranging Loops to Increase Spatial Locality
  - Using Blocking to Increase Temporal Locality
- Summary

Part II Running Programs on a System 

Chapter 7 Linking
Chapter 8 Exceptional Control Flow
Chapter 9 Measuring Program Execution Time

Chapter 10 Virtual Memory

10.1 Physical and Virtual Addressing
10.2 Address Spaces
10.3 VM as a Tool for Caching
+ Set of virtual pages: Unallocated/Cached/Uncached
10.3.1 DRAM Cache Organization
10.3.2 Page Tables
10.3.3 Page Hits
10.3.4 Page Faults
10.3.5 Allocating Pages
10.3.6 Locality to the Rescue Again
10.4 VM as a Tool for Memory Management
10.4.1 Simplifying Linking
10.4.2 Simplifying Sharing
10.4.3 Simplifying Memory Allocation
10.4.4 Simplifying Loading
10.5 VM as a Tool for Memory Protection
10.6 Address Translation
10.6.1 Integrating Caches and VM
10.6.2 Speeding up Address Translation with a TLB
10.6.3 Multi-level Page Tables
10.6.4 Putting it Together: End-to-end Address Translation
10.7 Case Study: The Pentium/Linux Memory System
10.8 Memory Mapping
10.8.1 Shared Objects Revisited
10.8.2 The fork Function Revisited
10.8.3 The execve Function Revisited
10.8.4 User-level Memory Mapping with the mmap Function
10.9 Dynamic Memory Allocation
10.9.1 The malloc and free Functions
10.9.2 Why Dynamic Memory Allocation?
10.9.3 Allocator Requirements and Goals
- Requirements:
  - Handling arbitrary request sequences
  - Making immediate responses to requests
  - Using only the heap.
  - Aligning blocks (alignment requirement).
  - Not modifying allocated blocks.
- Goals:
  - Goal 1: Maximizing throughput.
  - Goal 2: Maximizing memory utilization.
10.9.4 Fragmentation
- internal fragmentation: 
  occurs when an allocated block is larger than the payload.
  e.g. to satisfy memory alignment.
- external fragmentation: 
  there is enough aggregate free memory to satisfy an 
  allocate request, but no single free block is large enough
- External fragmentation is much more difficult to quantify than internal
  fragmentation
10.9.5 Implementation Issues
10.9.6 Implicit Free Lists
10.9.7 Placing Allocated Blocks
10.9.8 Splitting Free Blocks
10.9.9 Getting Additional Heap Memory
10.9.10 Coalescing Free Blocks
10.9.11 Coalescing with Boundary Tags
10.9.12 Putting it Together: Implementing a Simple Allocator
10.9.13 Explicit Free Lists
10.9.14 Segregated Free Lists
10.10 Garbage Collection
10.10.1 Garbage Collector Basics
- A garbage collector views memory as a directed reachability graph.
- The nodes of the graph are partitioned into 1) root nodes and 2) heap nodes.
10.10.2 Mark&Sweep Garbage Collectors
10.10.3 Conservative Mark&Sweep for C Programs
10.11 Common Memory-related Bugs in C Programs
10.11.1 Dereferencing Bad Pointers
10.11.2 Reading Uninitialized Memory
10.11.3 Allowing Stack Buffer Overflows
10.11.4 Assuming that Pointers and the Objects they Point to Are the Same Size
10.11.5 Making Off-by-one Errors
10.11.6 Referencing a Pointer Instead of the Object it Points to
10.11.7 Misunderstanding Pointer Arithmetic
10.11.8 Referencing Non-existent Variables
10.11.9 Referencing Data in Free Heap Blocks
10.11.10 Introducing Memory Leaks
10.12 Summary

Part III Interaction and Communication Between Programs

Chapter 11 Concurrent Programming with Threads

- A thread is a unit of execution, associated with a process, with its own 
  thread ID, stack, stack pointer, program counter, condition codes, and 
  general-purpose registers.
11.1 Basic Thread Concepts
- process context: 1) program context, 2) kernel context.
11.2 Thread Control
- Pthreads defines about 60 functions
11.2.1 Creating Threads
11.2.2 Terminating Threads
11.2.3 Reaping Terminated Threads
11.2.4 Detaching Threads
11.3 Shared Variables in Threaded Programs
11.3.1 Threads Memory Model
11.3.2 Mapping Variables to Memory
11.3.3 Shared Variables
11.4 Synchronizing Threads with Semaphores
11.4.1 Sequential Consistency
11.4.2 Progress Graphs
11.4.3 Protecting Shared Variables with Semaphores
11.4.4 Posix Semaphores
11.4.5 SignalingWith Semaphores
11.5 Synchronizing Threads with Mutex and Condition Variables
11.5.1 Mutex Variables
11.5.2 Condition Variables
11.5.3 Barrier Synchronization
11.5.4 Timeout Waiting
11.6 Thread-safe and Reentrant Functions
- A function is thread-safe if and only if it will always produce correct results 
  when called repeatedly within multiple concurrent threads.
- Four (non-disjoint) classes of thread-unsafe functions:
  1) Failing to protect shared variables.
  2) Relying on state across multiple function invocations.
  3) Returning a pointer to a static variable.
  4) Calling thread-unsafe functions.
11.6.1 Reentrant Functions
- Property: do not reference any shared data when called by multiple threads.
- Reentrant functions are typically more efficient than non-reentrant
  thread-safe functions because they require no synchronization operations.
- Reentrant functions is a subset of thread-safe functions.
11.6.2 Thread-safe Library Functions
11.7 Other Synchronization Errors
11.7.1 Races
11.7.2 Deadlocks
11.8 Summary

Chapter 12 Network Programming

12.1 Client-Server Programming Model
- The fundamental operation in the client-server model is the transaction.
12.2 Networks
12.3 The Global IP Internet
12.3.1 IP Addresses
12.3.2 Internet Domain Names
12.3.3 Internet Connections
12.4 Unix file I/O
12.4.1 The read and write Functions
12.4.2 Robust File I/OWith the readn and writen Functions
12.4.3 Robust Input of Text Lines Using the readline Function
12.4.4 The stat Function
12.4.5 The dup2 Function
12.4.6 The close Function
12.4.7 Other Unix I/O Functions
12.4.8 Unix I/O vs. Standard I/O
12.5 The Sockets Interface
12.5.1 Socket Address Structures
12.5.2 The socket Function
12.5.3 The connect Function
12.5.4 The bind Function
12.5.5 The listen Function
12.5.6 The accept Function
12.5.7 Example Echo Client and Server
12.6 Concurrent Servers
12.6.1 Concurrent Servers Based on Processes
12.6.2 Concurrent Servers Based on Threads
12.7 Web Servers
12.7.3 HTTP Transactions
12.8 Putting it Together: The TINY Web Server
12.9 Summary

Appendix A Error handling
Appendix B Solutions to Practice Problems

Sams Teach Yourself TCP/IP in 24 Hours

Sams Teach Yourself TCP/IP in 24 Hours (4th Edition) - by Joe Casad, 2008, 456 pages. ISBN-10: 0672329964.

I caught this book in sight at Barns and Noble. It is a short book to read, to the point and clear on basic concepts. Short is good.

I. TCP/IP basics

II. TCP/IP Protocol system

2. Correspondence of TCP/IP model and OSI model.
  TCP/IP                      OSI         Relevant protocols
  ----------------------------------------------------------------------------------
  Application layer           A,P,S          
  Transport layer             T           TCP/UDP
  Internet layer              N           IP, ARP, RARP, ICMP, router(RIP, OSPF etc.)
  Network access layer        D,P         FTS, FDDI, PPP, 802.11, 802.3, 802.16

  note: 802.3 - ethernet, 802.11 - wireless, 802.16 - winmax

3. Network access layer
  - physical addressing.
  - LAN - ethernet.
    CSMA/CS (Carrier Sense Multiple Access with Collision Detect)
    ethernet frame: preamble|dest addr|sr addr|length|data|FCS(CRC)

4. Internet layer
  - IP, IP header
  - IP addressing: class A(8/24), B(16/16), C(24/8), D, E
  - ARP (Address Resolution Protocol)
  - RARP (Reverse ARP)
  - ICMP
  - BGP (Border Gateway Protocol), RIP (Routing Information Protocol)

5. Subnetting & CIDR (Classless Inter-Domain Routing)
  - subnet mask/host ID
  - split and combine networks.

6. Transport layer
  - TCP/UDP
  - ports, sockets
  - multiplexing, demultiplexing.
  - TCP: stream, resequencing, flow control, precedence & security, graceful close.

7. Application layer
  - use socket/port to communicate with transport layer.
  - target of multiplexing/de-multiplexing

III. Networking with TCP/IP

8. Routing
  - routing table
  - IP forwarding
  - Dynamic routing algorithm
    - DV (Distance vector). e.g. RIP
    - LS (Link state). e.g. OSPF (Open Shortest Path First)
      LS is more popular than DV now.
  - Complex network routing
    1) core router - backbone network (GGP)
    2) exterior router - on border of autonomous systems (EGP: e.g. BGP)
    3) interior router - within autonomous system (IGP: OSPF/RIP)
  - classless routing: CIDR.
  - OSPF: implemented as routed on unix/linux, builds SPT (Shortest Path Tree)

10. Firewall
  - DMZ (Demilitarized Zone)
  - rules
  - proxy service
  - reverse proxy

11. Name resolution
  - DNS (Domain Name Server)

IV. TCP/IP utilities.

V. TCP/IP and the internet

18. Email
  - outgoing email: SMTP
  - incoming email: POP3/IMAP

19. Streaming and casting
  - stack:
    RTP
    UDP
    Internet layer
    Network Access layer

VI. Advanced topics

C Traps and Pitfalls

C Traps and Pitfalls - by Andrew Koenig, 1989, 160 pages. ISBN-10: 0201179288.

Andrew Koenig wrote a small reference manual on C programming based on his experience when he worked at AT&T lab. Since it received wide acceptance, he added more material and resulted in this book. It's highly recommended to any serious C programmers. Some contents are kind of outdated, such as those about problems of early day compilers. But many points are still ubiquitously applicable.

- Introduction

- Chapter 1. Lexical pitfalls
  1.3 greedy principle in evaluating statement.
      e.g. a --- b is: a-- - b, 
           y = x/*p is: y=x plus the start of a comment! 
                        Should write as y = x / *p or y = x / (*p).
           a +++++ b is: a++ ++ + b. This has compile error since a++ is not l-value.
      Be careful, if a number starts with 0, it's an octal number.

- Chapter 2. Syntax pitfalls
  2.1 Function declaration.
      This casts address 0 as the pointer to function void f() and call it.
      (* (void (*)()) 0)(); 
  2.2 Operator precedence.
      if (a == 'a' || b = 'b' || c == 'c') {} is equivalent to:
      if ((a == 'a' || b) = ('b' || c == 'c')) {}
  2.6 dangling else.
      if (a) 
        if (b) b ++;
      else { c ++; }
      is equivalent to:
      if (a) {
        if (b) b ++;
        else { c ++; }
      }

Chapter 3. Semantic pitfalls
  3.6 off-by-1 error - is the most prevalent.
      One solution in C: 0-based C array, using asymmetric boundary.
      e.g. x >= 16 && x < 38. 38-16 is exactly the size of the range.
  3.9 Check overflow.
      method 1: if ((unsigned) a + (unsigned) b > INT_MAX) // overflowed
      method 2: if (a > INT_MAX - b) // overflowed

Chapter 4. Linking
  lint.

Chapter 5. Library functions
  5.1 int getchar() - return types does not match function, can cause problem.
  5.2 I/O buffer. 
      setbuf(stdout, (char *) 0); // no buffer
  5.4 errno
  5.5 signal, longjmp

Chapter 6. Preprocessor
  - macro
  - use of -- or ++ can cause unexpected side effects in macro.
  6.3 assert
      #define assert(e) \
              ((void) ((e) || _assert_error(__FILE__, __LINE__)))

Chapter 7. Portability
  7.5 >> and divide by 2. >> is faster and works correctly when var is positive.
      e.g. replace "mid = (left + right) / 2" with "mid = (left + right) >> 1".
  7.11 literal string can represent an array.
      e.g. "0123456789"[n%10] is equivalent to: a[] = "0123456789"; a[n%10];
           This is used in systems where 0-9 may not be consecutive.

Chapter 8. Suggestions and answers.
  - Optimize binary search: 
    1) use >> instead of 1/2, 2) use pointer instead of array indexing.
  - Little/big ending.
  - getchar(), putchar() have both macro and function definitions. macro is faster.
  - atol().

Appendix A
  - printf. %p, %n, %06d is equivalent to %.6d in most cases.
  - varargs
  - stdarg

Author's suggestions on using C++:
  - avoid pointer
  - use library
  - use class

More Effective C++

More Effective C++

Basics

1. Pointers and References.
   - A reference must be initialized. There is no null reference.
   - result of the following is undefined:
   char *pc = 0; // set pointer to null
   char& rc = *pc; // make reference refer to
   - Reference is more efficient, b/c there is no need to test its validity.
   - Pointers should generally be tested against NULL first.
   - A pointer can be reassigned, but a reference does not change.
   - certain operators need to use reference, e.g., [].
   


2. Prefer C++-style casts. (over C-style cast: (type) expression)
   - static_cast (similar to C-style cast in fxn): static_cast(expression)
   - const_cast: cast away the constness or volatileness of an expression. enforced by compiler
   - dynamic_cast: perform safe casts down or across an inheritance hierarchy. Failed casts are indicated by a null pointer (when casting pointers) or an exception (when casting references).
   - reinterpret_cast: result is implementation-defined. rarely portable.
   


3. Never treat arrays polymorphically.
   - not able to distinguish between base type and derived type for correct polymorphism.
   


4. Avoid gratuitous default constructors.

Operators

5. Be wary of user-defined conversion functions.
   - Single-argument constructors
   - Implicit type conversion operators (better avoid)
   


6. Distinguish between prefix and postfix forms of increment and decrement operators.
   - E.g. Class UPInt. prefix ++ returns reference, postfix ++ returns const object.
   - i ++++ is inhibited.
   - i ++ is less efficient because it creates a temporary copy of its return value.
   


7. Never overload &&, ||, or ,.
   - otherwise it'll lose short-circuit semantics, and sequence of evaluation becomes uncertain.
   


8. Understand the different meanings of new and delete.
   - new operator: 1) allocates memory, 2) calls constructor
   - operator new: does memory allocation only. knows nothing about constructor
   - placement new
   - Deletion and Memory Deallocation
   - Array
   

Exceptions

9. Use destructors to prevent resource leaks.
   - pointer operation may lead to memory leak if exception is thrown
   - a possible solution is to use local object instead of pointer, with help of smart_ptr, or STL auto_ptr.
   


10. Prevent resource leaks in constructors.
    - destructor deletes only FULLY constructed objects. So if an exception is thrown in constructor, destructor won't be called.
    


11. Prevent exceptions from leaving destructors.
    - if control leaves a destructor due to an exception while another exception is active, C++ terminates the program.
    - stack unwinding.
    


12. Understand how throwing an exception differs from passing a parameter or calling a virtual function. (more reading needed)
    


13. Catch exceptions by reference.
    - four standard exceptions: 1) bad_alloc (thrown when operator new (see Item 8) can't satisfy a memory request), 2) bad_cast (thrown when a dynamic_cast to a reference fails; see Item 2), 3) bad_typeid (thrown when dynamic_cast is applied to a null pointer), and 4) bad_exception (available for unexpected exceptions).
    


14. Use exception specifications judiciously. (more reading needed)


15. Understand the costs of exception handling.

Efficiency

16. Remember the 80-20 rule.


17. Consider using lazy evaluation. (more reading needed)


18. Amortize the cost of expected computations.
    - over eager evaluation, caching
    - prefetching
    


19. Understand the origin of temporary objects.


20. Facilitate the return value optimization.


21. Overload to avoid implicit type conversions.


22. Consider using op= instead of stand-alone op.


23. Consider alternative libraries.


24. Understand the costs of virtual functions, multiple inheritance, virtual base classes, and RTTI.
    - virtual table (vtable)
    - RTTI: runtime type identification
    

Techniques

25. Virtualizing constructors and non-member functions.


26. Limiting the number of objects of a class.


27. Requiring or prohibiting heap-based objects.


28. Smart pointers.


29. Reference counting.
    - a simple form of garbage collection.
    


30. Proxy classes.


31. Making functions virtual with respect to more than one object.

Miscellany

32. Program in the future tense.


33. Make non-leaf classes abstract.


34. Understand how to combine C++ and C in the same program.
    - name mangling
    - initialization of statics
    - dynamic memory allocation
    - data structure compatibility
    


35. Familiarize yourself with the language standard.

Recommended Reading
An auto_ptr Implementation

Effective C++

Scott Meyers' Effective C++ (1997)

Shifting from C to C++


1. Prefer const and inline to #define
   - Value by #define does not go to symbol table, but processed by preprocessor.
   - For const pointer, needs to be like const char * const a = "zzz";
   - Class-specific constants: in class declaration: "static const int a;", need to define outside class.
   


2. Prefer <iostream> to <stdio.h>
   - stdio.h is not type-safe and not extensible.
   - e.g. friend ostream& operator<<(ostream& s, const Rational& r);
   - iostream is in std (preferred), iostream.h is in global range.
   


3. Prefer new/delete to malloc/free
   - Reason: malloc/delete do not know constructor/destructor
   


4. Prefer C++ style comments (// ...) over C'(/* ... */)
   - Note some preprocessors only recognize /* ... */
   

Memory management


5. Use the same form in corresponding uses of new and delete.
   - Example:
   string *stringPtr1 = new string;
   string *stringPtr2 = new string[100];
   ...
   delete stringPtr1; // delete an object
   delete [] stringPtr2; // delete an array of
   


6. Use delete on pointer members in destructors
   - Delete a NULL pointer does no harm (free a NULL pointer causes error though)
   - One way to avoid using delete is to use smart pointers (e.g. auto_ptr in STL)
   


7. Be prepared for out-of-memory conditions (more reading needed..)
   - When new fails, it throws an exception std::bad_alloc (in old compilers, it may return NULL)
   - assert is a macro. It does not work when NDEBUG is defined.
   


8. Adhere to convention when writing operator new and operator delete. (more reading needed..)
   


9. Avoid hiding the "normal" form of new.
   - Declare a function called "operator new" inside the class would block access to the "normal" form of new.
   - Two solutions: 1) overload operator new, 2) provide default value for additional parameters.
   - Example:

   class X {
   public:
     void f();
     static void * operator new(size_t size, new_handler p);
     static void * operator new(size_t size)
     { return ::operator new(size); }
   };
   X *px1 = new (specialErrorHandler) X;  // calls X::operator new(size_t, new_handler)
   X* px2 = new X;                        // calls X::operator new(size_t)



10. Write operator delete if you write operator new. (new/delete should be paired) (more reading needed..)
    

Constructors, Destructors and Assignment Operators

Almost every class has one or more constructors, a destructor, and an assignment operator.

11. Declare a copy constructor and an assignment operator for classes with dynamically allocated memory.


12. Prefer initialization to assignment in constructors. (more reading needed..)


13. List members in an initialization list in the order in which they are declared.
    - Otherwise there is overhead for compiler to track information.
    


14. Make sure base classes have virtual destructors.
    - Base class virtual destructor should be used when base class has virtual fxns.
    - No virtual fxns in a base class often means it's not suitable to be a base class.
    - When need an abstract class, it may be convenient to declare destructor as pure virtual destructor, but then a definition of it should also be defined.
    


15. Have operator= return a reference to *this. (more reading needed..)
    - So as to be able to chain assignments together (assignment is right associative)
    


16. Assign to all data members in operator=. (more reading needed..)
    


17. Check for assignment to self in operator=. (more reading needed..)
    

Classes and Functions: Design and Declaration

18. Strive for class interfaces that are complete and minimal.


19. Differentiate among member functions, non-member functions, and friend functions.
    - Member fxns can be virtual, non-member fxns can't.
    - Operator>> and operator<< are never members.
    - Only non-member functions get type conversions on their left-most argument.
    - Everything else should be a member function.
    


20. Avoid data members in the public interface.
    - Use access/inline functions instead of data members.
    


21. Use const whenever possible. (more reading needed)
    - const value and const pointer
    - mutable
    - const_cast()
    


22. Prefer pass-by-reference to pass-by-value.
    - The meaning of passing an object by value is defined by the copy constructor of that object's class. This can be expensive.
    - Bad use: Student returnStudent(Student s) { return s; }
    - Good use: const Student& returnStudent(const Student& s) { return s; }
    - Slicing problem. (Pass by base class type will cut off derived class members.)
    - Aliasing.
    - Reference is implemented by pointer.
    


23. Don't try to return a reference when you must return an object.
    - E.g., operator* should return an object instead of reference.
    


24. Choose carefully between function overloading and parameter defaulting.
    - 2 questions: 1) is there a value you can use for a default? 2) how many algorithms do you want to use?
    


25. Avoid overloading on a pointer and a numerical type.


26. Guard against potential ambiguity. (more reading needed)


27. Explicitly disallow use of implicitly generated member functions you don't want.
    - E.g. operator=
    


28. Partition the global namespace. (more reading needed)

Classes and Functions: Implementation

29. Avoid returning "handles" to internal data.


30. Avoid member functions that return non-const pointers or references to members less accessible than themselves.


31. Never return a reference to a local object or to a dereferenced pointer initialized by new within the function.
    - e.g. this is bad because the difficulty of applying delete:
    inline const Rational& operator*(const Rational& lhs, const Rational& rhs)
    { Rational *result = new Rational(lhs.n * rhs.n, lhs.d * rhs.d); return *result; }
    


32. Postpone variable definitions as long as possible.
    - instead of "string encrypted; encrypted = password;", use "string encrypted = password;", this avoids calling default constructor on string.
    


33. Item 33: Use inlining judiciously.
    - inline function used extensively may increase code size a lot.
    - inline, like "register", is only a hint to compiler.
    - uninlined inline function, in old rule, is treated as static and included into every translation unit.
    - library needs careful consideration on inline function, inline functions make it impossible to provide binary upgrades to the inline functions in a library - all clients have to recompile.
    - inline function should avoid using static variable.
    - most debuggers have problem with inline function.
    


34. Minimize compilation dependencies between files.
    - should do: replacement of dependencies on class definitions with dependencies on class declarations
    - Avoid using objects when object references and pointers will do.
    - Use class declarations instead of class definitions whenever you can.
    - Don't #include header files in your header files unless your headers won't compile without them.
    - Handle/body class, envelope/letter class.
    

Inheritance and Object-Oriented Design

35. Make sure public inheritance models "isa."
    - isa == public inheritance
    - Two other common inter-class relationships are "has-a" and "is-implemented-in-terms-of."
    


36. Differentiate between inheritance of interface and inheritance of implementation. (more reading needed)


37. Never redefine an inherited nonvirtual function.
    - nonvirtual - statically bound
    - virtual - dynamically bound
    


38. Never redefine an inherited default parameter value.
    - default parameters are statically bound!
    


39. Avoid casts down the inheritance hierarchy.
    - down cast: from a base class pointer to a derived class pointer
    - down cast leads to a maintenance nightmare
    - safe downcasting: by using dynamic_cast
    


40. Model "has-a" or "is-implemented-in-terms-of" through layering.
    - difference between isa and is-implemented-in-terms-of
    


41. Differentiate between inheritance and templates. (more reading needed)


42. Use private inheritance judiciously. (more reading needed)
    - compilers will generally not convert a derived class object into a base class object if the inheritance relationship between the classes is private.
    - members inherited from a private base class become private members of the derived class, even if they were protected or public in the base class.
    - private inheritance means is-implemented-in-terms-of.
    - use layering whenever you can, use private inheritance whenever you must.
    - template-induced code bloat. It is not a good thing.
    


43. Use multiple inheritance (MI) judiciously. (more reading needed)
    - MI leads to many problems, one is ambiguity (diamond inheritance).
    


44. Say what you mean; understand what you're saying.

Miscellaneous

45. Know what functions C++ silently writes and calls.
    - default constructor, destructor, assignment/copy constructor, address-of operator, const address-of operator.
    


46. Prefer compile-time and link-time errors to runtime errors.


47. Ensure that non-local static objects are initialized before they're used. (more reading needed)


48. Pay attention to compiler warnings.


49. Familiarize yourself with the standard library.


50. Improve your understanding of C++.

Career-Cup Top 150 Questions

The book is pretty easy to read.

There are over 20 chapters, each covers one area of topic, includes a short discussion and a small number of relevant problems.

Solutions to all questions are provided at the later half of the book.
http://www.docin.com/p-41796787.html
http://www.careercup.com/book

Linkers and Loaders

== Linkers and Loaders ==
By John R. Levine. 2000. ISBN 1-55860-496-0

- linkers and loaders are part of the software toolkit for almost 
  as long as there have been computers.
- This book is for: 
  students, programmers, computer language designers and developers.
- All the linker writers in the world could probably fit in one room, 
  and half of them would already have this book because they reviewed 
  the manuscript.

Chapter 1. Linking and Loading

1.1 What do linkers and loaders do?
- Basic job of linker/loader: binds more abstract names to more 
  concrete names. (name management, address binding)

1.2 Address binding: A historical perspective
- Linker and Loader divides the job: Linker do part of address binding, 
  assign relative addresses. Loader do final step of assigning actual addresses.

1.3 Linking and Loading
- linker does 1) symbol resolution, loader does 2) program loading. 
  Either can do 3) relocation.
- There are linking loaders that do all 3 functions
- Both patch object code

- Two-pass linking: linking is fundamentally a 2-pass process: 
  step 1) collecting info, step 2) linking
  object files + shared lib + normal lib + linker control files + cmd line args --> 
  (linker) --> 
  Debug symbol file + Executable file + link/load map
- Object code libraries
- Relocation and code modification

1.4 Compiler drivers
- assembly code --> object code --> link object code and library together
- Linker command languages. Ways of passing commands to a linker:
  1) command line, 2) intermixed with obj files, 
  3) embedded in obj files, 4) separate config language.

1.5 Linking: A true-life example

Chapter 2. Architecture issues

- Architecture: 1) hardward (program addressing, instruction formats), 2) OS.

2.1 ABI (Application Binary Interfaces)
- procedure call etc.

2.2 Memory addresses
- Byte order & alignment
  IBM/Motorola: big endian
  Intel/DEC: little endian
- misalignment: fault, or loss of performance
- register. size: program address

2.3 Address formation
- clean: 360/370/390 
- simple: SPARC (RISC): v8 (32-bit), v9 (64-bit)
  similar to other RISC arch: MIPS, Alpha
- irregular: x86

2.4 Instruction formats
- opcode operand
- direct/register addressing, base/indexed addressing
- fixed/variable length instruction
  SPARC: all 4 bytes
  370: 2/4/6 bytes
  x86: 1-14 bytes

2.5 Procedure calls and addressibility
- abandon direct addressing for shorter instructions at the cost of 
  more complicated programming.
- bootstrapping for non-direct addressing
- procedure calls
- stack frame
  arguments/local variables - on stack
  local/global static variables - on heap

More Programming Pearls - Reading notes

==## Part I: Programming techniques ##==

==Column 1== Profilers

- Profilers: 1) line-count, 2) procedure-time
- e.g. Optimize prime testing
* test until square root
* rule out 2, 3, 5
* use multiplication instead of division
* test only previous primes
* simple sieve of Evatosthenes
(complexity: time - O((nlogn)(loglogn)), space - O(n)).
(Complexity with optimizations such as wheel factorization: time - O(n), space - O(n^{1 / 2}loglogn / logn)

- A specialized profiler
- Building profiler: 1) insert counter to source code, 2) run it, 3) collect counter output.

==Column 2== Associative arrays

- i.e., Associative array in AWK, or Hash in perl.
- e.g., A finite state machine simulator
- e.g., Topological sorting

==Column 3== Confession of a coder

- Scaffolding for testing and debugging
- e.g. Binary search
- e.g. k-th smallest selection
- e.g. A subroutine library

==Column 4== Self-describing data

- Name-value pairs
- Provenances in programming. (metadata, e.g., history of the code)
- e.g. A sorting lab

==## Part II: Tricks of the trade ##==

==Column 5== Cutting the gordian knot (finding a clever solution to a complex problem)

- Gordius tied the knot. Asia was the promised prize to anyone who can untie it. Alexander the Great approached it in 333 B.C. He drew his sword and slashed through the knot. Asia was soon his.
- Mail sorting: instead of let a clerk do the sorting, just let the mailman drop to different mailbox.
- Data transmission: instead of an automobile courier, use a pigeon.
- Random sample: draw from a box.

==Column 6== Bumper-sticker computer science

- pi seconds is a nano century
- Plagiarism is the sincerest form of flattery
- Coding
* If you can't write it down in English, you can't code it.
- User Interface
- Debugging
- Performance
- Documentation
- Managing software
- Miscellaneous rules

==Column 7== The envelope is back (Back of envelop calculation)

- Order of magnitude.
- Little's Law (Law of system flow and congestion): the average of things in the system is the product of the average rate at which things leave the system and the average time each one spends in the system.

==Column 8== The furbelow memorandum

- Larger programmer stuff team leads to larger cost than expected
- Fred Brooke's Mythical Man Month (1975).

==## Part III: I/O Fit for Humans ##==

==Column 9== Little language

- The PIC language

==Column 10== Document design

- Tables
- 3 design principles: interaction, consistency, minimalism
- Figures
- Text
- Medium

==Column 11== Graphic output

==Column 12== A survey of surveys

==## Part IV: Algorithms ##==

==Column 13== Random sampling

- A flawed algorithm
- * Floyd's algorithm
- * Random permutations

==Column 14== Birth of a cruncher

- The problem
- Newton iteration
- Decide starting point
- Coding

==Column 15== k-th smallest selection

- Problem
- Program.
* O(n log(n)) algorithm
* An O(n) algorithm by L.A.R. Hoare: by quick-sort
- Analysis
- Principles

Programming Pearls - Reading notes

==## Part I ##==Preliminaries

==Column 1== Cracking the Oyster

The major point is find the optimal solution of a problem, instead of going straight with a rash solution.
The coding example is soring with bit vector (aka bitmap).

==Column 2== Aha! Algorithms

- binary search
* search
* find bug by setting checking points in a binary search pattern
* find missing element in an integer range
* finding root for equation: bisection method in numerical analysis

- the power of primitives
Problem: rotating an array ab to ba.
Solutions:
* copying. but this is space inefficient
* juggling
* recursive swapping
* define primitive action reverse(): a b -> a^r b -> a^r b^r -> b a

- sorting
Problem: find anagrams in a dictionary.
Solution: get signature for each word.

==Column 3== Data structures programs

- Use of array
- Structuring data
- Powerful tools for specialized data

Don't write a big program when a little one will do.

==Column 4== Writing correct programs

- binary search - hard to get right
- program verification, invariant

==Column 5== A small matter of programming

- Use assertion for correctness
- Scaffolding
- Automated testing
- debugging
- Timing

==## Part II ##==Performance

==Column 6== Perspective on Performance

- A case study: Andrew Appel's many-body simulation program
- Work at many level to achieve performance improvement:
* problem definition
* system structure
* algorithms and data structures
* code tuning
* hardware

==Column 7==The back of the envelop

- Calculation by reasonable estimation
- Quick check: Test by dimension
- Rules of thumb: e.g., 1) Rule of 72 (for exponential increase), 2) pi seconds is a nanocentury.
- Performance estimates, and little experiments
- Safety factors: compensate ignorance with extra safe factors
- Little's Law: queue size = consumption rate * average wait time

==Column 8==Algorithm design techniques

- Problem: range of array for max sum
- Solutions:
* cubic
* quadratic
* Divide and conquer (n log(n))
* scanning (linear)

==Column 9==Code tuning

- Prevent premature optimization
- Optimization should be made on the bottle-neck part - profiling the program

==Column 10==Squeezing space

- The key is simplicity
- Example: sparse matrix representation of grid.
- When simplicity is not sufficient, there are skills to better utilize space:
* recompute
* sparse data structure
* data compression
* allocation policies
* garbage collection

==## Part III ##==The Product

==Column 11==Sorting

- Insertion sort
- Quick sort

==Column 12== A sample problem

- Problem: sampling: select m from n integers
* by selection
* by shuffling
- Principles: understand the problem, specify an abstraction, explore design space, implement, retrospect.

==Column 13== Searching

- Problem: store a set of integers (w/o associated data).
- linear structure
- binary search trees: STL, BST, BST*, Bins, Bins*, BitVec
- structures for integers

==Column 14== Heaps

- Heap, Priority Queue, Heap sort
Comment: the material here can be found in any data structure and algorithm textbook, nothing new.

== Column 15== Strings of pearls

- We are surrounded by strings
- Words. 1) Map, Set, 2) Hash (no worst case guarantee, no order information)
- Phrases.
* the longest substring problem - solved by suffix array
- Generating sentences

==Appendix 1== A catalog of algorithms

- Sorting
- Searching
- Other Set algorithms
- Algorithms on Strings
- Vector and Matrix algorithms
- Random objects
- Numerical algorithms

==Appendix 4== Rules for code tuning

- Space-for-time rules
- Time-for-space rules
- Loop rules
- Logic rules
- Procedure rules
- Expression rules