The document provides an overview of key concepts related to data structures and algorithms including:
1) Data structures are defined by the logical arrangement of data elements and the operations needed to access those elements. Basic data structures include linked lists, stacks, queues, and binary trees.
2) Algorithms are computable sets of steps to achieve a desired result. Algorithms operate on data structures.
3) Functions provide modularity and avoid duplication. Function calls use a stack to store information needed to resume execution after the call is complete. Parameters can be passed by value or reference.
The document provides an overview of key concepts related to data structures and algorithms including:
1) Data structures are defined by the logical arrangement of data elements and the operations needed to access those elements. Basic data structures include linked lists, stacks, queues, and binary trees.
2) Algorithms are computable sets of steps to achieve a desired result. Algorithms operate on data structures.
3) Functions provide modularity and avoid duplication. Function calls use a stack to store information needed to resume execution after the call is complete. Parameters can be passed by value or reference.
The document provides an overview of key concepts related to data structures and algorithms including:
1) Data structures are defined by the logical arrangement of data elements and the operations needed to access those elements. Basic data structures include linked lists, stacks, queues, and binary trees.
2) Algorithms are computable sets of steps to achieve a desired result. Algorithms operate on data structures.
3) Functions provide modularity and avoid duplication. Function calls use a stack to store information needed to resume execution after the call is complete. Parameters can be passed by value or reference.
The document provides an overview of key concepts related to data structures and algorithms including:
1) Data structures are defined by the logical arrangement of data elements and the operations needed to access those elements. Basic data structures include linked lists, stacks, queues, and binary trees.
2) Algorithms are computable sets of steps to achieve a desired result. Algorithms operate on data structures.
3) Functions provide modularity and avoid duplication. Function calls use a stack to store information needed to resume execution after the call is complete. Parameters can be passed by value or reference.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 39
Data Structures & Algorithms
Week1
CHAPTER 1: INTRODUTION
What is Data Structures?
A data structure is defined by
(1) the logical arrangement of data elements, combined with (2) the set of operations we need to access the elements.
Atomic Variables
Atomic variables can only store one value at a time.
int num; float s;
A value stored in an atomic variable cannot be subdivided.
What is Data Structures?
Example:library
is composed of elements (books) Accessing a particular book requires knowledge of the arrangement of the books Users access books only through the librarian
the logical arrangement of data elements, combined with the set of operations we need to access the elements.
Basic Data Structures
Structures include
linked lists Stack, Queue binary trees and others
What is Algorithm?
Algorithm:
A computable set of steps to achieve a desired result Ralationship to Data Structure
Example: Find an element
2 1 3 4 5 6 7
Sumary
CHAPTER 2: FUNCTION & RECURSION
1. FUNCTION 2. THE CONCEPT OF STACK 3. THE SEQUENCE OF EXECUTION DURING A FUNCTION CALL 4. PARAMETER PASSING 5. CALL BY REFERENCE 6. RESOLVING VARIABLE REFERENCES 7. RECURSION 8. STACK OVERHEADS IN RECURSION 9. WRITING A RECURSIVE FUNCTION 10. TYPES OF RECURSION
CHAPTER 2: FUNCTION & RECURSION
1. FUNCTION
provide modularity to the software divide complex tasks into small manageable tasks avoid duplication of work
CHAPTER 2: FUNCTION & RECURSION
2. THE CONCEPT OF STACK
A stack is memory in which values are stored and retrieved in "last in first out" manner by using operations called push and pop.
CHAPTER 2: FUNCTION & RECURSION
3. THE SEQUENCE OF EXECUTION DURING A FUNCTION CALL
When the function is called, the current execution is temporarily stopped and the control goes to the called function. After the call, the execution resumes from the point at which the execution is stopped. To get the exact point at which execution is resumed, the address of the next instruction is stored in the stack. When the function call completes, the address at the top of the stack is taken.
CHAPTER 2: FUNCTION & RECURSION
3. THE SEQUENCE OF EXECUTION DURING A FUNCTION CALL
Functions or sub-programs are implemented using a stack. When a function is called, the address of the next instruction is pushed into the stack. When the function is finished, the address for execution is taken by using the pop operation.
CHAPTER 2: FUNCTION & RECURSION
3. THE SEQUENCE OF EXECUTION DURING A FUNCTION CALL Result:?
CHAPTER 2: FUNCTION & RECURSION
4. PARAMETER * REFERENCE PASSING
passing by value
the value before and after the call remains the same changed value after the function completes
passing by reference
CHAPTER 2: FUNCTION & RECURSION
6. RESOLVING VARIABLE REFERENCES
When a variable can be resolved by using multiple references, the local definition is given more preference
CHAPTER 2: FUNCTION & RECURSION
7. RECURSION
A method of programming whereby a function directly or indirectly calls itself Problems: stop recursion?
CHAPTER 2: FUNCTION & RECURSION
7. RECURSION
CHAPTER 2: FUNCTION & RECURSION
7. RECURSION: Hanoi tower
CHAPTER 2: FUNCTION & RECURSION
7. RECURSION
CHAPTER 2: FUNCTION & RECURSION
8. STACK OVERHEADS IN RECURSION
two important results: the depth of recursion and the stack overheads in recursion
CHAPTER 2: FUNCTION & RECURSION
9. WRITING A RECURSIVE FUNCTION
Recursion enables us to write a program in a natural way. The speed of a recursive program is slower because of stack overheads. In a recursive program you have to specify recursive conditions, terminating conditions, and recursive expressions.
only makes a single call to itself each time the function runs
CHAPTER 2: FUNCTION & RECURSION
10. TYPES OF RECURSION
TAIL RECURSION
Tail recursion is a form of linear recursion. In tail recursion, the recursive call is the last thing the function does. Often, the value of the recursive call is returned.
CHAPTER 2: FUNCTION & RECURSION
10. TYPES OF RECURSION
BINARY RECURSION
Some recursive functions don't just have one call to themself, they have two (or more).
CHAPTER 2: FUNCTION & RECURSION
10. TYPES OF RECURSION
EXPONENTIAL RECURSION
An exponential recursive function is one that, if you were to draw out a representation of all the function calls, would have an exponential number of calls in relation to the size of the data set (exponential meaning if there were n elements, there would be O(an) function calls where a is a positive number)
CHAPTER 2: FUNCTION & RECURSION
10. TYPES OF RECURSION
EXPONENTIAL RECURSION
CHAPTER 2: FUNCTION & RECURSION
10. TYPES OF RECURSION
NESTED RECURSION
In nested recursion, one of the arguments to the recursive function is the recursive function itself These functions tend to grow extremely fast.
CHAPTER 2: FUNCTION & RECURSION
10. TYPES OF RECURSION
MUTUAL RECURSION
A recursive function doesn't necessarily need to call itself. Some recursive functions work in pairs or even larger groups. For example, function A calls function B which calls function C which in turn calls function A.
CHAPTER 2: FUNCTION & RECURSION
10. TYPES OF RECURSION
MUTUAL RECURSION
Exercises : Recursion
Recursion Exercise (1)
Write a program to compute: S = 1 + 2 + 3 + n using recursion.
Recursion Exercise (2)
Write a program to print a revert number Example: input n=12345. Print out: 54321.
Recursion Exercise (4)
Write a recursion function to find the sum of every number in a int number. Example: n=1980 => Sum=1+9+8+0=18.
Python Advanced Programming: The Guide to Learn Python Programming. Reference with Exercises and Samples About Dynamical Programming, Multithreading, Multiprocessing, Debugging, Testing and More
Python Advanced Programming: The Guide to Learn Python Programming. Reference with Exercises and Samples About Dynamical Programming, Multithreading, Multiprocessing, Debugging, Testing and More
