Unit CL: Basic Counting and Listing
Section 1: Lists with Repetitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .CL-1
set, list, multiset, sequence, word, permutation, k-set, k-list, k-multiset, k-lists
with repetition, rule of product, Cartesian product, lexicographic order (lex order),
dictionary order, rule of sum, composition of a positive integer
Section 2: Lists Without Repetition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CL-9
k-lists without repetition, Stirling’s formula for approximating n!, circular arrange-
ments, words from a collection of letters
Section 3: Sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .CL-13
set intersection, set union, set difference, set complement, symmetric difference, set
product (Cartesian product), binomial coefficients, generating functions, binomial
theorem, full house (card hand), two pairs (card hand), rearranging words, multino-
mial coefficients, card hands and multinomial coefficients, recursions, set partitions,
Stirling numbers of the second kind (S(n, k)), straight (card hand), Bell numbers
B n
Section 4: Probability and Basic Counting. . . . . . . . . . . . . . . . . . . . . . . . . .CL-28
sample space, selections done uniformly at random, event, probability function,
combining events, Venn diagrams, odds, hypergeometric probabilities, fair dice,
geometric probability, principle of inclusion exclusion, birthday problem
Multiple Choice Questions for Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CL-41
Unit Fn: Functions
Section 1: Some Basic Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fn-1
direct product, intersection, union, symmetric difference, domain, range, codomain,
one-line notation, surjection, onto, injection, one-to-one, bijection, permutation,
relation, functional relation, two-line notation
Section 2: Permutations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Fn-7
composition, cycle, cycle form of permutation, involution, permutation matrices,
derangements
Section 3: Other Combinatorial Aspects of Functions. . . . . . . . . . . . . .Fn-14
image, inverse image, coimage, image size and Stirling numbers, strictly increasing,
strictly decreasing, weakly increasing, weakly decreasing, monotone, multisets, lists
without repetition, restricted growth functions and partitions
Section 4: Functions and Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fn-21
random variable, probability function, event, probability distribution function, ex-
pectation, covariance, variance, standard deviation, correlation, independent events,
independent random variables, product spaces, generating random permutations,
joint distribution function, marginal distributions, binomial distribution, Poisson
distribution, normal distribution, standard normal distribution, cumulative distri-
bution, central limit theorem, normal approximation to binomial, Poisson approx-
imation to binomial, Tchebycheff’s inequality
Multiple Choice Questions for Review. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Fn-41
Unit DT: Decision Trees and Recursion
Section 1: Basic Concepts of Decision Trees. . . . . . . . . . . . . . . . . . . . . . . . . DT-1
decision trees, vertices, root, edges, degree of vertex, down degree, child, parent,
leaves, internal vertex, height of leaf, path to vertex, traversals of decision tree,
depth first vertices, depth first edges, breadth first, preorder, postorder, length-
first lex order, dictionary order, permutations in lex order, partial permutation,
rank of leaf, direct insertion order for permutations, backtracking, Latin squares,
domino coverings, strictly decreasing functions, unlabeled balls into boxes, isomorph
rejection
Section 2: Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DT-15
recursive algorithm, simplest case reduction, recursive algorithm for 0-1 sequences,
sorting by recursive merging, recursive approach, recursive solutions, local descrip-
tion for permutations in lex order, recursive description of Towers of Hanoi, decision
tree for Towers of Hanoi, recursion and stacks, configuration analysis of Towers of
Hanoi, abandoned leaves and RANK, characteristic functions and subsets, Gray
code for subsets, decision tree for Gray code for subsets, local description of Gray
code, Towers of Hanoi with four poles
Section 3: Decision Trees and Conditional Probability . . . . . . . . . . . . DT-27
conditional probability, independent events, Venn diagrams, probabilities of leaves,
probabilities of edges, probabilistic decision trees, decision trees and Bayesian meth-
ods, Bayes’ theorem, multiplication theorem for conditional probabilities, sequen-
tial sampling, the SAT problem, first moment method, tournaments, gambler’s ruin
problem
Section 4: Inductive Proofs and Recursive Equations . . . . . . . . . . . . . DT-40
induction, recursive equations, induction hypothesis, inductive step, base case,
prime factorization, sum of first n integers, local description, recurrence relation,
binomial coefficients C(n, k), Stirling numbers S(n, k), guessing solutions to recur-
rences, linear two term recurrence, constant coefficients, characteristic equation,
two real roots, one real root, complex roots, recursion for derangements, Fibonacci
recurrence relation, recurrence relation for derangements
Multiple Choice Questions for Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DT-52
Unit GT: Basic Concepts in Graph Theory
Section 1: What is a Graph?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GT-1
computer network example, simple graph, graph, vertices, edges, set theoretic de-
scription of graph, pictorial description of a graph, incidence function, vertices
joined by an edge, adjacent vertices, edge incident on a vertex, simple graphs are
graphs, form of a graph, equivalence relations, equivalence classes, blocks, binary
relations, reflexive, symmetric, transitive, equivalent forms, isomorphism of graphs,
graph isomorphism as an equivalence relation, degree of a vertex, loops, parallel
edges, isolated vertices, degree sequences and isomorphism, random graphs
Section 2: Digraphs, Paths, and Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . GT-13
flow of commodities, directed graph, digraph, simple digraph, simple graphs as
simple digraphs, directed loops, digraphs and binary relations, symmetric binary
relations and simple graphs with loops, complete simple graphs, path, trail, walk,
vertex sequence, walk implies path, restrictions of incidence functions, subgraphs,
subgraph induced by edges, subgraph induced by vertices, cycles, connected graphs,
connected components and equivalence classes, connectivity in digraphs, Eulerian
trail, Eulerian circuit, Hamiltonian cycle, Hamiltonian graph, bicomponents of
graphs, bipartite graphs, oriented simple graphs, antisymmetry, order relations,
Hasse diagrams, covering relations, counting trees
Section 3: Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . GT-24
tree, alternative definitions of a tree, rooted graph, rooted tree, parent, child,
sibling, leaf, internal vertices, unique paths in trees, rooted plane tree, RP-tree,
traversing RP-trees, depth first sequences, breadth first sequences, spanning trees,
minimum spanning trees, greedy algorithms, Prim’s algorithm, Kruskal’s algorithm,
lineal or depth-first spanning trees, algorithm for depth-first spanning trees, bipar-
tite graphs and depth first spanning trees, degree sequences of trees, binary trees,
full binary trees, height and leaf restrictions in binary trees
Section 4: Rates of Growth and Analysis of Algorithms . . . . . . . . . . GT-37
comparing algorithms, machine independence, example of finding the maximum, Θ
notation, O notation, properties of Θ and O, Θ as an equivalence relation, suffi-
ciently large, eventually positive, asymptotic, “little oh” notation, using Θ to com-
pare polynomial evaluation algorithms, average running time, tractable, intractable,
graph coloring problem, traveling salesman problem, clique problem, NP-complete
problems, NP-hard, NP-easy, chromatic number of a graph, almost good algo-
rithms, almost correct algorithms, close algorithms, polynomial time, exponential
time, Θ and series, Θ and logs
Multiple Choice Questions for Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GT-51
Solutions to Exerciseshttp://www.blogger.com/img/blank.gif
Notation Index
Subject Index
Another Algorithms Books
Another The Core of CS Books
Download
No comments:
Post a Comment