Data Structures and Algorithms(All Sessions) PDF

2 Data Structure & Algorithms Code: INSY 8321  MODULE of DATA STRUCTURE AND ALGORITHMS INSTRUCTOR: BYIRINGIRO ERIC TEL:0782427392 E-mail :[email protected] 2024-11-17...

2 Data Structure & Algorithms Code: INSY 8321  MODULE of DATA STRUCTURE AND ALGORITHMS INSTRUCTOR: BYIRINGIRO ERIC TEL:0782427392 E-mail :[email protected] 2024-11-17 2  7 UNIT I: Algorithm analysis and design Chapter1 Introduction Chapter2 Presentation of algorithm Chapter3 Algorithm analysis UNIT II: Linear Data structures programming using C Course Outline Chapter1 Pointers, Arrays and Structures Chapter2 Sorting and searching Algorithms Chapter3 Linked list, Stacks and queues UNIT III: Non-Linear Data structure programming using c Chapter1 Tree and Graph Topics in data structure( Practice in C) 1. Binary search Algorithm 1. Doubly linked list 2. Linear Search Algorithm 2. Circular linked list 3. Stack 3. In-order tree traversal 4. Queue 4. Pre-order tree traversal 5. Sequential Queue 5. Post-order tree traversal 6. Priority Queue 6. Bubble sort 7. Circular Queue 7. Insertion sort 8. Double ended Queue 8. Selection sort 9. Singly linked list 9. Merge sort ALGORITHM ANALYSIS AND DESIGN "Learning to program is about developing algorithmic thinking skills, not about learning a programming language”  INTRODUCTION ❑Programming task can be divided into two phases: ▪ Problem solving phase Produce an ordered sequence of steps that describe solution of problem This sequence of steps is called an algorithm ▪ Implementation phase Implement the program in some programming language  Steps in Problem Solving ❑First produce a general algorithm. ❑Algorithms can be designed through the use of flowcharts or pseudocode ❑ Pseudocode is one of the tools that can be used to write a preliminary plan that can be developed into a computer program. Pseudocode is a generic way of describing an algorithm without use of any specific programming language syntax. ❑ Flowcharts work well for small problems but Pseudocode is used for larger problems  The Flowchart ❑Flowcharting is a tool developed in the computer industry, for showing the steps involved in a process. ❑A flowchart is a diagram made up of boxes, diamonds and other shapes, connected by arrows - each shape represents a step in the process, and the arrows show the order in which they occur. ❑Flowcharting combines symbols and flow lines, to show figuratively the operation of an algorithm. Flowchart Symbols Example 1. Design an algorithm and the corresponding flowchart for adding the test scores as given below: 26, 49, 98 a) Algorithm 1. Start 2. Sum = 0 3. Get the first tests core 4. Add first test score to sum 5. Get the second test score 6. Add to sum 7. Get the third test score 8. Add to sum 9. Output the sum 10. Stop In the above example, the problem with this algorithm is that, some of the steps appear more than once, i.e. step 5 get second number, step 7, get third number, etc. One could shorten the algorithm or flowchart as follows: 1. Start 2. Sum = 0 3. Get a value 4. sum = sum + value 5. Go to step 3 to get next Value 6. Output the sum 7. Stop Loops ❖ while loops ❖ for loops Loops  Algorithms employ two primary types of loops: 🞑 while loops: loops that execute as long as a specified condition is met – loop executes as many times as is necessary 🞑 for loops: loops that execute a specified exact number of times  Similar looking flowchart structures 🞑 for loop can be thought of as a special case of a while loop 🞑 However, the distinction between the two is very important  while Loop 26  Repeatedly execute an instruction or set of instructions as long as (while) a certain condition is met (is true)  Repeat A while X is true As soon as X is no longer true, break 🞑 out of the loop and continue on to B 🞑 A may never execute 🞑 A may execute only once 🞑 A may execute forever – an infinite loop ◼ If A never causes X to be false ◼ Usually not intentional  while Loop 27  Algorithm loops while 𝑥 ≤ 4 🞑 Loops three times: Iteration x 0 1 1 6 3 2 8 4 3 9 4.5  Value of 𝑥 exceeds 4 several times during execution 🞑 𝑥 value checked at the beginning of the loop  Final value of 𝑥 is greater than 4  while Loop – Example 1 30  Consider the following algorithm: 🞑 Read in a number (e.g. user input, from a file, etc.) 🞑 Determine the number of times that number can be successively divided by 2 before the result is ≤ 1  Use a while loop 🞑 Divide by 2 while number is > 1  while Loop – Example 1 32  Consider a few different input, x, values: count x x x 0 5 16 0.8 1 2.5 8 - 2 1.25 4 - 3 0.625 2 - 4 - 1 - 5 - - -  While Loop – Example2 33  Next, consider an algorithm to calculate x!, the factorial of x: 🞑 Read in a number, x 🞑 Compute the product of all integers between 1 and x 🞑 Initialize result, fact, to 1 🞑 Multiply fact by x 🞑 Decrement x by 1  Use a while loop 🞑 Multiply fact by x, then decrement x while x > 1 K. Webb ENGR 112  while Loop – Example 2 34  Consider a few different input, x, values: x fact x fact x fact 5 1 4 1 0 1 5 5 4 4 - - 4 20 3 12 - - 3 60 2 24 - - 2 120 1 24 - - 1 120 - - - - for Loop  We’ve seen that the number of while loop iterations is not known ahead of time 🞑 May depend on inputs, for example  Sometimes we want a loop to execute an exact, specified number of times  A for loop 🞑 Utilize a loop counter 🞑 Increment (or decrement) the counter on each iteration 🞑 Loop until the counter reaches a certain value  for Loop 38  Initialize the loop counter 🞑 i, j, k are common, but name does not matter  Set the range for i 🞑 Not necessary to define variable istop  Execute loop instructions, A  Increment loop counter, i  Repeat until loop counter reaches its stopping value  Continue on to B  for Loop 39  for loops are counted loops  Number of loop iterations is known and is constant 🞑 Here loop executes 10 times  Stopping value not necessarily hard-coded 🞑 Could depend on an input or vector size, etc. for Loop  Loop counter may start at value other than 1  Increment size may be a value other than 1  Loop counter may count backwards Iteration cntr Process 1 6 A 2 4 A 3 2 A 4 0 A 5 -2 A 6 -4 B for Loop – Example 1  Here, the loop counter, i, is used to update a variable, x, on each iteration Iteration i x 1 1 1 2 2 4 3 3 9 4 4 16 5 5 25  When loop terminates, and flow proceeds to the next process step, x = 25 Show the output for the following flowchart: Draw a flowchart for checking a user’s PIN number and locking them out if three incorrect entries are made.  Nested Loops 46  A loop repeats some process some number of times 🞑 The repeated process can, itself, be a loop 🞑 A nested loop  Can have nested for loops or while loops 🞑 Can nest for loops within while loops and vice versa  One application of a nested for loop is to step through every element in a matrix 🞑 Loop counter variables used as matrix indices 🞑 Outer loop steps through rows (or columns) 🞑 Inner loop steps through columns (or rows) // Pseudocode for nested while loops outer_initialization while (outer_condition) { inner_initialization while (inner_condition) { // Code block to be repeated inner_update } outer_update } Write down the output of the following flowchart: Activity#1&2 ❑Write down the pseudocode, build a flow chart and C program to print the times table for 8 in one column ❑Write down the pseudocode, build a flow chart and C program to print out all integers from 11 down to -20. ❑ Pseudocode Start Declare a variable of type integer and set the initial value to 0, int i = 0; For repetition we need to use loop, for loop. Start the for loop. Set the terminal condition, i