Introduction to Data Structures and Algorithms PDF

Introduction to Data Structures and Algorithms What is Data Structures? Are the fundamental building blocks of computer programming. They define how data is organized, stored, and manipulated within a program. Commonly used data structures including arrays, linked lists, stacks, queues, and...

Introduction to Data Structures and Algorithms What is Data Structures? Are the fundamental building blocks of computer programming. They define how data is organized, stored, and manipulated within a program. Commonly used data structures including arrays, linked lists, stacks, queues, and trees. Common Data Structures: Arrays a collection of elements, each identified by an index. ○ Example: A shopping list where each item is stored in a numbered position. Common Data Structures: Cont., Linked Lists a linear collection of data elements where each element points to the next. ○ Example: A playlist where each song points to the next one. Common Data Structures: Cont., Stacks a LIFO (Last In, First Out) structure. New elements are added and removed from the top. ○ Example: A stack of plates where the last plate placed is the first one taken out. Common Data Structures: Cont., Queues a FIFO (First In, First Out) structure. Elements are added at the rear and removed from the front. ○ Example: A waiting line at a ticket counter. Common Data Structures: Cont., Trees A hierarchical structure with a root node and child nodes. ○ Example: A file system structure with folders and files. Why Data Structures Matter? The choice of data structure depends on the specific problem you're solving. Some key factors to consider include: ○ Access patterns ○ Insertion and deletion ○ Memory usage ○ Performance Classification of Data Structures What is an Algorithm? An algorithm is essentially a step-by-step recipe for solving a problem. It's a set of instructions that a computer can follow to accomplish a task. A good algorithm should be: ○ Correct: It should always produce the right answer. ○ Efficient: It should use minimal resources (like time and memory) to solve the problem. Example: Finding the Largest Number 1. Start 2. Assume the first number in the list is the largest. 3. Compare the current largest number with the next number in the list. 4. If the next number is larger, make it the new largest number. 5. Repeat steps 3 and 4 for all remaining numbers in the list. 6. The final largest number is the answer. 7. End Criteria for Algorithms For an algorithm to be effective, it must meet the following criteria: Input: The algorithm must clearly specify the data it takes as input. Output: The algorithm must clearly define the result it produces. Definiteness: Each step of the algorithm must be clear. Finiteness: The algorithm must eventually terminate after a finite number of steps. Effectiveness: The algorithm must be feasible and produce the correct result. Representing Algorithms There are different ways to represent an algorithm: Natural Language: Using everyday language to describe the steps. Flowcharts: Using diagrams to represent the flow of control. Pseudocode: A mixture of natural language and code-like syntax. EXAMPLE: A program that calculates the factorial of a number NATURAL LANGUAGE To find the factorial of a number n, follow these steps: 1. Start with a variable result and set it to 1. 2. For every number i from 1 to n, multiply result by i. 3. After completing all multiplications, the result will be the factorial of n. EXAMPLE: A program that calculates the factorial of a number PSEUDOCODE function factorial(n): result = 1 for i = 1 to n: result = result * i return result Activity Refer to the instructions outlined in Canvas - Module 1, Activity 1. Python's Built-in Collections Lists: ○ Ordered collections of items. ○ Mutable (can be changed). ○ Use square brackets [] to create. Examples: numbers = [1, 2, 3, 4, 5] names = ["Alice", "Bob", "Charlie"] ○ Are used to store multiple items in a single variable. my_list = [10, "apple", 3.14, True, ["nested", "list"]] print(my_list) Python Lists List items are ordered, changeable, and allow duplicate values. ○ List items are indexed, the first item has index , the second item has index etc. Ordered The items have a defined order, and that order will not change. If you add new items to a list, the new items will be placed at the end of the list. Changeable you can change, add, and remove items in a list after it has been created. List Operations Lists Length To determine how many items a list has, use the len() function. Example def list(): fruits = ["apple", "banana", "cherry"] print(len(fruits)) list() Lists Item Data Types List items can be of any data type: String, int and boolean data types. def mylists(): list1 = ["apple", "banana", "cherry"] list2 = [1, 5, 7, 9, 3] list3 = [True, False, False] print(list1) print(list2) print(list3) mylists() Access List Items List items are indexed and you can access them by referring to the index number. def index_list(): fruits = ["apple", "banana", "cherry"] print(fruits) index_list() Access List Items Range of Indexes specify a range of indexes by specifying where to start and where to end the range. def index(): thislist = ["apple", "banana", "cherry", "orange", "kiwi", "melon", "mango"] print(thislist[2:5]) index() Access List Items Range of Indexes ○ Leaving out the value def index_remove(): thislist = ["apple", "banana", "cherry", "orange", "kiwi", "melon", "mango"] print(thislist[:4]) index_remove() Access List Items Range of Negative Indexes ○ Specify negative indexes if you want to start the search from the end of the list. def index_negative(): thislist = ["apple", "banana", "cherry", "orange", "kiwi", "melon", "mango"] print(thislist[-4:-1]) index_negative() Change Item Value To change the value of a specific item, refer to the index number. def index_list1(): fruits = ["apple", "banana", "cherry"] fruits = "melon" print(fruits) index_list1() Change a Range of Item Values To change the value of items within a specific range def index_change(): fruits = ["apple", "banana", "cherry", "orange", "kiwi", "mango"] fruits[1:2] = ["pineapple", "watermelon"] print(fruits) index_change() Insert Items To insert a new list item, without replacing any of the existing values, we can use the insert() method. def add_list(): fruits = ["apple", "banana", "cherry"] fruits.insert(2, "watermelon") print(fruits) add_list() Add List Items Append items To add an item to the end of the list, use the append() method. def add_list1(): fruits = ["apple", "banana", "cherry"] fruits.append("orange") print(fruits) add_list1() Extend List To append elements from another list to the current list, use the extend() method. def insert(): thislist = ["apple", "banana", "cherry"] tropical = ["mango", "pineapple", "papaya"] thislist.extend(tropical) print(thislist) insert() Remove Specified Items The remove() method removes the specified item.. def list_remove(): thislist = ["apple", "banana", "cherry"] thislist.remove("banana") print(thislist) list_remove() Remove Specified Index The pop() method removes the specified index. def remove1(): thislist = ["apple", "banana", "cherry"] thislist.pop(1) print(thislist) remove1() Remove Specified Index The del keyword also removes the specified index. def del_list(): thislist = ["apple", "banana", "cherry"] del thislist print(thislist) del_list() Activity Refer to the instructions outlined in Canvas - Module 1, Activity 2. Tuples Python's Built-in Collections Cont., Tuples: ○ Ordered collections of items. ○ Contain elements of different data types. ○ Immutable (cannot be changed). ○ Use parenthesis () to create. Examples: coordinates = (3, 4) person = ("John Doe", 30, "New York") Why use Tuples? Efficiency Data Integrity Tuples Operations While tuples are immutable, you can perform some operations on them: Indexing and slicing: Access specific elements or create sub-tuples. Concatenation: Combine tuples using the + operator. Length: Find the number of elements using len(). Membership testing: Check if an element is present using in and not in. Concatenation: Combine tuples using the + operator. Python code coordinates = (3, 4) new_coordinates = coordinates + (5,) print(len(coordinates)) print(3 in coordinates) Membership Testing: Check if an element is present using in and not in Python code my_tuple = (1, 2, 3, 4, 5) if 6 in my_tuple: print("6 is present in the tuple") else: print("6 is not present in the tuple")  Access Tuple Items name = ("ana", "boy", "cherry") print(name) Negative Indexing means start from the end. -1 refers to the last item, -2 refers to the second last item etc. name = ("ana", "boy", "cherry") print(name[-1])  Range of Indexes a range of indexes by specifying where to start and where to end the range. name = ("ana", "boy", "cherry") print(name[1:2]) Range of Negative Indexes returns the items from index -2 (included/ refers to second to last element) to index -1 (excluded/ last element) name = ("ana", "boy", "cherry") print(name[-2:-1]) Tuple Modification Converting it to a List Modify a tuple by converting it to a list, making changes, and then converting it back to a tuple. Example name = ["ana", "boy", "cherry"] name1 = list(name) name1=("dennis") name = tuple(name1) print(name) Using append() method name = ("ana", "boy", "cherry") name1 = list(name) name1.append("dennis") name = tuple(name1) print(name) Concatenate + operator It creates a new list by combining the elements of the original lists. name = ["ana", "boy", "chery"] name1 = ("den", "bing") name += name1 print(name) * operator This method unpacks the elements of multiple lists and creates a new list. names = ["ana", "boy", "chery"] names1 = ("den", "bing") concatenated_names = [*names, *names1] print(concatenated_names) Activity Refer to the instructions outlined in Canvas - Module 1, Activity 3. Dictionary Python's Built-in Collections Cont., Dictionary: ○ Unordered collections of key-value pairs. ○ Mutable. ○ Use curly braces {} to create. Examples: person = {"name": "Alice", "age": 30, "city": "New York"} phonebook = {"Alice": "123-4567", "Bob": "987-6543"} Key Characteristics of Dictionaries Unordered Mutable Key Value Pairs Curly Braces Example student = {"name": "Alice", "age": 20, "city": "New York"} print(student["name"]) print(student["age"]) student["age"] = 21 print(student["age"]) student["major"] = "Computer Science" print(student) Dictionary Operations get() method Provides a safer way to access values in a dictionary. Unlike direct access using square brackets, get() returns a default value if the key is not found, preventing a KeyError. student = {"name": "Alice", "age": 20, "city": "New York"} print(student.get("name")) print(student.get("age")) print(student.get("major")) print(student.get("phone", "Not available")) Removing Key-Value Pairs Using del: used to deletes a key-value pair. student = {"name": "Alice", "age": 20, "city": "New York"} del student ["age"] print(student) Removing Key-Value Pairs Cont., Using pop(): method is used to remove and return an element from a dictionary. student = {"name": "Alice", "age": 20, "city": "New York"} student.pop("age") print(student) Checking for Keys Using in: is used to check if a specific key exists within a dictionary. student = {"name": "Alice", "age": 20, "city": "New York"} if 'name' in student: print("Name exists") else: print("Name does not exists") Getting Keys, Values, and Items keys(): method is used to extract all the keys from a dictionary. student = {"name": "Alice", "age": 20, "city": "New York"} print(student.keys()) Getting Keys, Values, and Items values(): Returns a view of the dictionary's values student = {"name": "Alice", "age": 20, "city": "New York"} print(student.values()) Getting Keys, Values, and Items items(): Returns a view of the dictionary's key-value pairs student = {"name": "Alice", "age": 20, "city": "New York"} print(student.items()) Other Useful operations len(my_dict): Returns the number of key-value pairs ○ print(len(student)) my_dict = {} / del my_dict ○ student = {} / del student Activity Refer to the instructions outlined in Canvas - Module 1, Activity 4. Quiz 1 and 2 End. References - GeeksforGeeks. (2014). Data Structures - GeeksforGeeks. GeeksforGeeks. https://www.geeksforgeeks.org/data-structures/ - Intro TO DATA Structure - INTRO TO DATA STRUCTURE/ALGORITHM Data structures and algorithms are - Studocu. (n.d.). Retrieved August 3, 2024, from https://www.studocu.com/en-us/document/la-salle-university/intro-data-structurealgorithm/int ro-to-data-structure/41766542 - Python - Lists. (n.d.). Www.tutorialspoint.com. Retrieved February 6, 2024, from https://www.tutorialspoint.com/python_data_structure/python_lists_data_structure.htm - Easy, S. (2023, April 18). Tuple in Python | Creating, Example. Scientech Easy. https://www.scientecheasy.com/2023/04/python-tuple.html/ - Gus. (2022, April 6). Python Tuples. Pi My Life Up. https://pimylifeup.com/python-tuples/ - Python - Dictionary. (n.d.). Www.tutorialspoint.com. Retrieved February 12, 2024, from https://www.tutorialspoint.com/python_data_structure/python_dictionary_data_structure.htm