2024-S2-IT2070-Lecture-01-Introduction.pdf

Data Structures and Algorithms IT2070 – Data Structures and Algorithms Introduction 1 SLIIT - Facul...

Data Structures and Algorithms IT2070 – Data Structures and Algorithms Introduction 1 SLIIT - Faculty of Computing Data Structures and Algorithms Subject Group Malabe Campus Dr. Bhagya Nathali Silva Dr. Dinuka Wijendra Ms. Jenny Krishara Metro Campus Ms. Mihiri Samaraweera Kandy Center Ms. Chathurika Pinnaduwage Matara Center Mr. Ravi Supunya Jaffna Center Ms. Sangeetha Balasingam 2 SLIIT - Faculty of Computing Data Structures and Algorithms Teaching Methods Lectures – 2 hours/week Tutorials – 2 hour/week Labs – 2 hours /week 3 SLIIT - Faculty of Computing Data Structures and Algorithms Student Evaluation Assessments (Two exams) - 40 % Final Examination - 60 % 4 SLIIT - Faculty of Computing Data Structures and Algorithms Lectures will cover Data Structures - Stack data structure - Queue data structure - Linked list data structure - Tree data structure Algorithms - Asymptotic Notations - Algorithm designing techniques - Searching and Sorting algorithms 5 SLIIT - Faculty of Computing Data Structures and Algorithms Tutorials and Labs will cover -Solve problems using the knowledge acquired in the lecture -Get hands on experience in writing programs - Java - Python 6 SLIIT - Faculty of Computing Data Structures and Algorithms Data Structures and Algorithms Data Structures - Data structure is an arrangement of data in a computer’s memory or sometimes on a disk. Ex: stacks, queues, linked lists, trees Algorithms - Algorithms manipulate the data in these structures in various ways. Ex: searching and sorting algorithms 7 SLIIT - Faculty of Computing Data Structures and Algorithms Data Structures and Algorithms Usage of data structures Real world data storage Real world modeling - queue, can model customers waiting in line - graphs, can represent airline routes between cities Programmers Tools - stacks, queues are used to facilitate some other operations 8 SLIIT - Faculty of Computing Data Structures and Algorithms Data Structures and Algorithms Algorithms Algorithm is a well defined computational procedure that takes some value or set of values as input and produce some value or set of values as output. An algorithm should be - correct. - unambiguous. - give the correct solution for all cases. - simple. - terminate. 9 SLIIT - Faculty of Computing Data Structures and Algorithms Academic Integrity Policy Are you aware that following are not accepted in SLIIT??? Plagiarism - using work and ideas of other individuals intentionally or unintentionally Collusion - preparing individual assignments together and submitting similar work for assessment. Cheating - obtaining or giving assistance during the course of an examination or assessment without approval Falsification – providing fabricated information or making use of such materials From year 2018 the committing above offenses come with serious consequences ! See General support section of Courseweb for full information. 10 SLIIT - Faculty of Computing Data Structures and Algorithms References 1. Mitchell Waite,Robert Lafore, Data Structures and Algorithms in Java,2nd Edition, Waite Group Press,1998. 2. T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms,3rd Edition, MIT Press, 2009. 11 SLIIT - Faculty of Computing Data Structures and Algorithms IT2070 – Data Structures and Algorithms Lecture 01 Introduction to Stack 12 SLIIT - Faculty of Computing Data Structures and Algorithms Stack  Allows access to only one data item; the last item inserted  If you remove this item, then you can access the next-to-last item inserted 13 SLIIT - Faculty of Computing Data Structures and Algorithms Application of Stacks String Reverse Page visited history in Web browser. Undo sequence of text editor. Recursive function calling. Auxiliary data structure for Algorithms. Stack in memory for a process 14 SLIIT - Faculty of Computing Data Structures and Algorithms Stack Top  In a stack all insertions and deletions are made at one end (Top). Insertions and deletions are restricted from the Middle and at the End of a Stack  Adding an item is called Push  Removing an item is called Pop  Elements are removed from a Stack in the reverse order of that in which the elements were inserted into the Stack  The elements are inserted and removed according to the Last-In-First-Out (LIFO) principle. 15 SLIIT - Faculty of Computing Data Structures and Algorithms Stack - Push Push item 49 Before inserting Item 49 is inserted on top After inserting 16 SLIIT - Faculty of Computing Data Structures and Algorithms Stack - Pop Pop Before removing Top item is removed After removing 17 SLIIT - Faculty of Computing Data Structures and Algorithms Stack - Peek 49 Peek Stack remains the same Peek is used to read the value from the top of the stack without removing it. You can peek only the Top item, all the other items are invisible to the stack user. 18 SLIIT - Faculty of Computing Data Structures and Algorithms Question Draw the stack frame after performing the below operations to the stack given below. 25 Top 300 i) Push item 50 ii) Push item 500 iii) Peek iv) Push item 100 v) Pop vi) Pop vii) Pop viii) Pop 19 SLIIT - Faculty of Computing Data Structures and Algorithms Uses of Stack  The stack operations are built into the microprocessor.  When a method is called, its return address and arguments are pushed onto a stack, and when it returns they’re popped off. 20 SLIIT - Faculty of Computing Data Structures and Algorithms Stack - Implementation Stack implementation using an array class StackX {  Constructor creates a new stack of a size specified in its argument. private int maxSize; // size of stack array private double[] stackArray; private int top; //top of the stack  Variable top, which stores the publc StackX(int s) { // constructor index of the item on the top of the stack. maxSize = s; // set array size stackArray = new double[maxSize]; top = -1; // no items } ……………………. ……………………. } 21 SLIIT - Faculty of Computing Data Structures and Algorithms Stack – Implementation - push class StackX{ private int maxSize; // size of stack array private double[] stackArray; private int top; //top of the stack publc StackX(int s) { // constructor maxSize = s; // set array size stackArray = new double[maxSize]; top = -1; // no items } public void push(double j) { // increment top // insert item } 22 SLIIT - Faculty of Computing Data Structures and Algorithms Stack – Implementation - push class StackX { private int maxSize; // size of stack array private double[] stackArray; private int top; //top of the stack publc StackX(int s) {// constructor maxSize = s; // set array size stackArray = new double[maxSize]; top = -1; // no items } public void push(double j) { // increment top. insert item stackArray[++top] = j; } 23 SLIIT - Faculty of Computing Data Structures and Algorithms Stack – Implementation - push class StackX { private int maxSize; // size of stack array private double[] stackArray; private int top; //top of the stack public StackX(int s) {// constructor maxSize = s; // set array size stackArray = new double[maxSize]; top = -1; // no items } public void push(double j) { // check whether stack is full if (top == maxSize – 1) System.out.println(“Stack is full”); else stackArray[++top] = j; } 24 SLIIT - Faculty of Computing Data Structures and Algorithms Stack – Implementation – pop/peek class StackX public double pop() { { // check whether stack is empty private int maxSize; // size of stack array // if not private double[] stackArray; // access item and decrement top private int top; //top of the stack } public StackX(int s) {// constructor maxSize = s; // set array size public double peek() { stackArray = new double[maxSize]; top = -1; // no items } // check whether stack is empty public void push(double j) { // if not // check whether stack is full // access item if (top == maxSize – 1) } System.out.println(“Stack is full”); else stackArray[++top] = j; } 25 SLIIT - Faculty of Computing Data Structures and Algorithms Stack – Implementation – pop/peek class StackX { public double pop() { private int maxSize; // size of stack array if (top == -1) private double[] stackArray; return -99; private int top; //top of the stack else public StackX(int s) { // constructor return stackArray[top--]; maxSize = s; // set array size } stackArray = new double[maxSize]; top = -1; // no items } public double peek() { public void push(double j) { if (top == -1) // check whether stack is full return -99; if (top == maxSize – 1) else System.out.println(“Stack is full”); else return stackArray[top]; stackArray[++top] = j; } } 26 SLIIT - Faculty of Computing Data Structures and Algorithms Question isEmpty() method returns true if the stack is empty and isFull() method return true if the Stack is full. Implement isEmpty() and isFull() methods of the stack class. 27 SLIIT - Faculty of Computing Data Structures and Algorithms Creating a stack Question Using the implemented StackX class, Write a program to create a stack with maximum size 10 and insert the following items to the stack. 30 80 100 25 Delete all the items from the stack and display the deleted items. 28 SLIIT - Faculty of Computing Data Structures and Algorithms Creating a stack class StackApp { public static void main(String[] args) { StackX theStack = new StackX(10); // create a stack with max size 10 theStack.push(30); // insert given items theStack.push(80); theStack.push(100); theStack.push(25); while( !theStack.isEmpty() ) { // until it is empty, delete item from stack double val = theStack.pop(); System.out.print(val); System.out.print(“ “); } } } // end of class 29 SLIIT - Faculty of Computing Data Structures and Algorithms References 1. Mitchell Waite,Robert Lafore, Data Structures and Algorithms in Java,2nd Edition, Waite Group Press,1998. 30 SLIIT - Faculty of Computing