TAILIEUCHUNG - Lecture Algorithms and data structures: Chapter 3 - Recursion

This chapter will provide a brief overview of C++. In this topic we will see: The similarities between C# and C++; some differences (including global variables and functions; the preprocessor, compilation, namespaces; printing), concluding with classes, templates, pointers memory allocation and deallocation. | Review Introduction to Searching External and Internal Searching Types of Searching Linear or sequential search Binary Search Algorithms for Linear Search Algorithms for Binary Search 1 Recursion 2 Introduction to Recursion Recursive Definition Recursive Algorithms Finding a Recursive Solution Example Recursive Function Recursive Programming Rules for Recursive Function Example Tower of Hanoi Other examples Introduction Any function can call another function A function can even call itself When a function call itself, it is making a recursive call Recursive Call A function call in which the function being called is the same as the one making the call Recursion is a powerful technique that can be used in place of iteration(looping) Recursion Recursion is a programming technique in which functions call themselves. 3 3 Recursive Definition 4 A definition in which something is defined in terms of smaller versions of itself. To do recursion we should know the followings Base Case: The case for which the solution can be stated non-recursively The case for which the answer is explicitly known. General Case: The case for which the solution is expressed in smaller version of itself. Also known as recursive case Recursive Algorithm 5 Definition An algorithm that calls itself Approach Solve small problem directly Simplify large problem into 1 or more smaller sub problem(s) & solve recursively Calculate solution from solution(s) for sub problem Finding a Recursive Solution 6 a recursive solution to a problem must be written carefully the idea is for each successive recursive call to bring you one step closer to a situation in which the problem can easily be solved this easily solved situation is called the base case each recursive algorithm must have at least one base case, as well as a general (recursive) case Example 1 7 We can write a function called power that calculates the result of raising an integer to a positive power. If X is an integer and N is a positive integer, .

• Cơ sở dữ liệu
• Algorithm analysis
• Graph algorithms
• Design techniques
• Data structures
• Lecture Algorithms and data structures
• Algorithm analysis
• Design techniques
• Cấu trúc dữ liệu
• Algorithm analysis in C++
• 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
• Analysis of Algorithm
• Incorrect algorithms
• Analyzing an algorithm
• nalyzing an algorithm
• The correct output
• Communication bandwidth
• Computational time
• 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