리얼월드 알고리즘

1장 주가 스팬
1.1 알고리즘
1.2 실행 시간과 복잡도
1.3 스택을 사용하는 주가 스팬

2장 미로 탐색
2.1 그래프
2.2 그래프 표현
2.3 깊이 우선 탐색
2.4 너비 우선 탐색

3장 압축
3.1 압축
3.2 트리와 우선순위 큐
3.3 허프만 코딩
3.4 LZW 압축

4장 암호
4.1 복호화 문제
4.2 일회성 패드
4.3 AES 암호
4.4 디피-헬먼 키 교환
4.5 빠른 모듈러 거듭제곱

5장 암호 분리
5.1 공개키 암호화
5.2 RSA 암호 체계
5.3 메시지 해싱
5.4 인터넷 트래픽 익명화

6장 작업 순서
6.1 위상 정렬
6.2 가중치 그래프
6.3 임계 경로

7장 행, 문단, 경로
7.1 최단 경로
7.2 데이크스트라 알고리즘

8장 라우팅과 중개
8.1 인터넷 라우팅
8.2 벨만-포드(-무어) 알고리즘
8.3 음의 가중치와 순환
8.4 차익 거래

9장 무엇이 가장 중요한가
9.1 페이지랭크
9.2 하이퍼링크 행렬
9.3 누승법
9.4 구글 행렬

10장 투표 우열 측정
10.1 선거 제도
10.2 슐츠 방법
10.3 플로이드-워셜 알고리즘

11장 무차별 대입 검색과 비서 문제 그리고 양분
11.1 순차 검색
11.2 매칭, 비교, 레코드, 키
11.3 마태 효과와 멱 법칙
11.4 자기 조직화 검색
11.5 비서 문제
11.6 이진 검색
11.7 컴퓨터에서의 정수 표현
11.8 이진 검색으로 되돌아가서
11.9 비교 트리

12장 다양한 정렬 알고리즘
12.1 선택 정렬
12.2 삽입 정렬
12.3 힙 정렬
12.4 병합 정렬
12.5 퀵 정렬
12.6 무엇을 선택할까

13장 검색: 휴대품 보관소, 비둘기, 버킷
13.1 키 값 매핑
13.2 해싱
13.3 해시 함수
13.4 부동 소수점과 해싱
13.5 충돌
13.6 디지털 지문
13.7 블룸 필터

14장 비트와 트리
14.1 통신 문제로서의 점(占)
14.2 정보와 엔트로피
14.3 분류
14.4 결정 트리
14.5 속성 선택
14.6 ID3 알고리즘
14.7 기초 장치
14.8 오컴의 면도날
14.9 비용, 문제, 개선

15장 문자열 처리
15.1 무차별 대입 문자열 매칭
15.2 크누스-모리스-프랫 알고리즘
15.3 보이어-무어-호스풀 알고리즘

16장 운에 맡기기
16.1 난수
16.2 무작위 표본 추출
16.3 파워 게임
16.4 소수 찾기

미로 탐색은 오래된 문제다. 이 문제의 시작은 크레타의 미노스 왕이 전쟁에서 진 아테네 왕에게 7년마다 남녀 각각 7명을 크레타로 보내게 한 이야기로 거슬러 올라간다. 크레타로 온 남녀는 사람의 몸과 황소의 머리를 한 괴물인 미노타우로스가 사는 미궁에 던져졌다. 이 미궁은 매우 복잡한 미로여서 불운한 희생자들은 미노타우로스에게 잡아 먹힐 운명이었다. 세 번째로 공물을 바칠 때가 되자 아테네의 테세우스가 자원했다. 테세우스가 크레타섬에 도착했을 때 미노스 왕의 딸 아리아드네는 그에게 반해서 그를 돕기 위해 실뭉치를 주었다. 테세우스는 미궁에 들어가 미노타우로스를 발견하고 죽인 후 실을 사용하여 출구를 찾아냈다.

차익 거래 프로그램은 교환하고 사고팔 수 있는 상품 집합을 포함한다. 그러한 상품을 예로 들면 구리, 납, 아연 같은 산업용 금속과 유로, 달러 같은 통화 또는 시장에서 거래되는 많은 것이 포함될 수 있다. 차익 거래는 시장 간 가격 차이로 이윤을 만드는 장점이 있다. 간단한 예로, 런던에서 유로와 달러 사이의 환율이 1유로당 1.37달러(€1 = $1.37)지만, 뉴욕에서는 1달러는 0.74유로($1 = €0.74)라고 해 보자. 그러면 거래자는 런던에서 1,000,000유로(€1,000,000)로 총 1,370,000달러($1,370,000)를 사서 이를 뉴욕으로 보내 다시 유로를 살 수 있다. 거래자는 결국 1,370,000달러로 1,013,800유로를 사서($1,370,000 × 0.74 = €1,013,800) 13,800유로라는 위험 부담 없는 깔끔한 이익을 얻게 된다.

한 회사에서 직원들에게 매일 점심을 제공하려고 업체를 선정한다고 해 보자. 얼마간의 시장 조사 후에 회사에서는 품질과 가격 조건을 충족하는 업체 3곳을 찾았다. 그러나 업체들이 제공하는 서비스에는 제약이 있었다. 첫 번째 업체는 파스타를 곁들인 고기 메뉴를 주로 제공하고, 두 번째 업체는 고기에서 채식 요리까지 다양한 메뉴를 제공하며, 세 번째 업체는 엄격히 채식 메뉴만을 제공한다.