Data structures chapter 1(1)

ali48

Download

Post to :

URL :

Related Presentations :

Add to Flag Embed

Views: 867

Category: Science & Tech..

Presentation Description

No description available.

Comments

By: janniceyumul (13 month(s) ago) Private Comment

pls allow me to the download the slides its very interesting....thanks

By: ali48 (13 month(s) ago)

ok. givve me some time. i'll upload it 4shared

Presentation Transcript

Slide 1:

EE 232, Data Structures :

Copyright © Kashif Javed Introduction 1-2 EE 232, Data Structures Text Book: Mark Allen Weiss, “Data Structures and Algorithm Analysis in C” , 2nd Edition, Pearson Education Reference Books: Robert Sedgewick, “Algorithms in C”, 3rd Edition, Pearson Education Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms”, 2nd Edition, McGraw-Hill

Course Overview :

Copyright © Kashif Javed Introduction 1-3 Course Overview A fundamental computer science course Essential for programming Prerequisite for “design and analysis of Algorithms” taught in 6th term A challenging course Intensive programming Intensive (mathematical and logic) thinking

Slide 4:

Prerequisites :

Copyright © Kashif Javed Introduction 1-5 Prerequisites Computer Fundamentals C language programming Functions, Pointers, Arrays , Structures, Recursion Editors, Compilers , Linkers, Debuggers User-level knowledge of Operating Systems Windows Linux Elementary Calculus and Algebra

First some course terminology :

Copyright © Kashif Javed Introduction 1-6 First some course terminology A data structure is a way to store and organize data in order to facilitate access and modifications No single data structure works well for all purposes, so it is important to know the strengths and limitations of several of them

First some course terminology :

Copyright © Kashif Javed Introduction 1-7 First some course terminology An algorithm is a well-defined computational procedure that takes some values, as input and produces some value, or set of values, as output Computing time of an algorithm and the space it requires in the memory determine its efficiency These are bounded resources and therefore should be used wisely

Course Objectives :

Copyright © Kashif Javed Introduction 1-8 Course Objectives This course will help the students To understand the fundamental ways of organizing collections of data to be processed by a program focus is on main-memory data structures To evaluate the efficiency of data structures and their algorithms To define, implement and use Abstract Data Types (ADTs)

Course Outline :

Slide 10:

Chapter 1: Introduction :

Copyright © Kashif Javed Introduction 1-11 Chapter 1: Introduction Our goals: we shall discuss the aims and goals of this course and briefly review programming concepts summarize the basic mathematical background also briefly review recursion

Chapter 1: roadmap :

What's the book about? :

Copyright © Kashif Javed Introduction 1-13 What's the book about? Selection Problem Given a list of N numbers, determine the kth largest, where k  N Algorithm 1 Read N numbers into an array Sort the array in decreasing order by some simple algorithm Return the element in position k

What's the book about?... :

Copyright © Kashif Javed Introduction 1-14 What's the book about?... Algorithm 2 Read the first k elements into an array and sort them in decreasing order Each remaining element is read one by one If smaller than the kth element, then it is ignored Otherwise, it is placed in its correct spot in the array, bumping one element out of the array The element in the kth position is returned as the answer

What's the book about?... :

Copyright © Kashif Javed Introduction 1-15 What's the book about?... Considering large input values such as N = 1million and k = 500,000 , both the algorithms do not terminate in a reasonable amount of time -> impractical A better algorithm can solve this in a second! What should we conclude: Writing a working program is not good enough! When a program is to be run on a large data set, then the running time becomes an issue

What's the book about?... :

Copyright © Kashif Javed Introduction 1-16 What's the book about?... We will learn How to estimate the running time of a program for large inputs How to compare the running times of two programs without actually coding them Techniques for drastically improving the speed of a program Techniques for determining program bottlenecks

Chapter 1: roadmap :

Mathematics review :

Copyright © Kashif Javed Introduction 1-18 Mathematics review Exponents XA•XB = X A+B XA  XB = X A-B (XA) B = X A•B XA + XA = 2•XA  X2•A 2N + 2N = 2•2N = 2N+1 Logarithms All logarithms are to the base 2, unless otherwise specified Definition: XA = B if and only if logX B = A To describe portions of an algorithm and to analyse the performance characteristics of an algorithm

Mathematics review… :

Copyright © Kashif Javed Introduction 1-19 Mathematics review… Properties of logarithms logAB = ; A,B,C > 0 , A  1 log AB = log A + log B ; A, B > 0 log(A/B) = log(A) - log(B) log(AB) = B log(A) log(X) < X for all X > 0 log(1)=0, log(2)=1, log(1,024)=10, log(1,048,576)=20

Mathematics review… :

Copyright © Kashif Javed Introduction 1-22 Mathematics review… Modular Arithmetic The number-theoretical concept of congruence is A  B (mod N) A is congruent to B modulo N , if N divides (A-B) In other words, the remainder is the same if either A or B are divided by N e.g. 81  61  1 (mod 10) Similarly, A+C  B+C (mod N) and AD  BD (mod N)

Mathematics review… :

Copyright © Kashif Javed Introduction 1-23 Mathematics review… Proof By Induction Given a theorem First prove a base case Show the theorem is true for some small value(s) Next assume an inductive hypothesis Assume the theorem is true for all cases up to some limit k Using this assumption, prove that the theorem holds for the next value (k+1) Proving the statements in data structure analysis

Mathematics review… :

Copyright © Kashif Javed Introduction 1-24 Mathematics review… Proof By Induction – example Fibonacci Series F0 = 1, F1 = 1, Fi = Fi-1 + Fi-2 , for i > 1 Show that Fi < (5/3) i , for i  1 Base case: F1 = 1 < 5/3 Inductive Hypothesis: Fi < (5/3) i , for i = 1, 2, ..., k

Mathematics review… :

Copyright © Kashif Javed Introduction 1-25 Mathematics review… Proof By Induction – example… Now prove that Fk+1 < (5/3)k+1 From definition of Fibonacci Series Fk+1 = Fk + Fk-1 Using inductive Hypothesis Fk+1 < (5/3) k + (5/3) k-1 < (3/5)(5/3) k+1 + (3/5)2(5/3) k+1 < (5/3) k+1 [ 3/5 + (3/5)2] < (5/3) k+1 [24/25] < (5/3) k+1

Mathematics review… :

Copyright © Kashif Javed Introduction 1-26 Mathematics review… Proof by Contradiction Assume a theorem is false Show that this assumption implies that some known property is false Hence, the original assumption is erroneous Proof by Contradiction – example “There is an infinite number of prime numbers” Proof: Assume the theorem is false and there is some largest prime Pk

Mathematics review… :

Copyright © Kashif Javed Introduction 1-27 Mathematics review… Proof by Contradiction – example… Let P1, P2, …,Pk be all the primes in the increasing order Consider N = P1P2P3…Pk + 1 Since N > Pk, so N is not a prime However, none of P1, P2, …,Pk divides N exactly, because there will always be a remainder of 1 This is a contradiction, because every number is either a prime or a product of primes Hence the original assumption is false  the theorem is true

Chapter 1: roadmap :

A brief introduction to recursion :

Copyright © Kashif Javed Introduction 1-29 A brief introduction to recursion Recursive function a function that is defined in terms of itself e.g. a factorial function: 6! = 6 * 5 * 4 * 3 * 2 * 1 could be written as: 6! = 6 * 5! In general, we can express the factorial function as follows: n! = n * (n-1)!

A brief introduction to recursion… :

Copyright © Kashif Javed Introduction 1-30 A brief introduction to recursion… The factorial function is only defined for positive integers. So we should be a bit more precise: n! = 1 (if n is equal to 1) n! = n * (n-1)! (if n is larger than 1) The C equivalent of this definition: int fac(int numb){ if(numb <=1) return 1; else return numb * fac(numb-1); } Base Case Recursive Call

A brief introduction to recursion… :

Copyright © Kashif Javed Introduction 1-31 A brief introduction to recursion… Lets find the factorial of 3, that is, numb=3 fac(3) : int fac(int numb){ if(numb<=1) return 1; else return numb * fac(numb-1); } 3 <= 1 ? No fac(3) = 3 * fac(2) fac(2) : 2 <= 1 ? No fac(2) = 2 * fac(1) fac(1) : 1 <= 1 ? Yes return 1 fac(2) = 2 * 1 = 2 return fac(2) fac(3) = 3 * 2 = 6 return fac(3) fac(3) has the value 6

Slide 32:

Copyright © Kashif Javed Introduction 1-32 A brief introduction to recursion… While using recursion, we must be careful not to create an infinite chain of function calls: int fac(int numb){ return numb * fac(numb-1); } or int fac(int numb){ if (numb<=1) return 1; else return numb * fac(numb+1); } Oops! No termination condition Oops!

A brief introduction to recursion… :

Copyright © Kashif Javed Introduction 1-33 A brief introduction to recursion… Two rules for writing correct recursive programs Define a base case A base case can be solved without recursion and it terminates recursion Making progress For cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward the base case

Introduction: Summary :

Copyright © Kashif Javed Introduction 1-34 Introduction: Summary Covered the basics What's the book about? In the mathematical review, Logarithms Arithmetic series Geometric Series Mathematical induction We also have learnt how to write correct recursive programs You now have: Overview of this course