- Harvard CS50 - Asymptotic Notation (video)
- Big O Notations (general quick tutorial) (video)
- Big O Notation (and Omega and Theta) - best mathematical explanation (video)
- Skiena:
- A Gentle Introduction to Algorithm Complexity Analysis
- Orders of Growth (video)
- Asymptotics (video)
- UC Berkeley Big O (video)
- UC Berkeley Big Omega (video)
- Amortized Analysis (video)
- Illustrating "Big O" (video)
- TopCoder (includes recurrence relations and master theorem):
- Cheat sheet
-
- Description:
- Implement an array list (mutable array with automatic resizing):
- Practice coding using arrays and pointers, and pointer math to jump to an index instead of using indexing.
- New raw data array with allocated memory
- can allocate int array under the hood, just not use its features
- start with 16, or if starting number is greater, use power of 2 - 16, 32, 64, 128
- Len() - number of items
- Cap() - number of items it can hold
- IsEmpty()
- Get(index) - returns item at given index, blows up if index out of bounds
- Set(index, item) - sets item at given index, blows up if index out of bounds
- Push(item)
- Insert(index, item) - inserts item at index, shifts that index's value and trailing elements to the right
- Prepend(item) - can use insert above at index 0
- Pop() - remove from end, return value
- Delete(index) - delete item at index, shifting all trailing elements left
- Remove(item) - looks for value and removes index holding it (even if in multiple places)
- Find(item) - looks for value and returns first index with that value, -1 if not found
- Resize(newCapacity) // private function
- when you reach capacity, resize to double the size
- when popping an item, if size is 1/4 of capacity, resize to half
- Time
- O(1) to add/remove at end (amortized for allocations for more space), index, or update
- O(n) to insert/remove elsewhere
- Space
- contiguous in memory, so proximity helps performance
- space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)
-
- Description:
- C Code (video) - not the whole video, just portions about Node struct and memory allocation.
- Linked List vs Arrays:
- why you should avoid linked lists (video)
- Gotcha: you need pointer to pointer knowledge: (for when you pass a pointer to a function that may change the address where that pointer points) This page is just to get a grasp on ptr to ptr. I don't recommend this list traversal style. Readability and maintainability suffer due to cleverness.
- Implement (I did with tail pointer & without):
- Size() - returns number of data elements in list
- Empty() - bool returns true if empty
- Get(index) - returns the value of the nth item (starting at 0 for first)
- PushFront(value) - adds an item to the front of the list
- PopFront() - remove front item and return its value
- PushBack(value) - adds an item at the end
- PopBack() - removes end item and returns its value
- Front() - get value of front item
- Back() - get value of end item
- Insert(index, value) - insert value at index, so current item at that index is pointed to by new item at index
- Erase(index) - removes node at given index
- ValueNthfromEnd(n) - returns the value of the node at nth position from the end of the list
- Reverse() - reverses the list
- RemoveValue(value) - removes the first item in the list with this value
- Doubly-linked List
- Description (video)
- No need to implement
-
- Stacks (video)
- Using Stacks Last-In First-Out (video)
- Implement using linked-list:
- Push(value) - pushes an item to top of the stack
- Pop() - removes and returns an item from top of the stack
- Empty()
- Implement using fixed-sized array:
- Push(value) - pushes an item to top of the stack
- Pop() - removes and returns an item from top of the stack
- Empty()
-
- Using Queues First-In First-Out(video)
- Queue (video)
- Circular buffer/FIFO
- Priority Queues (video)
- Implement using linked-list, with tail pointer:
- Enqueue(value) - adds value at position at tail
- Eequeue() - returns value and removes least recently added element (front)
- Empty()
- Implement using fixed-sized array:
- Enqueue(value) - adds item at end of available storage
- Dequeue() - returns value and removes least recently added element
- Empty()
- Cost:
- A bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you'd need the next to last element, causing a full traversal each dequeue
- Enqueue: O(1) (amortized, linked list and array [probing])
- Dequeue: O(1) (linked list and array)
- Empty: O(1) (linked list and array)
-
-
Videos:
-
Online Courses:
-
Implement with array using linear probing
- Hash(key)
- Add(key, value) - if key already exists, update value
- Exists(key)
- Get(key)
- Remove(key)
-
-
- Binary Search (video)
- Binary Search (video)
- Detail
- Implement:
- Binary search (on sorted array of integers)
- Binary search using recursion