Depth-First Search Variations and A*
Best-First Search as a Generalized Search Algorithm
Breadth-first search: (the smaller depth the smaller cost)
Depth-first search: (the bigger the depth the smaller relative cost)
Which frontier node would we visit first?
The one with the lowest estim...
Artificial Intelligence Algorithms
Artificial intelligence can be used to automatically create models from data.
Typically not guaranteed to find perfect models, but may be able to find good models, depending on the difficulty of the problem and on the data available.
Good for problems where...
Introduction to Operating Systems
1. What happens when a program runs?
It executes instructions.
Von Neumann model of computation
2. Making System Easy to Use
Body of Software: Operating System (OS)
Responsibility
Programs appear to run simultaneously.
Allowing program to share m...
Basic Set Theory
Set
no duplicate element.
Subset
. A is a subset of B if every element in A is contained in B
Proper Subset
. Set A is said to be a proper subset of B if every element in A is contained in B AND .
Union
. The Union of two sets A and B is the set that contains all the...
Hash tables & Graphic
Hash Tables
1. Summary
A hash table consists of
an array arr for storing the values.
a hash function hash(key).
a mechanism for dealing with collisions.
Basic operations
put(key, value)
delete(key)
get(key)
Disclaimer: We will consider a simplified sit...
Sorting
Selection Sort
1. Algorithm:
Split the array in two parts such that:
the first part of the array is sorted.
the second part contains elements than the elements in the first part.
Pick the smallest element from the second part.
Swap it with the element on the position right a...
Priority Queues
(Max) Priority Queue = Max-In-First-Out
1. Basic Operations
insert(value,priority)
deleteMax()
update(value,priority)
isEmpty()
2. Naïve implementation: Array
Store in an array, ordered by priority (the highest at the end):
insert(value, priority) - find the posit...
Time Complexity
Average Case complexity = average complexity over all possible inputs/situations (we need to know the likelihood of each of the input!)
Worst Case complexity = the worst complexity over all possible inputs/situations
Best Case complexity (mostly useless) = the best complexity...
Stack & Queue
Stacks
Stack is an abstract data type, LIFOs (Last-In-First-Out).
1. Basic operation
push(x) = insert_beg
pop() = delete_beg
is_empty() = is_empty (for linked list)
2. Stacks as arrays
To avoid calling allocate_memory all the time, we need to know the maximum size of...
