Reading Materials
IRIS H.-R. JIANG
DEE3504
ALGORITHMS
Iris Hui-Ru Jiang
Fall 2014
Introduction
Administrative Matters
Course Objectives
IRIS H.-R. JIANG
Time/location: 1CD3A@SC204
Instructor: Iris Hui-Ru Jiang
Email: huiru.jiang@gmail.com
Office: ED540, ext. 31211
Office hours: 1X (made by appointment)
Teaching assistants:
Email: nctuee.alg@gmail.com
Lab: ED413, ext. 54226
Office hours: 2EF
Prerequisite: two out of the following courses
Data structures
Discrete mathematics
Computer programming in C
Computer programming in C++
Introduction
Course webpage:
e3, NCTU open course ware
Required text:
Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2006
n Jon Kleinberg, 20 Best Brains under 40, Discover Magazine,
2008
n Cornell
Reference:
S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms,
McGraw-Hill, 2007
n UC Berkeley
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd
Ed., McGraw Hill/MIT Press, 2009
n Bible! MIT
IRIS H.-R. JIANG
Study unifying principles and concepts of algorithm design
Algorithmic problems form the heart of computer science
Polish your critical thinking and problem-solving technique
Algorithmic problems tend to come bundled together with lots of
messy, application-specific detail, some of it essential, some of it
extraneous
Two fundamental components
n Get to the mathematically clean core of a problem
n Identify the appropriate algorithm design techniques based on
the structure of the problem
Intended audience:
Who are interested in computer science
Who are computing something
Who are learning problem-solving techniques
Introduction
Course Content (1/3)
Course Content (3/3)
IRIS H.-R. JIANG
Introduction
An opening problem: stable marriages
Range of problems we will consider
Background:
Basics of algorithm analysis
Graphs
General algorithmic techniques
Greedy algorithms
n Finding optimal solutions with greedy methods
n Scheduling time intervals
n The minimum spanning tree problem
The divide and conquer method
n Some basic primitives in computational geometry
Introduction
*The details are subject to change
Dynamic programming with many applications
n Weighted interval scheduling
n Knapsack problems
n Shortest paths
n Sequence alignment
n Including efficient implementation via divide and conquer
Flows and cuts in networks
n The basic flow and cut problems
n Basic methods: augmenting paths
n Application to matching
n Polynomial time methods
n Extensions to more general models
n Applications to resource allocation, sequencing, and
segmentation
Introduction
*The details are subject to change
Course Content (Optional)
IRIS H.-R. JIANG
Computational Intractability (Optional)
NP-completeness
n Hardness of problems in optimization and constraint
satisfaction
n How to show NP-completeness: reducibility
n Examples including the traveling salesman problem, 3dimensional matching, covering, packing, partitioning
problems, and subset sum
PSPACE completeness
n Hardness of problems in artificial intelligence and gameplaying
Introduction
Course Content (2/3)
6
IRIS H.-R. JIANG
*The details are subject to change
IRIS H.-R. JIANG
Algorithms for hard problems
Improved exponential methods
Approximation algorithms
n greedy algorithms (load balancing, facility location)
n The application of linear programming
Local search techniques
n The Metropolis Algorithm
n Simulated annealing
n Applications to graph partitioning and neural networks
Randomized algorithms
Including contention-resolution protocols and satisfiability
heuristics
Algorithms that run forever
Introduction
*The details are subject to change
Grading Policy
IRIS H.-R. JIANG
Grading:
Homework: 15%
Programming: (two mini-projects: 10% + project: 25%)
Exams: (Midterm: 25% + Final: 25%)
Homework & programming:
Discussions are encouraged. However, solutions should be
written individually and separately (no credits for plagiarism)
No late submission (partial solutions may get partial credits)
Homework is usually due in two weeks
Programming assignments are usually due in two or three weeks
Exams
No discussions, solutions should be written individually
Introduction
What is an Algorithm?
Problem-solving
procedure
IRIS H.-R. JIANG
10
Definition: An algorithm is
A finite, definite, effective procedure, with some output
[Donald Knuth, 1968]
Input: may have
problem
solution
Output: must have
Definiteness: must be clear and unambiguous
Finiteness: terminate after a finite number of steps
Effectiveness: must be basic and feasible with pencil and paper
Procedure: the sequence of specific steps in a logical order
Cf. An algorithm is
A well-defined procedure for transforming some input to a desired
output [Cormen et al. Introduction to Algorithms, 2nd Ed.]
Introduction
