CPE5 Midterm - Data Structures and Algorithms

**for loop** **Nested if** **if... else** statement is also called as **multi-way decision control statement** **while loop** while boolean\_expression: range(start, stop, step) range(stop) it follows indexing so stop starts at 0 by default and ends with the stop value but doesn't includes th...

**for loop** **Nested if** **if... else** statement is also called as **multi-way decision control statement** **while loop** while boolean\_expression: range(start, stop, step) range(stop) it follows indexing so stop starts at 0 by default and ends with the stop value but doesn't includes the value itself An **algorithm** is a sequence of clear and precise **step-by-step instructions for solving a problem** in a finite amount of time. **2 Common Types of Abstraction encountered in Computer Science** **1. Procedural abstraction** is the use of a function or method knowing what it does but ignoring how it\'s accomplished. Consider the mathematical square root function. The function will compute the square root of a given number. **2. Data Abstraction** is the separation of the properties of a data type (its values and operations) from the implementation of that data type **Abstract Data Types** Abstract Data Type (ADT) is a programmer-defined data type that specifies a set of data values and a collection of well-defined operations that can be performed on those values. This in known as **information hiding**. Focusing on the **"what"** instead of the **"how".** User programs interact with instances of the ADT by invoking one of the several operations defined by its interface. The set of operations can be grouped into four categories: **Constructors:** Create and initialize new instances of the ADT. **Accessors:** Return data contained in an instance without modifying it. **Mutators:** Modify the contents of an ADT instance. **Iterators:** Process individual data components sequentially. This separation is typically enforced by requiring interaction with the abstract data type through an **interface** or **defined set of operations.** **Traversals** are very common operations, especially on containers. A traversal iterates over the entire collection, providing access to each individual element. **Traversals** can be used for a number of operations, including searching for a specific item or printing an entire collection. **Array** - The most basic structure for storing and accessing a collection of data. Arrays can be used to solve a wide range of problems in computer science. Most programming languages provide this structured data type as a primitive and allow for the creation of arrays with multiple dimensions. **The Array Structure** At the hardware level, most computer architectures provide a mechanism for creating and using **one-dimensional arrays**. It is composed of multiple sequential elements stored in contiguous bytes of memory and allows for random access to the individual elements. **Array vs. List** **Array** has limited operations, which commonly include those for, array creation, reading a value from a specific element, and writing a value to a specific element, compared to **list** that has a large number of operations. Second, the **list** can grow and shrink during execution as elements are added or removed while the size of an array cannot be changed after it has been created. In short, list has more operation, easily mutable and has more storage, in contrast to an array. **Array** is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of **arrays** to implement their algorithms. **Lists** can be used to form arrays. Following are the important terms to understand the concept of **Array**. **List** **Access:** List\_name\[index\] **Change items:** List\_name\[index\] = element\_to\_change **Add elements at the end:** List\_name.append(end\_element) **Add element at a specified position:** List\_name.insert(index, element) **Extend list:** List\_name\_1.extend(List\_name\_2) **Sort list:** **Ascending:** List\_name.sort() **Descending:** List\_name.sort(reverse = True) **Removes the first occurrence of a specified element:** List\_name.remove(element\_first\_occurence) **Remove the element at a specified position in the list and returns it:** List\_name.pop(index) **Last element if index is not specified.**