Books on Programming Contests

算法艺术与信息学竞赛. 刘汝佳, 黄亮著 (2003). 经典著作. 高度推荐. 理论介绍全面深入, 一些别的书不常见的内容这里也有. 难度较高. 有大量经典题目. 2003版为一册. 最近新版(算法竞赛入门经典(2009), 算法竞赛入门经典--训练指南(2012), 算法艺术与问题求解)更新为三册. 百度百科简介.

ACM国际大学生程序设计竞赛. 俞勇主编 (2013). (ISBN 978-7-302-29413-9). 分四册. 全面精简, 书薄, 总结得好, 易读易懂易记. 高度推荐.

实用算法的分析与程序设计(1998)/新编实用算法的分析与程序设计(2008). 吴文虎、王建德编著. 经典老著作.

程序设计中使用的数据结构. 王建德, 吴永辉编著 (2012). (ISBN 978-7-115-26865-5). 组织分成三部分: 线性表, 树, 图. 比较全面. 例题有一定难度. 但是伪代码难读, 排版需要改进, 感觉也不是太有必要包括, 读者不太可能去仔细阅读伪代码.

ACM程序设计(国际大学生程序设计竞赛指南). 曾棕根 编著. 第二版(2011). 内容浅显, 非常适合入门, 推荐给刚刚开始接触程序竞赛的人. 比较有用的是第二章.C++STL泛型编程, 详细介绍了STL.

其它有很多关于真题集的书. 有兴趣有时间可以看. 不然的话, 以上的书打好基础完全够用了.

C++ weblog

刘未鹏 | Mind Hacks

陈硕的Blog
- 对 C++ 历史的个人观点

Monitor url content

if wget -q [url] -O - | grep [keyword regular expression] > /dev/null
then
   sendmail -t < From: from@email.com
To: to@email.com
Subject: your key word appeared
in URL
FOO
fi

Add this script to crontab. 

T-SQL III

1. Examples of using sp_executesql with output parameters.

Two scenarios: 1) execute a query, 2) execute a stored procedure.
See [1] http://support.microsoft.com/kb/262499

-- Example 1.

DECLARE @SQLString NVARCHAR(500)
DECLARE @ParmDefinition NVARCHAR(500)
DECLARE @IntVariable INT
DECLARE @Lastlname varchar(30)
SET @SQLString = N'SELECT @LastlnameOUT = max(lname)
                   FROM pubs.dbo.employee WHERE job_lvl = @level'
SET @ParmDefinition = N'@level tinyint,
                        @LastlnameOUT varchar(30) OUTPUT'
SET @IntVariable = 35
EXECUTE sp_executesql
@SQLString,
@ParmDefinition,
@level = @IntVariable,
@LastlnameOUT=@Lastlname OUTPUT
SELECT @Lastlname

-- Example 2.

CREATE PROCEDURE Myproc
    @parm varchar(10),
    @parm1OUT varchar(30) OUTPUT,
    @parm2OUT varchar(30) OUTPUT
    AS
      SELECT @parm1OUT='parm 1' + @parm
     SELECT @parm2OUT='parm 2' + @parm
GO
DECLARE @SQLString NVARCHAR(500)
DECLARE @ParmDefinition NVARCHAR(500)
DECLARE @parmIN VARCHAR(10)
DECLARE @parmRET1 VARCHAR(30)
DECLARE @parmRET2 VARCHAR(30)
SET @parmIN=' returned'
SET @SQLString=N'EXEC Myproc @parm,
                             @parm1OUT OUTPUT, @parm2OUT OUTPUT'
SET @ParmDefinition=N'@parm varchar(10),
                      @parm1OUT varchar(30) OUTPUT,
                      @parm2OUT varchar(30) OUTPUT'

EXECUTE sp_executesql
    @SQLString,
    @ParmDefinition,
    @parm=@parmIN,
    @parm1OUT=@parmRET1 OUTPUT,@parm2OUT=@parmRET2 OUTPUT

SELECT @parmRET1 AS "parameter 1", @parmRET2 AS "parameter 2"
go
drop procedure Myproc

2. Use FETCH to go through a cycle.

-- Example 3. Note the use of: 1) cursor, 2) fetch, 3) raiserror to print without wait.

DECLARE @tbl varchar(20)
DECLARE c CURSOR FOR SELECT empID FROM test.dbo.Employee
OPEN c

FETCH NEXT FROM c INTO @tbl
WHILE @@FETCH_STATUS = 0
BEGIN
    --print @tbl
    RAISERROR(@tbl, 0, 1) WITH NOWAIT
    FETCH NEXT FROM c INTO @tbl
END

CLOSE c
DEALLOCATE c

T-SQL II

Follow T-SQL I. Now assume some employees make phone calls. How to get the total amount of phone call time of the employees managed by a manager?

Say manager's empID is 1, then it's easy to get:

select SUM(phoneusage) AS PhoneUsage from Employee where mgrID = 1

What if you want the manager's name etc. to be returned on the same row? You could do this:

select A.EmpID, A.ManagerName, B.PhoneUsage FROM
(
    (select ID = 1, EmpID, (firstname + ' ' + lastname) AS ManagerName from Employee where empID = 1) A
    INNER JOIN
    (select ID = 1, SUM(phoneusage) AS PhoneUsage from Employee where mgrID = 1) B
    ON A.ID = B.ID
)

Or, you can first get the phone usage of employees for all the managers:

SELECT A.empID, (A.firstName + ' ' + A.lastName) as [ManagerName], B.phoneUsage FROM
(
    (select mgrID, SUM(phoneUsage) as phoneUsage from Employee group by mgrID) as B
    INNER JOIN Employee A
    ON A.empID = B.mgrID
)

Then you can add "AND A.empID = 1" to get the phone usage of employees managed by manager whose empID is 1:

SELECT A.empID, (A.firstName + ' ' + A.lastName) as [ManagerName], B.phoneUsage FROM
(
    (select mgrID, SUM(phoneUsage) as phoneUsage from Employee group by mgrID) as B
    INNER JOIN Employee A
    ON A.empID = B.mgrID
    AND A.empID = 1
)

The last method is better than the first method, since it does not use an artificial ID.

Parsing expression grammar (PEG)

Parsing expression grammar or PEG is a type of analytic formal grammar. It was first proposed by Bryan Ford in 2004. It is related to the top-down parsing model.

It looks similar to CFG, but different in that it uses "/" instead of "|" to specify the derivation choices of a non-terminal. In doing so it also specifies that the rules delimited by "/" are chosen in the order of appearance. This in effect adds a priority order to the rules involved, and avoids relevant ambiguity. Say in a CFG state you have two rules in shift/reduce or reduce/reduce conflict, which in CFG needs extra priority/precedence specification, now in PEG one just choose the one with high priority. This way it claims that: unlike CFG, PEG cannot be ambiguous.

Any PEG can be parsed in linear time by using a packrat parser.

Advantages of PEG include: no ambiguity; more powerful than regular expressions (this does not sound a very special advantage though, since LL/LR are also more powerful than regular expressions); does not need a separate tokenization step (such as by lex), tokenization rules in PEG can be written the same way as other grammar rules.

Disadvantages of PEG include: large memory consumption; cannot use left-recursion (same as LL); may contain subtle grammar errors and the author needs to tweak the grammar a bit; cannot recognize some unambiguous non-deterministic grammars, for example: S ← 'x' S 'x' | 'x'. Note that LL and LR also cannot recognize this, but CYK algorithm can.

Reference:
[1] http://en.wikipedia.org/wiki/Parsing_expression_grammar

T-SQL I

--
-- This script solves the problem:
-- Given an Employee table, each rows has empID, mgrID, firstName, lastName,
-- return all the managers in hierarchy for a given employee.
-- This is easy, but can also be extended to something of medium complexity.
--
-- This T-SQL script demonostrates:
-- +  create/drop stored procedure
-- +  declare table and variable
-- +  while loop
-- +* assign parameter in dynamically constructed query
-- +  stored procedure returns variable or table
-- + convert data type
-- + execute stored procedure in t-sql
--
-- @execute from command line: sqlcmd -S localhost -d test -i getList.sql
--   -s: server, -d: database, -i: input file
--
-- @Author: HomeTom
-- @Created on: 3/15/2013
-- @Last modified: 3/15/2013
--

--if object_id('dbo.getList') is not null
--    drop procedure dbo.getList
--go

--create procedure getList
--  @ID varchar,
--  @EID int output
--as
begin

SET NOCOUNT ON;

declare @tbl table (
    empID varchar,
    name  varchar(50)
)

declare @empID varchar --= 5
declare @mgrID varchar
declare @name varchar(100)
declare @cond int = 1
declare @query nvarchar(512)

set @empID = 5 --@ID

while @cond = 1
BEGIN
    --print @empID
    -- CONVERT(varchar, @empID)

    IF NOT EXISTS (select empID from Employee WHERE empID = @empID) BREAK

    set @query = 'select @name = firstname + '' '' + lastname from Employee WHERE empID = ' + @empID
    exec sp_executesql @query, N'@name varchar(100) output',  @name = @name output
    insert into @tbl (empID, name) values (@empID, @name)
   
    -- get manager's empID.
    set @query = 'select @empID = mgrID from Employee WHERE empID = ' + @empID
    exec sp_executesql @query, N'@empID varchar output',  @empID = @empID output
    if @empID is null set @cond = 0
END

select * from @tbl

--select @EID = -999

end
go


-------------------
-- execute getList
-------------------

--USE [test]
--GO

--DECLARE    @return_value int,
--        @EID int

--SELECT    @EID = 1

--EXEC    @return_value = [dbo].[getList]
--EXEC    [dbo].[getList]
--        @ID = N'1',
--        @EID = @EID OUTPUT

--SELECT    @EID as N'@EID'
--select @EID

--SELECT    'Return Value' = @return_value

--GO

-------------------
-- Table Employee
-------------------

-- CREATE TABLE [dbo].[Employee](
--     [empID] [int] NOT NULL,
--     [mgrID] [int] NULL,
--     [firstName] [varchar](50) NULL,
--     [lastName] [varchar](50) NULL,
--  CONSTRAINT [PK_Employee] PRIMARY KEY CLUSTERED
-- (
--     [empID] ASC
-- )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
-- ) ON [PRIMARY]