Reasons to study Data Structures & Algorithms
Data structures and algorithms provide essential tools for programmers to abstractly manage real-world data, enhance coding readability, understandability, and maintainability. By mastering these concepts, programmers can improve their problem-solving skills and overall programming efficiency. Considerations such as speed, memory usage, and complexity play crucial roles in selecting the optimal solution. Understanding complexity classes, Big O notation, and practical examples further enhance programming skills. Through exploring various complexity examples and scenarios, programmers can sharpen their algorithmic thinking and decision-making processes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Reasons to study Data Structures & Algorithms Provide abstraction Handling of real-world data storage Programmer s tools Modeling of real-world objects and concepts Programs more readable, understandable, maintainable If you have a good feeling for them, you are a better programmer! You can solve the problem faster Your program works better, with fewer bugs You will know when you have been given an impossible task COSC 2P03 Week 1 1
Considerations Speed Memory usage Complexity of structure Examples of tradeoffs: Insertion speed vs. search speed vs. deletion speed Structure vs. speed Your task as a programmer: think of the tradeoffs and select the best option COSC 2P03 Week 1 2
Complexity Expresses the efficiency of an algorithm Running time expressed as function of problem size Problem size: number of inputs Some complexity classes: Logarithmic Linear Quadratic Exponential COSC 2P03 Week 1 3
Big O notation Function g(n) is O(f(n)) if there are positive constants c and n0such that g(n) c*f(n) for all n n0 Upper bound on its rate of growth Determines algorithm s cost in terms of time to run Note: other measurements exist for lower bound (etc) COSC 2P03 Week 1 4
Complexity Examples 1 and 2 for(i = 0; i < n; i++) { b[i] = a[i]+1; c[i] = a[i]+b[i]; } for(i = 0; i < n; i++) { for(j = 7; j < n; j=j+3) { b[i] = a[i]+1; } c[i] = a[i]+b[i]; } COSC 2P03 Week 1 5
Complexity Example 3 for(i = 0; i < n; i++) { if(a[i] > 0) { for(j = 0; j < n; j++) c[i] = c[i] + b[j]; } else c[i] = b[i]; } Question: what if the outer loop were changed to: for(i = 1; i < n; i=i*2)? COSC 2P03 Week 1 6
Complexity Example 4 int xyz(int n) { if(n <= 1) return 1; else return xyz(n/2) + n; } Question: what if the last statement were changed to return xyz(n-2) + n; ? COSC 2P03 Week 1 7
Complexity Example 5 int bc(int n) { int c; c = 0; while(n > 0) { c = c + (n % 2); n = n / 2; } return c; } COSC 2P03 Week 1 8
Complexity Example 6 int pc(int n) { int i, c; if(n == 1) { return 1; } c = 0; for(i = 0; i < n; i++) { c = c + pc(n-1); } return c; } COSC 2P03 Week 1 9
Table of Computational Complexity If a step takes 0.001 ms and the problem size is N: N=10 N=100 N=1000 Steps Time 10 100 Steps 100 104 106 Time 0.1ms 10ms 1s Steps 1000 106 109 1.07x103013.4x10287 Time 1ms 1s 16.67min f(N) = N f(N) = N2 f(N) = N31000 1.0ms f(N) = 2N1024 1.02ms 1.27x10304.0x1016 0.01ms 0.1ms yrs yrs COSC 2P03 Week 1 10
Comparison: O(n2) vs O(n log n) Assume a machine is running at 300 000 MIPs Assume 1 instruction per iteration. Time to sort 1 billion numbers: Bubble sort O(n2) (109)2 steps / (3x1011steps/sec) 39 days. Quick sort O(n log n) 109 * log2(109) steps / (3x1011 steps/sec) 109 * 30 steps / (3x1011steps/sec) 0.11 seconds. COSC 2P03 Week 1 11
The Rules of Recursion (Weiss, section 1.3) 1. There must be base cases that can be solved without recursion 2. Recursive calls must always make progress towards a base case 3. Assume that all recursive calls work 4. Never duplicate work by solving the same instance of a problem in separate recursive calls COSC 2P03 Week 1 12
Recursive method printOut (Weiss, section 1.3) public static void printOut(int n) { if(n >= 10) printOut(n/10); printDigit(n % 10); } COSC 2P03 Week 1 13
printOut(5034) { if(5034 >= 10) // true printOut(5034 / 10); printDigit(5034 % 10); } Output 4 printOut(503) { if(503 >= 10) // true printOut(503 / 10); printDigit(503 % 10); } 3 printOut(50) { if(50 >= 10) // true printOut(50 / 10); printDigit(50 % 10); } 0 printOut(5) { if(5 >= 10) // false printDigit(5 % 10); } 5 14 COSC 2P03 Week 1
Sequence of calls to determine F5 fib(5) fib(4) fib(3) fib(3) fib(2) fib(2) fib(1) fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) fib(1) fib(0) COSC 2P03 Week 1 15
