General
En este curso, se aprenderá a analizar y comprender la complejidad computacional de diferentes algoritmos y estructuras de datos relevantes en las Ciencias de la Computación. Se aprenderá a usar la notación asintótica para acotar la complejidad computacional de problemas y algoritmos fundamentales. Además de los algoritmos tradicionales de búsqueda y ordenamiento, se revisarán algoritmos importantes en la teoría de grafos. Se estudiarán las estrategias generales para diseño de algoritmos como estrategias codiciosas, divide y vencerás y programación dinámica. Se estudiará el conjunto de problemas polinomiales y los no polinomiales. Se planteará la relevancia de la conjetura P=NP. Finalmente, se planteran algunas estrategias para la solución de problemas con complejidad exponencial.

Específicos

1 Introduction:
1.1 Why Algorithms?
1.2 Some Representative Problems
1.3 Class presentation
1.4 A first Problem
2 Getting Started
2.1 Insertion sort
2.2 Analyzing algorithms
2.3 Designing algorithms
3 Growth of Functions
3.1 Asymptotic notation
3.2 Standard notations and common functions
4 Divide-and-Conquer
4.1 The maximum-subarray problem
4.2 Strassen’s algorithm for matrix multiplication
4.3 The substitution method for solving recurrences
5 Probabilistic Analysis and Randomized Algorithms
5.1 The hiring problem
5.2 Indicator random variables
5.3 Randomized algorithms
6 Medians and Order Statistics
6.1 Selection in expected linear time
7 Mergesort and Quicksort
7.1 Mergesort
7.2 Quicksort´s Algorithm
7.3 A randomized version of quicksort
8 Counting and Probability
8.1 Counting
8.2 Probability
8.3 Discrete random variables
8.4 The geometric and binomial distributions
8.5 The tails of the binomial distribution
9 Medians and Order Statistics
9.1 Minimum and maximum
9.2 Selection in expected linear time
9.3 Selection in worst-case linear time
10 Sorting algorithms
10.1 Heaps
10.2 Maintaining the heap property
10.3 Building a heap
10.4 The heapsort algorithm
10.5 Priority queues
10.6 Mergesort
10.7 Quicksort
11 Sorting in Linear Time
11.1 Lower bounds for sorting
11.2 Counting sort
11.3 Radix sort
11.4 Bucket sort
12 Hash Tables
12.1 Direct-address tables
12.2 Hash tables
12.3 Hash functions
13 Amortized Analysis
13.1 Aggregate analysis
13.2 The accounting method
13.3 The potential method
13.4 Dynamic tables
14 Binary Search Trees
14.1 What is a binary search tree?
14.2 Querying a binary search tree
14.3 Insertion and deletion
15 Augmenting Data Structures
15.1 Dynamic order statistics
15.2 How to augment a data structure
15.3 Interval tres
16 Dynamic Programming
16.1 Rod cutting
16.2 Matrix-chain multiplication
16.3 Elements of dynamic programming
16.4 Longest common subsequence
16.5 Optimal binary search trees
17 Greedy Algorithms
17.1 An activity-selection problem
17.2 Elements of the greedy strategy
17.3 Huffman codes
18 Elementary Graph Algorithms
18.1 Representations of graphs
18.2 Breadth-first search
18.3 Depth-first search
18.4 Topological sort
18.5 Strongly connected components
19 Minimum Spanning Trees
19.1 Growing a minimum spanning tree
19.2 Prim´s algorithm
19.3 Kruskal´s algorithm. Union-find data structure.
20 Single-Source Shortest Paths
20.1 The Bellman-Ford algorithm
20.2 Single-source shortest paths in directed acyclic graphs
20.3 Dijkstra´s algorithm
20.4 Difference constraints and shortest paths
20.5 Proofs of shortest-paths properties
21 All-Pairs Shortest Paths
21.1 Shortest paths and matrix multiplication
21.2 The Floyd-Warshall algorithm
21.3 Johnson´s algorithm for sparse graphs
22 Number-Theoretic Algorithms
22.1 Elementary number-theoretic notions
22.2 Greatest common divisor
22.3 Modular arithmetic
22.4 Solving modular linear equations
22.5 The Chinese remainder theorem
22.6 Powers of an element
22.7 The RSA public-key cryptosystem
23 String Matching
23.1 The naive string-matching algorithm
23.2 The Rabin-Karp algorithm
23.3 String matching with finite automata
24 Computational Geometry
24.1 Line-segment properties
24.2 Determining whether any pair of segments intersects
24.3 Finding the closest pair of points
25 NP-Completeness
25.1 Polynomial time
25.2 Polynomial-time verification
25.3 NP-completeness and reducibility
25.4 NP-completeness proofs
25.5 NP-complete problems
26 Combinatorial Optimization
26.1 TSP
26.2 Branch and bound
26.3 Knapsack
26.4 Simulated Annealing
26.5 Meta-heuristics
26.6 Hyper-heuristics
26.7 Ant-colony
26.8 Genetic Algorithms
27 Parallel Computing
27.1 Introduction
27.2 Speedup, Efficiency, Redundancy
27.3 NC-Class
27.4 Models of parallel computing
27.5 PRAM
27.6 Parallel algorithms
27.7 Matrix multiplication
27.8 Parallel prefix-sum
27.9 GPU computing

1. S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, First Edition (McGraw-Hill Education, 2006).
2. Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, New York, NY, USA.
3. R. Sedgewick, K. Wayne, Algorithms (Addison-Wesley Professional, 2011).
4. Aho, A. V., Hopcorft, J. E., and Ullman, J. D. The Design and Analysis of Computer Algorithms. Addisson-Wesley. 1974.
5. Kleinberg, J. and Tardos, E. Algorithm Design, Addisson-Wesley, ISBN 0-321-29535-8, 2006.
6. Lehman, E., Leighton, F. T., and Meyer, A. R., Mathematics for Computer Science. Rev. January 2013.
7. Garey, M. and Johnson, D. S, Computers and untractability: A guide to the theory of NP-completeness. W H Freeman & Co.; ISBN: 0716710455. 1979.
8. Savage, John, E. Models of Computation: Exploring the Power of Computing. Addisson-Wesley. Reading, Mass. 1998. ISBN: 0201895390.

• Conocimientos:
• Habilidades:
• Actitudes y valores: