Computer Science Study Notes Help

Data Structures and Algorithms

In the following sections, we will explore more about Data Structures and Algorithms.

In the meantime, these topics will also serve as an introductory part to Java Programming.

1 Data Structures and Algorithms Overview

1.1 Data Storage & Logical Structures

1.1.1 Data Storage Structures

  1. Sequential Storage Structures:

    • Linear list

    • Array

    • Vector

  2. Linked Storage Structure

    • Linked list

  3. Index Storage Structure

    • B-Tree/B+-Tree

  4. Hashing Storage Structure

    • Hash table

1.1.2 Data Logical Structures

  1. Set

  2. Linear

  3. Tree

  4. Graph

1.2 Mathematical Models

Simplifications:

  1. Cost Model: Use some basic operations as a proxy for running time.

    Operation

    Frequency

    Variable declaration

    Assignment statement

    Less than compare

    Equal to compare

    Array access

    Increment

    to

    • Estimate running time (or memory) as a function of input size

    • Ignore lower order terms.

      • When is large, terms are negligible.

      • When is small, we don't care.

1.3 Order-of-Growth Classifications

1.3.1 Common Classifications

Order of growth

Name

Typical code Framework

Decription

Example

T(2N)/T(N)

Constant

a = b + c;

statement

add two numbers

Logarithmic

while (N > 1) {N = N / 2; ...}

divide in half

binary search

Linear

for (int i = 0; i < N; i++) {...}

loop

find the maximum

2

Linearithmatic

see mergesort lecture

divide and conquer

mergesort

Quadratic

for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {...}

double loop

check all pairs

Cubic

for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) {...}

triple loop

check all triples

8

Exponential

see combinatorial search lecture

exhaustive search

check all subsets

T(N)

Property: Binary search uses at most to search in a sorted array of size .

Proof:

number of compares to binary search in a sorted subarray of size .

Binary Seach

  1. Compare key against middle entry.

  2. Too small, go left.

  3. Too big, go right.

  4. Equal, found.

public static int binarySearch(int[] a, int key) { int lo = 0; int hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (key < a[mid]) { hi = mid - 1; } else if (key > a[mid]) { lo = mid + 1; } else { return mid; } } return -1; }
#include <vector> int binarySearch(std::vector<int> arr, int x) { int l = 0, r = arr.size() - 1; while (l <= r) { int m = l + (r - l) / 2; if (arr[m] == x) { return m; } if (arr[m] < x) { l = m + 1; } else { r = m - 1; } } return -1; }
def binary_search(arr, x): l, r = 0, len(arr) - 1 while l <= r: m = l + (r - l) // 2 if arr[m] == x: return m if arr[m] < x: l = m + 1 else: r = m - 1 return -1

1.3.3 3-Sum

Leetcode 15: 3Sum

Description:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

3-Sum

  1. Sort the (distinct) numbers.

  2. For each pair of numbers a[i] and a[j], binary search for -(a[i] + a[j]).

Analysis: Order of growth is

  • Step 1: with insertion sort.

  • Step 2: with binary search.

Better Algorithm: Sorting & Two pointers =>

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { public Solution() { } public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; Arrays.sort(nums); List<List<Integer>> answer = new ArrayList<>(); for (int first = 0; first < n; ++first) { if (first > 0 && nums[first] == nums[first - 1]) { continue; } int third = n - 1; int target = -nums[first]; for (int second = first + 1; second < n; ++second) { if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } while (second < third && nums[second] + nums[third] > target) { --third; } if (second == third) { break; } if (nums[second] + nums[third] == target) { List<Integer> list = new ArrayList<>(); list.add(nums[first]); list.add(nums[second]); list.add(nums[third]); answer.add(list); } } } return answer; } }
#include <vector> #include <algorithm> std::vector<std::vector<int>> threeSum(std::vector<int>& nums) { const int n = static_cast<int>(nums.size()); std::sort(nums.begin(), nums.end()); std::vector<std::vector<int>> answer; for (int first = 0; first < n; first++) { if (first > 0 && nums[first] == nums[first - 1]) { continue; } int third = n - 1; const int target = -nums[first]; for (int second = first + 1; second < n; second++) { if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } while (second < third && nums[second] + nums[third] > target) { --third; } if (second == third) { break; } if (nums[second] + nums[third] == target) { answer.emplace_back(std::vector<int>{nums[first], nums[second], nums[third]}); } } } return answer; }
from typing import List def threeSum(nums: List[int]) -> List[List[int]]: n = len(nums) nums.sort() ans = list() for first in range(n): if first > 0 and nums[first] == nums[first - 1]: continue third = n - 1 target = -nums[first] for second in range(first + 1, n): if second > first + 1 and nums[second] == nums[second - 1]: continue while second < third and nums[second] + nums[third] > target: third -= 1 if second == third: break if nums[second] + nums[third] == target: ans.append([nums[first], nums[second], nums[third]]) return ans

1.4 Theory of Algorithms

Notion

Formal Definition

Provides

Shorthand for

Example

Used to

Big Theta

means there are positive constants and such that

asymptotic order of growth

Classify Algorithms

Big Oh

means there is a positive constant such that

and smaller

Develop Upper Bounds

Big Omega

means there is a positive constant such that

and larger

Develop Lower Bounds

Last modified: 25 November 2024
x86-64 ArchitecturePart Ⅰ