combinatorial algorithms

Home Up Search


o linear transitor arrays, feasible wiring
introduction: backtracking, tractability, asymptotic bounds, graphs, sperner's lemma, euler trails, lists
PDF(pdf)
o simulation of combinatorial networks
the graph analysis: representations, depth- and breadth-first search, shortest path, bipartiteness, topological sorting, connectivity
PDF(pdf)
o register allocation, track assignment for linear transistor arrays
the greedy paradigm: partial order, conflict graphs, left-edge algorithm, intractability
PDF(pdf)
o minimum cost communication networks
spanning tree algorithms: generic algorithm, implementing the algorithms of Prim and Kruskal, priority queues, disjoint sets
PDF(pdf)
o design rule checking, minimum distance rules
divide and conquer: recurrences, solving recurrences, master theorem, closest points
PDF(pdf)
o technology mapping, application of knapsack
dynamic programming: string matching, principle of optimality, knapsack problems,pseudo-polynomial algorithms, greedy choice versus optimality
PDF(pdf)
o retiming, shortest path algorithms
all-pair shortest paths, difference cont\straints, bellman-ford algorithm, binary search
PDF(pdf)
o np-completeness
(polynomial time) reduction, np-hard problems, np-complete problems, np-completeness proofs
PDF(pdf)
o network flow
max-flow min-cut theorem,ford-fulkerson algorithm,scaling,bipartite matching,disjoint paths,circulations
PDF(pdf)
o an exam with answers
channel routing,wireablesubsets,vertical constraint graphs, NP-hardness, singlesided channels
PDF(pdf)