CS250: Data Structures and Algorithms Fall 2024 Course Outline PDF

CS250: Data Structures and Algorithms Fall 2024 BSDS-1A Credit Hours: 3+1 Lecture Outline Introduction Of the class Teaching team Overview Difference between File-based and Database Approach Data vs Information Information System Overview of DBMS Database Desi...

CS250: Data Structures and Algorithms Fall 2024 BSDS-1A Credit Hours: 3+1 Lecture Outline Introduction Of the class Teaching team Overview Difference between File-based and Database Approach Data vs Information Information System Overview of DBMS Database Design Types of Databases 2  Course Learning Outcome Assessment No. Course Learning Outcomes BT Level Methods CLO Describe the fundamentals of data C-2 Quiz, Assignment, 1 structures and algorithms (Understand) MSE, ESE CLO Solve a given real time problem by C-3 Quiz, Assignment, Lab, 2 applying appropriate data (Apply) MSE, ESE structure and algorithm. CLO Practice programs using the latest P-3 Lab 3 IDEs ensuring testing, (Guided documentation and packaging of Response) programs as per standards practices applicable to the software industry. CLO Demonstrate commitment to A-3 Project, Lab 4 professional ethics by following (Valuing) engineering norms applicable to the software industry. CLO Contribute effectively both A-2 Project, Lab 5 individually and as a team (Responding) member Recommended Text/ Reference Books Data Structures & Algorithms Using C++, Fourth or latest Edition, Nell Dale Adam Drozdek. Data Structures and Algorithms in C++, sixth Edition (2016) T. H. Cormen, Charles E. Leiserson, R. L. Rivest, Clifford S. Introduction to Algorithms, Third Edition (2009) Mark A. Weiss, Data Structures and Algorithm Analysis in C++, Fourth Edition (2013) Data Structures & Algorithms Using C++, Fourth or latest Edition, John Bullinaria (2019) 4 Lecture Resources & Class Policy LMS: Course Outline Lecture Assignment Labs/Lab Submission CMS: Attendance (75% is the minimum requirement to appear in ESE) Grading 5 Tentative Grading Criteria Lecture (3 Credit Hrs./Week-75%) Quizzes: 10% Assignments: 10% Final Report: 10% MSE: 30% ESE: 40% Lab (3 Hrs./Week-25%) In-Lab Work: 70% Final Lab: 10% Group Project: 20% Zero tolerance for plagiarism 6 Course Contents  Introduction to data structures & algorithms  Pointers, structures & arrays  Linked Lists (single, double & circular)  Stacks (and its applications)  Queues  Algorithm (with asymptotic analysis)  Sorting algorithms (insertion-, merge-, quick-sort)  Recursion  Trees (Binary tree, B-tree, etc.)  Heapsort  Hash tables  Graphs  Search algorithms (Depth First Search)  Shortest path algorithm 7 Class Rules (1/2) No verbal consultations during the class No personal comments Do not disturb the class If something is not clear, do tell!! If you have question, do not hesitate. Read the course outline(Uploaded on LMS) Course Contents Available on LMS Will contain limited information only, so better to consult online and secondary resources as well. Class Rules (2/2) Plagiarism and Academic Dishonesty are strictly prohibited No submission via email Late Day Policy Total late days: 5 Can be used for assignments, final report, and project only No consolidation among group members No swapping/sharing Use self tracking during the course Final count will be done at the end of the course (by me) No penalty for consuming a late day Each day consumed beyond the allocated late days -> -2% from overall score in assignments, Final report, and project; until all reach 0. Contact [email protected] Consulting Hours: Friday (3pm-5pm) or by appointment Lecture 1 Introduction to Data Structures 11 What is a Data Structure?  Data Structure => Data StructurING ► How do we organize information so that we can find, update, add, and delete portions of it efficiently? ► Data Structure is a systematic way to organize data in order to use it efficiently ► Data Structure Categorization: - In terms of Types: Primitive vs Non-primitive/User-Defined (Linear vs Non Linear) - In terms of memory allocation: static vs dynamic ► Non-primitive or User-Defined: - Linear vs Non-linear 12 What is a Data Structure?  It’s an agreement about: ► How to store a collection of objects in memory, ► What operations we can perform on that data, ► The algorithms for those operations, and ► How time and space efficient those algorithms are  A collection of data elements whose organization is managed by the operations that are used to store and retrieve the individual data elements 13 What is a Data Structure Anyway?  It’s an agreement about: ► how to store a collection of objects in memory, ► what operations we can perform on that data, ► the algorithms for those operations, and ► how time and space efficient those algorithms are.  Ex. List data structure ► A collection of homogenous elements with linear relationship b/w them e.g. list of students registered in this class ► Operations: Can access, change, insert or delete elements ► Algorithms: Searching  linear vs binary search ► Time Complexity: linear search O(n), binary search in array-list O(log2n), More operations later. 14 Why is Data StructurING necessay? Three common problems:  Data Search ► E.g., an inventory of 1 million(106) items of a store  Processor Speed ► Processor speed although being very high, falls limited if the data grows to billion records  Multiple Requests ► As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data 15 Foundation terms Each data structure has an  Interface ► Represents the set of operations that a data structure supports & ► Only provides the list of supported operations, type of parameters they can accept and the return type of these operations  Implementation ► Provides the internal representation of a data structure ► The definition of the algorithms used in the operations of the data structure 16 Example  Data structure for storing data of students:- ► Arrays ► Linked Lists  Issues ► Space needed ► Operations efficiency (Time required to complete operations) - Retrieval - Insertion - Deletion 17 Which data structure to use?  Data structures let the input and output be represented in a way that can be handled efficiently and effectively array Linked list queu tre e stac e k 18 Introduction to algorithms  Algorithm ► Named after a Muslim mathematician, Al-Khawarzmi ► Definition - An algorithm is a definite procedure for solving a problem in finite number of steps - Algorithm is a well-defined computational procedure that takes some value(s) as input, and produces some value(s) as output - Algorithm is finite number of computational statements that transform input into the output 19 What is an algorithm?  An algorithm is an effective method for solving a problem using a finite sequence of instructions  Examples ► sort a list of numbers ► find a route from one place to another (cars, packet routing, phone routing,...) ► find the longest common substring between two strings ► microchip wiring/design (VLSI) ► solving sudoku ► cryptography ► compression (file, audio, video) ► pagerank ► classify a web page 20 Properties of interest  What properties of algorithms are we interested in? ► Does it terminate? ► Is it correct, i.e. does it do what we think it’s supposed to do? ► What are the computational costs? ► What are the memory/space costs? ► What happens to the above with different inputs? ► How difficult is it to implement and implementing it correctly? 21 Data structures & algorithms  Operations are associated with data structure  To perform these operations, algorithms are needed Data structures + Algorithms = Programs 22 Data Type  A data type is a type together with a collection of operations to manipulate the type ► E.g., an integer variable is a member of the integer data type while addition is an example of an operation on the integer data type 23 Data Types  Primitive Data Types ► Bool, Int, float etc.  User-Defined Data Types (UDTs) ► Aggregate data types e.g., structures, array-of-integers etc.  Abstract Data Types (ADTs) ► Does not specify how the data type is implemented ► These implementation details are hidden from the user of the ADT and protected from outside access, a concept referred to as encapsulation 24 Abstract data types (ADT)  Different implementations possible for same ADT  In an object-oriented language such as C++, an ADT and its implementation together make up a class Much of our concern in this course is how to implement data structures as ADTs 25 Abstract Data Types (ADTs)  Data storage & operations encapsulated by an ADT.  ADT specifies permitted operations as well as time and space guarantees.  User unconcerned with how it’s implemented ► but we are concerned with implementation in this class  ADT is a concept or convention: ► not something that directly appears in your code ► programming language may provide support for communicating ADT to users ► (e.g. classes in Java & C++) 26 Data Organizing Principles  Ordering ► Put keys into some order so that we know something about where each key is relative to the other keys. ► Phone books are easier to search because they are alphabetized.  Linking ► Add pointers to each record so that we can find related records quickly. ► E.g. The index in the back of book provides links from words to the pages on which they appear.  Partitioning: ► Divide the records into 2 or more groups, each group sharing a particular property. ► E.g. Multi-volume encyclopedias (Aa-Be, W-Z) ► E.g. Folders on your hard drive 27 Ordering 28 Linking  Records located any where in memory  Green pointers give “next” element  Red pointers give “previous” element  Insertion & deletion easy if you have a pointer to the middle of the list  Don’t have to know size of data at start  Pointers let us express relationships between pieces of information. 29 Partitioning  Ordering implicitly gives a partitioning based on the “