Capítulo 1 - 8%


Sección Tema Subtema Porcentaje del capítulo
1.1 A First Problem: Stable Matching The problem
(p.1-5)		 22%
1.1 A First Problem: Stable Matching Designing the Algorithm (p.5-6) 5%
1.1 A First Problem: Stable Matching Analyzing the Algorithm, Extensions (p.7-12) 45%
1.2 Five Representative Problems 18%
Solved Exercises
(p.19-22)		 11%



Capítulo 2 - 6%


Sección Tema Subtema Porcentaje del capítulo
2.1
 Computational Tractability
18%
2.2
 Asymptotic Order of Growth
30%
2.3
 Implementing the Stable Matching Algorithm Using Lists and Arrays
17%
2.4
 A Survey of Common Running Times
 29%
Solved Exercises
(p.65-67)		 6%


Capítulo 3 - 11%


Sección Tema Subtema Porcentaje del capítulo
3.1
 Basic Definitions and Applications

6%
3.2
 Graph Connectivity and Graph Traversal
22%
3.3
 Implementing Graph TRaversal usinng Qeues and Stacks
31%
3.4
 Testing Bipartiteness: An Application Breadth-First Search
11%
3.5
 Connectivity in Directed Graphs
8%
3.6 DIrected Acyclic Graphs and Topological Ordering
12%
Solved Excercises
(p. 104-107)

10%


Capítulo 4 - 16%


Sección Tema Subtema Porcentaje del capítulo
4.1
 Interval Scheduling: The Greedy Algorithm Stays Ahead
18%
4.2
 Scheduling to MInimize Lateness: An Exchange Argument
15%
4.4
 Shortest Path in a Graph
15%
4.5
 The Minimum Spanning Tree Problem
 21%
4.6
 Implementing Kruskal's Algorithm: The Union-FInd Data Structure
 15%
Solved Exercise 1
(p.183-185)

7%
Solved Exercise 2
(p.185-187)

4%
Solved Exercise 3
(p.187-188)

5%


Capítulo 5 - 10%


Sección Tema Subtema Porcentaje del capítulo
5.1
 A First Recurrence: The Mergesort Algorithm
14%
5.2
 Further Recurrence Relations
25%
5.3
 Counting Inversions
13%
5.4
 Finding the Closest Pair of Points
 28%
5.5
 Integer Multiplication
 8%
Solved Exercise 1
(p.242-244)
6%
Solved Exercise 2
(p.244-246)
5%


Capítulo 13 - 3%


Sección Tema Subtema Porcentaje del capítulo
13.5 Randomized DIvide and Conquer: Median-FInding and Quicksort
 FInding the Median
(p. 727-731 )
51%
13.5
 Randomized DIvide and Conquer: Median-FInding and Quicksort
 Quicksort
(p. 731-734)
 49%
Extra
(Fuera del libro)
 Complejidad de Algoritmos de Ordenamiento
40%


Extra: Complejidad de Algoritmos de Ordenamiento- 2%

Capítulo 6 - 15%


Sección Tema Subtema Porcentaje del capítulo
6.1
 Weighted Interval Scheduling: A Recursive Procedure
13%
6.2
 Principles of Dynamic Programming: Memoization or Iteration over Subproblems
5%
6.3
 Segmented Least Squares: Multi-Way Choices
12%
6.4
 Subset Sums and Knapsacks: Adding a Variable
12%
6.5
 RNA Secondary Structures: Dynamic Programming over Intervals
15%
6.6 Sequence Alignment
 15%
6.8
 Shortest Path in a Graph
(p. 290 - 294)
16%
Solved Excercise 1.
(p. 307-309)

6%
Solved Excercise 2.
(p. 309-311)
7%


Capítulo 7 - 13%


Sección Tema Subtema Porcentaje del capítulo
7.1
 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
36%
7.2 Maximum Flows and Minimum Cuts in a Network
16%
7.3
 Choosing Good Augmenting Paths
16%
7.5
 A First Application: The Bipartite Matching Problem
 32%


Capítulo 8 - 11 %


Sección Tema Subtema Porcentaje del capítulo
8.1
 Polynomial-Time Reduction
29%
8.2 Reductions via "Gadgets": The Satisfiability Problem
17%
8.3
 Efficient Certification and the Definition of NP
14%
8.4
 NP-Complete Problemas
20%


Capítulo 10 y 11 - 5%


Sección Tema Subtema Porcentaje del capítulo
10.1
 Finding Small Vertex Covers
48%
10.2 Solving NP-Hard Problems on Trees
(p. 558-560)
25%
11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem
28%


Última modificación: lunes, 24 de agosto de 2020, 12:37