Algorithms, Data Structures, and Numerical Methods

Algorithms, Data Structures, and Numerical Methods form the bedrock of computer science, influencing everything from efficient data management to complex problem-solving. This guide delves into key concepts from these fields, providing insights relevant for students tackling challenging assignments and preparing for exams like the KIV/ZEP-E.

Understanding Algorithms, Data Structures, and Numerical Methods for Students

For students diving into computer science, a solid grasp of Algorithms, Data Structures, and Numerical Methods is crucial. These areas provide the tools to organize information efficiently, design effective problem-solving strategies, and perform complex calculations with precision. Let's break down some core challenges and solutions from these fields.

Practical Application: Elisa's Influencer Optimization Problem

Consider the scenario of Elisa, a VŠCHT student, who aims to maximize her social media "likes" by shooting selfies in a park. This problem serves as an excellent case study for applying algorithms and data structures to real-world optimization challenges. Elisa's constraints include a daily time limit (90 minutes in the park, 30 minutes for shooting), varied movement speeds (roads, off-road, overgrown, swimming), and specific location rules (100m from roads, unique locations, 50m distance for distinct locations).

Designing Data Structures for Park Representation

To effectively model Elisa's park scenario, specific data structures are essential. A vector map of the park, represented as a set of polygons, is provided. These polygons define different terrain types like water, overgrown parts, and general regions. Each region also has an associated "likes" value.

Candidate locations for shooting must be at least 100 meters away from the nearest road. Here's a possible data structure approach:

• Graph Representation: The park can be modeled as a graph where nodes represent navigable points (e.g., a fine grid, or specific points of interest) and edges represent paths between them. Edges would have weights based on distance and Elisa's speed in that terrain type.
• Polygon Data:
• Water_Polygons: A list of polygons defining water bodies.
• Overgrown_Polygons: A list of polygons defining overgrown areas.
• Region_Polygons: A list of polygons, each with an associated likes value.
• Road_Segments: A collection of line segments or polygons representing roads.
• Location Database: A data structure (e.g., a spatial tree like a Quadtree or K-d tree) to store potential shooting locations, each identified by coordinates and an ID. This facilitates efficient querying for proximity and uniqueness.

Algorithm for Expected Likes

An algorithm to return the expected number of likes for a given location (M) would involve:

1. Input: Location M (coordinates).
2. Process: Iterate through Region_Polygons. For each polygon, check if location M lies within its boundaries.
3. Output: If M is within a region polygon, return its associated likes value. If M is not in any defined region (or an invalid region), return 0 or an error.

Shortest Path Algorithm

To find the shortest path from a park gate (A) to a given location (M) and back to another park gate (B), a graph traversal algorithm is needed. Considering varying speeds and potentially large graphs, a variant of Dijkstra's Algorithm or A* search is suitable.

1. Graph Construction: Create a weighted graph where nodes are points in the park (e.g., intersections, grid points) and edge weights are travel times (distance / speed). Remember to factor in 5 minutes for swimsuit changes when crossing water bodies.
2. Path A to M: Run Dijkstra's from gate A to location M to find the minimum travel time.
3. Path M to B: Run Dijkstra's from location M to gate B to find the minimum travel time.
4. Total Time: Sum the travel times for A->M and M->B.

Location Validity Algorithm

An algorithm to decide if a given location (M) meets rules 3 and 4 (at least 100m from nearest road, and unique within 50m):

1. Rule 3 (Distance from Road):

• For location M, calculate the minimum distance to all Road_Segments.
• If this minimum distance is less than 100m, the location is invalid.

2. Rule 4 (Uniqueness):

• Maintain a record of Previously_Shot_Locations.
• For location M, check if there is any location L in Previously_Shot_Locations such that the distance between M and L is 50m or less.
• If such a location exists, M is not unique for this month and is invalid.

Overall Optimization Method for Elisa

To maximize Elisa's "likes" in one month, the following method can be designed, using the algorithms described above:

1. Identify All Potential Locations: Generate a set of candidate points within all Region_Polygons that meet the 100m road distance criterion.
2. Calculate Likes & Travel Time: For each valid candidate location:

• Calculate its expected_likes.
• Calculate the shortest_travel_time (gate A to location M to gate B). Note that Elisa has only 2 hours (120 minutes) for a part-time job, but can spend max 90 minutes in the park. The shooting itself takes 30 minutes, so total in-park time for travel and shooting is 90 minutes.

3. Filter by Time: Discard locations where shortest_travel_time + 30 minutes (shooting) > 90 minutes (daily park limit).
4. Greedy Selection (or Dynamic Programming): Sort the remaining valid locations by their likes_per_minute (expected likes / total time in park). Iterate daily for one month, selecting the highest-ranked location that has not been shot within 50m of any previously selected location that month, until the daily 90-minute park limit is reached or all valid locations are exhausted.
5. Monthly Optimization: Since locations can only be shot once per month, and uniqueness is based on a 50m radius, the greedy approach might need refinement. A more robust solution might involve a maximum bipartite matching or a flow network approach if the number of days and potential locations are significant, or a sophisticated scheduling algorithm.

Time and Memory Complexity

Analyzing the complexity of such a system is vital:

• Preprocessing:
• Graph construction: O(V + E) for a grid graph (V nodes, E edges). Creating polygons from raw data, O(P*N) where P is number of polygons and N average vertices.
• Identifying initial candidate locations: O(R * N_points * D_road) where R is regions, N_points is points in region, D_road is distance check to road segments.
• Running:
• Shortest path (Dijkstra): O(E + V log V) or O(E log V) depending on priority queue implementation.
• Location validity: O(N_roads) for distance to roads, O(K) for uniqueness where K is previously shot locations.
• Overall optimization (daily selection): Depends on the chosen scheduling algorithm. A greedy approach would be faster, O(L log L) for sorting L locations, but may not be globally optimal.

Asymptotic Complexity and Algorithm Analysis

Beyond practical applications, a theoretical understanding of algorithm efficiency is paramount. Asymptotic complexity describes how the running time or space requirements of an algorithm grow with the input size (n).

Solving Recurrence Relations for Time Complexity

Recurrence relations are used to express the time complexity of recursive algorithms. The Master Theorem is a powerful tool to solve many of these.

• T(n) = 7T(n/4) + n^2: Here a=7, b=4, f(n)=n^2. Compare f(n) with n^(log_b a) = n^(log_4 7) which is approximately n^(1.4). Since n^2 is polynomially larger than n^(log_4 7), the complexity is Θ(n^2).
• T(n) = 3T(n/10) + n: Here a=3, b=10, f(n)=n. Compare f(n) with n^(log_b a) = n^(log_10 3) which is approximately n^(0.47). Since n is polynomially larger than n^(log_10 3), the complexity is Θ(n).
• T(n) = 9T(n/3) + n^2: Here a=9, b=3, f(n)=n^2. Compare f(n) with n^(log_b a) = n^(log_3 9) = n^2. Since f(n) is asymptotically equal to n^(log_b a), the complexity is Θ(n^2 log n).
• T(n) = 7T(n/2) + n^2: Here a=7, b=2, f(n)=n^2. Compare f(n) with n^(log_b a) = n^(log_2 7) which is approximately n^(2.8). Since n^(log_2 7) is polynomially larger than n^2, the complexity is Θ(n^(log_2 7)).
• T(n) = T(√n) + 2: This can be solved by changing variables. Let n = 2^k, so √n = 2^(k/2). Then T(2^k) = T(2^(k/2)) + 2. Let S(k) = T(2^k), so S(k) = S(k/2) + 2. Using Master Theorem (a=1, b=2, f(k)=2), this is Θ(log k). Substituting back k = log n, the complexity is Θ(log log n).

Big O Notation Proofs

Big O notation describes the upper bound of an algorithm's growth rate.

• a) 2^(n+1) = O(2^n): True. We need to find constants c > 0 and n_0 such that for all n >= n_0, 2^(n+1) <= c * 2^n. We know 2^(n+1) = 2 * 2^n. So, if we choose c=2, then 2 * 2^n <= 2 * 2^n is true for all n >= 1. Thus, 2^(n+1) = O(2^n).
• b) 2^(2n) = O(2^n): False. We need to find constants c > 0 and n_0 such that for all n >= n_0, 2^(2n) <= c * 2^n. We know 2^(2n) = (2^n)^2 = 2^n * 2^n. If we assume 2^n * 2^n <= c * 2^n, this implies 2^n <= c. However, 2^n grows infinitely, so there is no fixed constant c that can bound 2^n for all large n. Therefore, 2^(2n) is not O(2^n).

Primality Test Algorithm Analysis

Consider a simple primality test algorithm that checks for divisibility by integers from 2 up to √n.

Input: An integer n >= 2 Output: true, if n is prime and false otherwise

1. s = ⌊√n⌋
2. for i = 2 to s do
3. if n is divisible by i then return false
4. end for
5. return true

• a) Complexity:
• Worst-case (O(f(n))): Occurs when n is a prime number, as the loop runs from 2 up to √n without finding any divisors. The number of iterations is approximately √n. Thus, the worst-case complexity is O(√n).
• Best-case (Ω(g(n))): Occurs when n is an even number (e.g., n=4). The loop immediately checks i=2, finds n is divisible by 2, and returns false. This takes a constant number of operations. Thus, the best-case complexity is Ω(1).
• b) Reducing Divisions:
• Optimization 1: After checking for divisibility by 2 (if n is even, return false immediately), subsequent checks can skip all even numbers. The loop can then start from i=3 and increment by 2 (i.e., i = i + 2). This effectively halves the number of iterations.
• Optimization 2: Further, after checking 2 and 3, all other primes (except 2 and 3) are of the form 6k ± 1. This means you can iterate by checking 5, then 7, then 11, then 13, etc., by stepping +2, +4, +2, +4... (e.g., check 5, skip 6, check 7, skip 8,9,10, check 11, etc.). This significantly reduces the number of division checks.

Impact of Time Complexities

Understanding the practical implications of different time complexities is crucial. A program performing operations at 1 nanosecond per operation demonstrates how quickly efficiency degrades for larger inputs.

Note: µs = microseconds, ms = milliseconds, s = seconds, hrs = hours, days = days, years = years. Times are rounded for readability.

This table vividly illustrates why polynomial and exponential complexities become impractical for large 'n'.

Ordering Functions by Rate of Growth

Ordering functions by their rate of growth (from fastest to slowest, g₁ = Ω(g₂)) helps in understanding the dominance of different complexities:

1. 2^(2n)
2. (n+1)!
3. n!
4. (3/2)^n
5. n * 2^n
6. 2^n
7. n^n
8. n^3
9. n^2
10. (log n)!
11. n log log n
12. n * log n
13. √n = (√2)^log n
14. n^(1/log n)
15. log(n!)
16. log^2 n
17. (log n)^log n
18. 4^(log n) = n^2 (This is equivalent to n^2 due to a^(log_b c) = c^(log_b a) and 4^(log_2 n) = n^(log_2 4) = n^2)
19. log n
20. log log n
21. √log n
22. 2^(√2 * log n) = n^(√2/log n)
23. 1
24. 1 / (log log n)
25. 1 / n

Practical Algorithm Design Challenges

Several practical problems highlight the need for clever algorithm design.

Leftmost Nearest Smaller Element

Given an array A of distinct integers, for each element A[i], find the index j such that j < i, A[j] < A[i], and there is no k where j < k < i and A[k] < A[i]. This is finding the leftmost nearest smaller element.

• a) Example: For A = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.
• For A[1]=8, A[0]=0 is the leftmost nearest smaller. Index: 0.
• For A[2]=4, A[0]=0 is the leftmost nearest smaller. Index: 0.
• For A[3]=12, A[2]=4 is the leftmost nearest smaller. Index: 2. *...and so on.
• b) Θ(n) Algorithm: A stack-based approach can solve this in Θ(n) time. Iterate through the array. Maintain a monotonically increasing stack of elements encountered so far. When processing A[i], pop elements from the stack that are greater than A[i]. The top of the stack (if not empty) will be the leftmost nearest smaller element. Then push A[i] onto the stack.

Factorial Product Comparison

Given two arrays A and B of integers (0-9), design an efficient algorithm to decide if their factorial products are the same. A factorial product of A = {0, 4, 2, 7} is 0! * 4! * 2! * 7!.

Hint: Do not calculate the factorial product directly, as it can be astronomically large. Instead, think about the prime factorization of factorials.

1. Prime Factorization: For any number n!, its prime factorization contains specific powers of primes. For example, 4! = 24 = 2^3 * 3^1. 7! = 5040 = 2^4 * 3^2 * 5^1 * 7^1.
2. Algorithm: For each array (A and B), create a count of the powers of prime factors (e.g., 2, 3, 5, 7) that appear in the factorial product. For A = {0, 4, 2, 7}: 0! = 1, 4! = 2^3 * 3^1, 2! = 2^1, 7! = 2^4 * 3^2 * 5^1 * 7^1. Sum the exponents for each prime: 2^(3+1+4), 3^(1+2), 5^1, 7^1. Compare these total prime exponent counts for array A with those for array B. If all prime factor counts match, their factorial products are the same. This avoids large number computations.

Maximum Non-overlapping Activities

Given a list of activities with start and end times, find the maximum number of non-overlapping activities. This is a classic greedy algorithm problem.

1. Sort: Sort all activities by their finish times in ascending order.
2. Select: Select the first activity (which has the earliest finish time).
3. Iterate: Iterate through the remaining activities. For each activity, if its start time is greater than or equal to the finish time of the last selected activity, select it.
4. Count: The count of selected activities is the maximum number of non-overlapping activities.

Example from materials: F(15,17), A(9,11), H(16,18), C(11,13), G(8,10), E(14,16), B(10,12), D(13,15).

Sorted by end time: G(8,10), A(9,11), B(10,12), C(11,13), D(13,15), E(14,16), F(15,17), H(16,18)

Selected activities:

1. G(8,10)
2. A(9,11) - no, overlaps with G
3. B(10,12) - yes, starts at 10, G ends at 10. (Selected: G, B)
4. C(11,13) - no, overlaps with B
5. D(13,15) - yes, starts at 13, B ends at 12. (Selected: G, B, D)
6. E(14,16) - no, overlaps with D
7. F(15,17) - no, overlaps with D
8. H(16,18) - yes, starts at 16, D ends at 15. (Selected: G, B, D, H)

Maximum number of activities: 4 (G, B, D, H).

Numerical Methods: Derivatives and Summation

Numerical methods are techniques used to approximate mathematical problems. They are crucial when analytical solutions are impossible or impractical.

Numerical Derivative of sin(x)

Computing the derivative of sin(x) numerically using the definition f'(x) = lim (h→0) (f(x+h) - f(x)) / h highlights challenges with floating-point arithmetic.

• a) Calculation for x = π with h = 1e-16: When h is very small, the subtraction f(x+h) - f(x) can suffer from catastrophic cancellation due to the limited precision of floating-point numbers (IEEE 754 double). For x = π, f(x) = sin(π) = 0. f(x+h) = sin(π+h). If h is tiny, sin(π+h) is very close to 0. Subtracting two very small, very close numbers can lead to a significant loss of precision, resulting in an inaccurate derivative compared to the analytical cos(π) = -1.
• b) Minimizing Error (without cos(x)): Using goniometric formulas to transform the expression can reduce error. sin(x+h) - sin(x) = 2 * cos(x + h/2) * sin(h/2). So, (sin(x+h) - sin(x)) / h = (2 * cos(x + h/2) * sin(h/2)) / h. Since lim (h→0) sin(h/2) / (h/2) = 1, the expression approaches cos(x). This form avoids direct subtraction of two nearly equal numbers, thus mitigating cancellation error and improving accuracy even with small h.

Summation of 1/i

Calculating ∑(1/i) from i=1 to n for a large n (e.g., 1,000,000) using floating-point numbers demonstrates the importance of summation order and specialized algorithms.

• a) Standard Loop (1 to n vs. n down to 1):
• From 1 to n: 1/1 + 1/2 + 1/3 +... + 1/1,000,000. This adds large numbers to progressively smaller numbers. When a large sum has already accumulated, adding very small numbers (like 1/1,000,000) might not change the sum due to precision limits (the small number gets