CC4 Midterms Flashcards
- is a step-by-step unambiguous instruction used to solve a given problem.
o Example: A recipe that tells you exactly how to bake a cake, one step at a time.
Algorithm
o Example: A recipe that tells you exactly how to bake a cake, one step at a time.
Algorithm
- In programming, IT defines a set of values and the operations that can be performed on those values. Predefined values include integers, floats, and strings.
o Example: Integers (e.g., 1, 2, 3) are data types that represent whole numbers.
Data Types
o Example: Integers (e.g., 1, 2, 3) are data types that represent whole numbers.
Data Types
- is a way to organize and store data in a computer so that it can be accessed and modified efficiently.
o Example: Arrays, Linked Lists, Stacks, and Queues.
Data Structure
o Example: Arrays, Linked Lists, Stacks, and Queues.
Data Structure
- Refers to a type of data that is defined by its behavior (operations that can be performed on it), rather than its concrete implementation.
o Example: A stack can be represented with an array or linked list, but as an ADT, you only care about operations like push, pop, and peek.
4. Abstract Data Types (ADT)
o Example: A stack can be represented with an array or linked list, but as an ADT, you only care about operations like push, pop, and peek.
4. Abstract Data Types (ADT)
- : Data is arranged in a linear sequence (e.g., Arrays, Lists).
Linear Data Structure
- : Elements are arranged in a hierarchy or graph, such as Trees and Graphs.
Non-Linear Data Structure
- it measures how the running time of an algorithm grows with the input size. Common cases include:
o Best Case: Minimum time an algorithm takes to complete.
o Worst Case: Maximum time an algorithm takes to complete.
o Average Case: The expected running time across all possible inputs.
Time Complexity
ENUMERATE THE COMMON CASES IN TIME COMPLEXITY AND DIFFERENTIATE THEM
o Best Case: Minimum time an algorithm takes to complete.
o Worst Case: Maximum time an algorithm takes to complete.
o Average Case: The expected running time across all possible inputs.
- refers to the amount of memory an algorithm uses as it runs.
o Example: If an algorithm needs to store additional arrays or temporary variables, its space complexity increases.
Space Complexity
o Example: If an algorithm needs to store additional arrays or temporary variables, its space complexity increases.
Space Complexity
- are used to describe the performance of algorithms when the input size becomes very large. Common notations include:
o Big O (O): Describes the worst-case scenario.
o Omega (Ω): Describes the best-case scenario.
o Theta (Θ): Describes the average-case scenario.
Asymptotic Notation
ENUMERATE THE COMMON NOTATIONS AND DIFFERENTIATE THEM
o Big O (O): Describes the worst-case scenario.
o Omega (Ω): Describes the best-case scenario.
o Theta (Θ): Describes the average-case scenario.
- Data elements that are accessed one after the other in sequence (e.g., accessing elements in an array). However, it’s not always compulsory to store elements sequentially in memory.
Sequential Access
Accessing Elements in an Array
- Each element in an array can be accessed using an index. The index is a numerical value starting at 0 (for most programming languages) that represents the position of an element.
- Example:In the array arr[5] = [10, 20, 30, 40, 50], arr[2] refers to the third element, which is 30.
ADVANTAGES OF ARRAYS
- Arrays allow direct access to elements using their index, making retrieval very efficient.
- Example: Accessing the element at index 4 in an array is instantaneous and does not require searching through the rest of the array.
DISADVANTAGES OF ARRAYS
- Arrays have a fixed size and require contiguous memory space. Inserting or deleting elements can be slow because it may require shifting elements.
- Example: If you delete an element at the beginning of the array, all subsequent elements need to be shifted left.
- Arrays can have multiple dimensions, such as 2D or 3D arrays, allowing data to be stored in a matrix or grid form.
- Example: A 2D array can be visualized as a table with rows and columns (e.g., a chessboard layout).
Multidimensional Arrays
- Example: A 2D array can be visualized as a table with rows and columns (e.g., a chessboard layout).
Multidimensional Arrays
- Arrays are used to store a finite, ordered sequence of elements. This means every element in the array has a specific position or index, which allows for efficient data access based on index numbers.
Arrays as Lists
Relationship Between Values and Indexes
While arrays hold elements in an ordered sequence, there may or may not be any inherent relationship between the value of an element and its position in the array. This depends on how the array is being used.
size of an array
Once an array is created, its size is fixed in most programming languages. You cannot increase or decrease the size of the array during the program’s execution unless you’re working with dynamic data structures like lists in some languages
Array Bounds
- In an array, the Lower Bound is the smallest index, typically starting at 0, and the Upper Bound is the highest index, which depends on the size of the array (size - 1).
Deleting Items from Arrays
- -: When an element is removed from an array, the elements that follow are usually shifted to fill the gap, maintaining the sequence of elements.
- 2D arrays are arrays of arrays and can store data in a matrix form. They are often used to store and manipulate data like strings, which may require multiple rows and columns.
Two-Dimensional Arrays
Traversing Arrays
- When you traverse an array, you examine every element. This is usually necessary for operations such as searching or displaying all elements. There are no shortcuts in this process unless some data structures use optimizations like skipping certain elements.
Inserting in Arrays
- When you insert a new element into an array, the new data is placed in the specified position, potentially shifting other elements to accommodate the insertion. This operation does not replace any existing element unless explicitly stated.
2D Array Storage Efficiency
- In 2D arrays, every row typically needs to have the same number of elements. If not all rows need the same amount of storage, this can result in wasted memory.
Efficiency of Insertion/Deletion in Arrays
- Operations like insertion and deletion in arrays may require moving multiple elements, which can be time-consuming, especially with large arrays. This affects their efficiency.
Manipulating Linked Lists
- Unlike arrays, linked lists do not support direct index-based access. To find or modify an element, you need to traverse the list starting from the head, which involves following the pointers between nodes.
Arrays and Nodes
- Arrays are collections of elements, whereas linked lists are collections of nodes, where each node contains a data element and a reference (or pointer) to the next node in the sequence.
Data Storage in Lists
- Linked lists can store simple or complex data types. Each node may hold various types of data, including objects or structures, making them more flexible in terms of data storage.
Node Structure in Linked Lists
- Each node in a linked list, except the last one, points to the next node. The last node typically contains a null reference or pointer, indicating the end of the list.
Memory Management in Linked Lists
- Linked lists are dynamic structures and allocate memory from a specific area called the heap. This means the memory for each node is allocated as needed during runtime.
Node Placement in Memory
- Unlike arrays, nodes in a linked list are not necessarily placed in contiguous memory locations. The nodes can be scattered across different memory addresses, with each node storing a reference to the next one.
Pointers in Linked Lists
- Linked lists are implemented using pointers or references. Each node stores a pointer to the next node in the list, allowing traversal and manipulation of the list structure.
Traversing Linked Lists
- To access or search for data within a linked list, traversal is required. This involves moving from one node to the next by following the pointers.
Sorting in Linked Lists
- When sorting a linked list, comparison of data occurs between nodes. Depending on the sorting method, either the data itself or the node pointers are adjusted to arrange the nodes in order.
Efficiency of Insertion at the End
- Inserting a node at the end of a linked list often involves traversing the entire list to find the last node. This can take time, especially for long lists, unless a tail pointer is maintained.
- Node Insertion Time Complexity When a node is inserted at the end of a linked list, how many nodes are examined, and what is the time complexity of this operation?
To insert a node at the end of a linked list, you need to traverse the entire list to find the last node. This requires examining n nodes, where n is the number of nodes in the list.
Therefore, the time complexity of inserting a node at the end of a linked list is O(n), or linear time. This means that the time taken for this operation increases linearly with the number of nodes in the list.
-
Traversal Speed
Describe the performance characteristics of traversing through all elements in a linked list. Is it considered fast or slow, and why?
Linked lists are slower than arrays due to indirect memory access and cache misses. However, they are efficient for insertions and deletions at the beginning or middle.
