TAILIEUCHUNG - Analysis of Algorithm

Analysis of Algorithm we only analyze correct algorithms, Incorrect algorithms (Might not halt at all on some input instances, Might halt with other than the desired answer), Analyzing an algorithm (Predicting the resources that the algorithm requires, Resources include). | Nguyen Viet Anh - CS3329 Spring 2011 Algorithm Analysis We only analyze correct algorithms An algorithm is correct If, for every input instance, it halts with the correct output Incorrect algorithms Might not halt at all on some input instances Might halt with other than the desired answer Analyzing an algorithm Predicting the resources that the algorithm requires Resources include Memory Communication bandwidth Computational time (usually most important) Nguyen Viet Anh - CS3329 Spring 2011 Algorithm Analysis Factors affecting the running time computer compiler algorithm used input to the algorithm The content of the input affects the running time typically, the input size (number of items in the input) is the main consideration . sorting problem the number of items to be sorted . multiply two matrices together the total number of elements in the two matrices Machine model assumed Instructions are executed one after another, with no concurrent operations Not parallel computers Nguyen Viet Anh - CS3329 Spring 2011 Example Calculate N i3 i 1 1 1 2 2N+2 3 4N 4 1 Lines 1 and 4 count for one unit each Line 3: executed N times, each time four units Line 2: (1 for initialization, N+1 for all the tests, N for all the increments) total 2N + 2 total cost: 6N + 4 O(N) Nguyen Viet Anh - CS3329 Spring 2011 Worst- / average- / best-case Worst-case running time of an algorithm The longest running time for any input of size n An upper bound on the running time for any input guarantee that the algorithm will never take longer Example: Sort a set of numbers in increasing order; and the data is in decreasing order The worst case can occur fairly often . in searching a database for a particular piece of information Best-case running time sort a set of numbers in increasing order; and the data is already in increasing order Average-case running .

• Cơ sở dữ liệu
• Analysis of Algorithm
• Incorrect algorithms
• Analyzing an algorithm
• nalyzing an algorithm
• The correct output
• Communication bandwidth
• Computational time
• Data structures
• Algorithm analysis in C++
• Algorithm analysis
• The disjoint sets class
• Algorithm design techniques
• Amortized analysis
• Advanced data structures
• Advanced Algorithms Analysis and Design
• Lecture Advanced Algorithms Analysis and Design
• Bài giảng Phân tích và thiết kế thuật toán nâng cao
• The Floyd Warshall algorithm
• Johnson’s algorithm
• Bellman Ford algorithm
• Algorithm design
• Lecture Algorithm design
• Computational tractability
• Asymptotic order of growth
• Polynomial running time
• Dynamic programming
• Hirschbergs algorithm
• Greedy Algorithms
• Dijkstras algorithm
• Minimum spanning trees
• Network flow
• Ford Fulkerson algorithm
• Max flow min cut theorem
• Analysis in C++
• A general overview
• Extendible hashing
• Hash tables in the standard library
• Performance analysis of a sugar plant using genetic algorithm
• Optimization of crystallization system of a sugar plant using genetic algorithm
• A sugar plant using genetic algorithm
• Refining system fails
• The crystallization system includes crystallization units
• Local search
• Gradient descent
• Metropolis algorithm
• A practical introduction
• Mathematical preliminaries
• Binary trees
• Non binary trees
• Internal sorting
• Graph search
• Graph connectivity
• Graph traversal
• Coin changing
• Optimal caching
• Counting inversions
• Closest pair of points
• Randomized quicksort
• Master theorem
• Integer multiplication
• Matrix multiplication
• Weighted interval scheduling
• Knapsack problem
• Bipartite matching
• Disjoint paths
• Assignment problem
• Input queued switching
• Poly time reductions
• Constraint satisfaction problems
• Graph coloring
• Decision problems
• NP complete
• Nondeterministic polynomial
• PSPACE complexity class
• Quantified satisfiability
• PSPACE complete
• Vertex covers
• Bipartite graphs
• Limits of tractability
• Approximation Algorithms
• Vertex cover
• Randomized Algorithms
• Contention resolution
• Linearity of expectation
• Performance analysis of a real time adaptive prediction algorithm
• Real time adaptive prediction algorithm for traffic congestion
• Lower Mean Square Error
• The actual traffic congestion states