1.pdf

Algorithms and Data Structures This course is about the basic fundamental data structures and algorithms which form the basis of large complex software systems. This course builds an understanding of the storage mechanisms of computers...

Algorithms and Data Structures This course is about the basic fundamental data structures and algorithms which form the basis of large complex software systems. This course builds an understanding of the storage mechanisms of computers and how to manipulate storage in order to create efficient programs. This knowledge is used to guide the selection of an appropriate structure for a complex system. Dr. Mohmed Osman Hegazi Lecture 1 1  Aims and Objectives: This course will build an understanding of how the architecture of a computer impacts on the construction of programs and how data structures and algorithms can be constructed to efficiently perform desired functionality. The goal of this course is to build enough understanding of data structures and associated algorithms. The students should develop an understanding of: Actual computer data structures and how they impact on computer programs; Fundamental algorithms and data structures; Standard algorithms and data structures including their time and space requirements; It is expected that upon successful completion of the course, students will be able to select and implement an appropriate set of algorithms and data structures for standard problems. Dr. Mohmed Osman Hegazi Lecture 1 2  Definitions ◼ Algorithm a well-defined computational procedure that takes some value, or a set of values, as input and produces some value, or a set of values, as output. ◼ Algorithm sequence of computational steps that transform the input into the output. ◼ Data Structure a way to store and organize data to facilitate access and modifications. ◼ Implementation a way to realize the desired functionality ◼ how is the data stored (array, linked list, …) ◼ which algorithms implement the operations  Course contains and outlines This course contains 5 Units: 1- Unit 1: introduction to C- Language and algorithms. 2- Unit 2: Stack. 3- Unit 3: Queue. 4- Unit 4: Linked List. 5- Unit 5: Trees Dr. Mohmed Osman Hegazi Lecture 1 4 UNIT 1: Introduction to C- Language & Algorithms Objectives: The objectives of this unit is to understanding the algorithms through C- Language. To know how the computer solving the problems, how data elements are computationally represented , and to be familiar on sorting & the searching algorithms. Topics Basics of C-Language Variable in C. Input & Output in C. Function in C. Arrays in C. Sorting algorithms. Searching Algorithms. Pointer in C. Structures in C.  A Simple C Program Header file (preprocessor #include directive command int main ( void ) { The main function printf ( “Hello, World!\n” ) ; (C program) return 0 ; } Void means nothing (that means function main has no parameter) The type of return value – last line return 0 value Program statement ended with ; printf C function for output. Return its for the function return value  Anatomy of a C Program program header comment int main ( void ) { statement(s) return 0 ; } Program Header Comment ◼ A comment is descriptive text used to help a reader of the program understand its content. ◼ All comments must begin with the characters ◼ These are called comment delimiters  Preprocessor Directives ◼ Lines that begin with a # in column 1 are called preprocessor directives (commands). ◼ Example: the #include directive causes the preprocessor to include a copy of the standard input/output header file stdio.h at this point in the code. ◼ This header file was included because it contains information about the printf ( ) function that is used in this program. stdio.h ◼ When we write our programs, there are libraries of functions to help us so that we do not have to write the same code over and over. ◼ Some of the functions are very complex and long. Not having to write them ourselves make it easier and faster to write programs. ◼ Using the functions will also make it easier to learn to program!  int main ( void ) ◼ Every program must have a function called main. This is where program execution begins. ◼ main() is placed in the source code file as the first function for readability. There must be a function with this name or gcc can not successful compile and link your program. ◼ The reserved word “int” indicates that main() returns an integer value. ◼ The parentheses following the reserved word “main” indicate that it is a function. ◼ The reserved word “void” means nothing is there.  The Function Body ◼ A left brace (curly bracket) -- { -- begins the body of every function. A corresponding right brace -- } -- ends the function body. ◼ The style is to place these braces on separate lines in column 1 and to indent the entire function body 3 to 5 spaces.  printf (“Hello, World!\n”) ; ◼ This line is a C statement. ◼ It is a call to the function printf ( ) with a single argument (parameter), namely the string “Hello, World!\n”. ◼ Even though a string may contain many characters, the string itself should be thought of as a single quantity. ◼ Notice that this line ends with a semicolon. All statements in C end with a semicolon.  return 0 ; ◼ Because function main() returns an integer value, there must be a statement that indicates what this value is. ◼ The statement return 0 ; indicates that main() returns a value of zero to the operating system. ◼ A value of 0 indicates that the program successfully terminated execution. ◼ Do not worry about this concept now. Just remember to use the statement. Another C Program #include int main( void ) { int value1, value2, product ; printf(“Enter two integer values: “) ; scanf(“%d%d”, &value1, &value2) ; product = value1 * value2 ; printf(“Product = %d\n”, product) ; return 0 ; }  Tokens ◼ The smallest element in the C language is the token. ◼ It may be a single character or a sequence of characters to form a single item. Tokens are: ◼ Tokens can be: ◼ Numeric constants ◼ Character constants ◼ String constants ◼ Keywords ◼ Names (identifiers) ◼ Punctuation ◼ Operators Numeric Constants ◼ Numeric constants are an uninterrupted sequence of digits (and may contain a period). They never contain a comma. ◼ Examples: ◼ 123 ◼ 98.6 ◼ 1000000 Character Constants ◼ Singular! ◼ One character defined character set. ◼ Surrounded on the single quotation mark. ◼ Examples: ◼ ‘A’ ◼ ‘a’ ◼ ‘$’ ◼ ‘4’ String Constants ◼ A sequence characters surrounded by double quotation marks. ◼ Considered a single item. ◼ Examples: ◼ “UMBC” ◼ “I like ice cream.” ◼ “123” ◼ “CAR” ◼ “car” Keywords ◼ Sometimes called reserved words. ◼ Are defined as a part of the C language. ◼ Can not be used for anything else! ◼ Examples: ◼ int ◼ while ◼ for Names ◼ Sometimes called identifiers or labels. ◼ Can be of anything length, but on the first 31 are significant (too long is as bad as too short). ◼ Are case sensitive: ◼ abc is different from ABC ◼ Must begin with a letter and the rest can be letters, digits, and underscores. ◼ Must follow the standards for this course! Punctuation ◼ Semicolons, colons, commas, apostrophes, quotation marks, braces, brackets, and parentheses. ◼; : , ‘ “ [ ] { } ( ) Operators ◼ There are operators for: ◼ assignments ◼ mathematical operations ◼ relational operations ◼ Boolean operations ◼ bitwise operations ◼ shifting values ◼ calling functions ◼ subscripting ◼ obtaining the size of an object ◼ obtaining the address of an object ◼ referencing an object through its address ◼ choosing between alternate subexpressions  Variables in C Topics ◼ Naming Variables ◼ Declaring Variables ◼ Using Variables ◼ The Assignment Statement  What Are Variables in C? ◼ Variables in C have the same meaning as variables in algebra. That is, they represent some unknown, or variable, value. x=a+b z + 2 = 3(y - 5) ◼ Remember that variables in algebra are represented by a single alphabetic character. Naming Variables ◼ Variables in C may be given representations containing multiple characters. But there are rules for these representations. ◼ Variable names (identifiers) in C ◼ May only consist of letters, digits, and underscores ◼ May be as long as you like, but only the first 31 characters are significant ◼ May not begin with a digit ◼ May not be a C reserved word (keyword) Reserved Words (Keywords) in C auto break int long case char register return const continue short signed default do sizeof static double else struct switch enum extern typedef union float for unsigned void goto if volatile while  Naming Conventions ◼ C programmers generally agree on the following conventions for naming variables. ◼ Begin variable names with lowercase letters ◼ Use meaningful identifiers ◼ Separate “words” within identifiers with underscores or mixed upper and lower case. ◼ Examples: surfaceArea surface_Area surface_area ◼ Be consistent!  Naming Conventions (con’t) ◼ Use all uppercase for symbolic constants (used in #define preprocessor directives). ◼ Note: symbolic constants are not variables, but make the program easier to read. ◼ Examples: #define PI 3.14159 #define AGE 52  Case Sensitivity ◼ C is case sensitive ◼ It matters whether an identifier, such as a variable name, is uppercase or lowercase. ◼ Example: area Area AREA ArEa are all seen as different variables by the compiler. Which Are Legal Identifiers? AREA area_under_the_curve 3D num45 Last-Chance #values x_yt3 pi num$ %done lucky*** Declaring Variables ◼ Before using a variable, you must give the compiler some information about the variable; i.e., you must declare it. ◼ The declaration statement includes the data type of the variable. ◼ Examples of variable declarations: int meatballs ; float area ;  Declaring Variables (con’t) ◼ When we declare a variable ◼ Space is set aside in memory to hold a value of the specified data type ◼ That space is associated with the variable name ◼ That space is associated with a unique address ◼ Unless we specify otherwise, the space has no known value. ◼ Visualization of the declaration int meatballs ; meatballs garbage FE07 int  More About Variables C has three basic predefined data types: ◼ Integers (whole numbers) ◼ int, long int, short int, unsigned int ◼ Floating point (real numbers) ◼ float, double ◼ Characters ◼ char ◼ At this point, you need only be concerned with the data types that are bolded. Notes About Variables ◼ You must not use a variable until you somehow give it a value. ◼ You can not assume that the variable will have a value before you give it one. ◼ Some compilers do, others do not! This is the source of many errors that are difficult to find. ◼ Assume your compiler does not give it an initial value!  Using Variables: Initialization ◼ Variables may be be given initial values, or initialized, when declared. Examples: length 7 int length = 7 ; diameter 5.9 float diameter = 5.9 ; initial char initial = ‘A’ ; ‘A’  Using Variables: Assignment ◼ Variables may have values assigned to them through the use of an assignment statement. ◼ Such a statement uses the assignment operator = ◼ This operator does not denote equality. It assigns the value of the right-hand side of the statement (the expression) to the variable on the left-hand side. ◼ Examples: diameter = 5.9 ; area = length * width ; Note that only single variables may appear on the left- hand side of the assignment operator. Functions ◼ It is necessary for us to use some functions to write our first programs, but we are not going to explain functions in great detail at this time. ◼ Functions are parts of programs that perform a certain task and we have to give them some information so the function can do the task.  Displaying Variables ◼ Variables hold values that we occasionally want to show the person using the program. ◼ We have a function called printf( ) that will allow us to do that. ◼ The function printf needs two pieces of information to display things. ◼ How to display it ◼ What to display ◼ printf( “The value of the diameter: \n”, diameter ); printf( “The value of the diameter: \n”, diameter ); ◼ The name of the function is “printf”. ◼ Inside the parentheses are: ◼ print specification, where we are going to display: ◼ a message (“The value of the diameter: ”) ◼ We want to have the next thing started on a new line (“\n”). ◼ We want to display the contents of the variable diameter. ◼ printf( ) has many other capabilities.  Example: Declarations and Assignments inches #include garbage int main( void ) feet garbage { fathoms int inches, feet, fathoms ; garbage fathoms = 7 ; fathoms feet = 6 * fathoms ; 7 inches = 12 * feet ; feet 42 inches printf (“Its depth at sea: \n”) ; printf (“fathoms \n”, fathoms) ; 504 printf (“feet \n”, feet) ; printf (“inches \n”, inches) ; return 0 ; }  Enhanced Program #include int main ( void ) { float inches, feet, fathoms ; printf (“Enter the depth in fathoms : ”) ; scanf (“%f”, &fathoms) ; feet = 6 * fathoms ; inches = 12 * feet ; printf (“Its depth at sea: \n”) ; printf (“ fathoms \n”, fathoms) ; printf (“ feet \n”, feet) ; printf (“ inches \n”, inches) ; return 0 ; }  scanf (“%f”, &fathoms) ; ◼ The scanf( ) function also needs two items: ◼ The input specification “%f”. (Never put a “\n” into the input specification.) ◼ The address of where to store the information. (We can input more than one item at a time if we wish, as long as we specify it correctly.) ◼ Notice the “&” in front of the variable name. It says to use the address of the variable to hold the information that the user enters. Note About Input and Output ◼ Whenever we wish to display values or get values from the user, we have a format problem. ◼ We can only input characters, not values. ◼ We can only display characters, not values. ◼ The computer stores values in numeric variables. ◼ printf( ) and scanf( ) will automatically convert things for us correctly.  Final #include “Clean” Program #define FEET_PER_FATHOM 6 #define INCHES_PER_FOOT 12 int main( void ) { float inches ; float feet ; float fathoms ; printf (“Enter the depth in fathoms : ”) ; scanf (“%f”, &fathoms) ; feet = FEET_PER_FATHOM * fathoms ; inches = INCHES_PER_FOOT * feet ; printf (“Its depth at sea: \n”) ; printf (“ fathoms \n”, fathoms) ; printf (“ feet \n”, feet); printf (“ inches \n”, inches); return 0 ; }  Another Sample Program #include #define PI 3.14159 int main ( void ) { float radius = 3.0; float area; area = PI * radius * radius; printf( “The area is \n”, area ); return 0 ; } Functions in C OUTLINE ♦ Review of Functions in C ♦ Types of Function Calls ♦ Call by Value ♦ Call by Reference FUNCTIONS ♦ Modules in C are called functions. A function in C is defined to be the program segment that carries out some specific, well defined task. There are two types of functions: Library functions Programmer Defined functions Library Functions C standard library provides a rich collection of functions for performing I/O operations, mathematical calculations, string manipulation operations etc. For example, sqrt(x) is a function to calculate the square root of a double number provided by the C standard library and included in the header file. Library Functions Ex: : double a=9.9, b; b = sqrt(a); printf(“The square root of %f is %f”, a, b); : Other functions such as exp(x) (exponential function ex) and pow(x,y) (xy)... can be used as they are needed. Note that each program in C has a function called main which is used as the root function of calling other library functions. Programmer Defined Functions In C, the programmers can write their own functions and use them in their programs. Ex: The following program calls the programmer defined function called square to calculate the square of the numbers from 1 to 10. Programmer Defined Functions #include int square( int); int main() { int x; printf(“the squares of numbers from 1 to 10 are:\n”); for(x=1 ;x