itu.algs4.fundamentals package

Submodules

itu.algs4.fundamentals.bag module

class itu.algs4.fundamentals.bag.Bag

Bases: typing.Generic

The Bag class represents a bag (or multiset) of generic items. It supports insertion and iterating over the items in arbitrary order.

This implementation uses a singly linked list with a static nested class Node. See LinkedBag for the version from the textbook that uses a non-static nested class.

The add, is_empty, and size operations take constant time. Iteration takes time proportional to the number of items.

class Node

Bases: typing.Generic

add(item: T) → None

Adds the item to this bag.

Parameters:item – the item to add to this bag

is_empty() → bool

Returns true if this bag is empty.

Returns:true if this bag is empty false otherwise

size() → int

Returns the number of items in this bag.

Returns:the number of items in this bag

itu.algs4.fundamentals.binary_search module

itu.algs4.fundamentals.binary_search.T = ~T

The binary_search module provides a method for binary searching for an item in a sorted array. The index_of operation takes logarithmic time in the worst case.

itu.algs4.fundamentals.binary_search.index_of(a: List[T], key: T)

Returns the index of the specified key in the specified array.

Parameters:

• a – the array of items, must be sorted in ascending order
• key – the search key

Returns:

index of key in array if present -1 otherwise

itu.algs4.fundamentals.binary_search.main()

Reads strings from first input file and sorts them Reads strings from second input file and prints every string not in first input file.

itu.algs4.fundamentals.evaluate module

itu.algs4.fundamentals.evaluate.evaluate()

itu.algs4.fundamentals.java_helper module

itu.algs4.fundamentals.java_helper.java_string_hash(key)

If key is a string, compute its java .hash() code.

Taken from http://garage.pimentech.net/libcommonPython_src_python_libcommon_javastringhashcode/

itu.algs4.fundamentals.java_helper.trailing_zeros(i)

itu.algs4.fundamentals.queue module

class itu.algs4.fundamentals.queue.Node(item: T, next: Optional[Node[T]])

Bases: typing.Generic

class itu.algs4.fundamentals.queue.Queue

Bases: typing.Generic

The Queue class represents a first-in-first-out (FIFO) queue of generic items.

It supports the usual enqueue and dequeue operations, along with methods for peeking at the first item, testing if the queue is empty, and iterating through the items in FIFO order This implementation uses a singly linked list of linked-list nodes The enqueue, dequeue, peek, size, and is_empty operations all take constant time in the worst case

dequeue() → T

Removes and returns the item on this queue that was least recently added. :return: the item on this queue that was least recently added. :raises NoSuchElementException: if this queue is empty

enqueue(item: T) → None

Adds the item to this queue.

Parameters:item – the item to add

is_empty() → bool

Returns true if this queue is empty.

Returns:True if this queue is empty otherwise False Return type:bool

peek() → T

Returns the item least recently added to this queue. :return: the item least recently added to this queue :raises NoSuchElementException: if this queue is empty

size() → int

Returns the number of items in this queue.

Returns:the number of items in this queue Return type:int

itu.algs4.fundamentals.stack module

class itu.algs4.fundamentals.stack.FixedCapacityStack(capacity: int)

Bases: typing.Generic

is_empty() → bool

pop() → T

push(item: T)

size() → int

class itu.algs4.fundamentals.stack.Node

Bases: typing.Generic

class itu.algs4.fundamentals.stack.ResizingArrayStack

Bases: typing.Generic

is_empty() → bool

pop() → T

push(item: T) → None

resize(capacity: int) → None

size() → int

class itu.algs4.fundamentals.stack.Stack

Bases: typing.Generic

The Stack class represents a last-in-first-out (LIFO) stack of generic items. It supports the usual push and pop operations, along with methods for peeking at the top item, testing if the stack is empty, and iterating through the items in LIFO order.

This implementation uses a singly linked list with a static nested class for linked-list nodes. See LinkedStack for the version from the textbook that uses a non-static nested class. See ResizingArrayStack for a version that uses a resizing array. The push, pop, peek, size, and is-empty operations all take constant time in the worst case.

is_empty() → bool

Returns true if this stack is empty.

Returns:true if this stack is empty false otherwise

peek() → T

Returns (but does not remove) the item most recently added to this stack.

Returns:the item most recently added to this stack Raises:ValueError – if this stack is empty

pop() → T

Removes and returns the item most recently added to this stack.

Returns:the item most recently added Raises:ValueError – if this stack is empty

push(item: T) → None

Adds the item to this stack.

Parameters:item – the item to add

size() → int

Returns the number of items in this stack.

Returns:the number of items in this stack

itu.algs4.fundamentals.three_sum module

class itu.algs4.fundamentals.three_sum.ThreeSum

Bases: object

static count(a)

itu.algs4.fundamentals.three_sum_fast module

class itu.algs4.fundamentals.three_sum_fast.ThreeSumFast

Bases: object

static count(a)

itu.algs4.fundamentals.two_sum_fast module

class itu.algs4.fundamentals.two_sum_fast.TwoSumFast

Bases: object

static count(a)

itu.algs4.fundamentals.uf module

The UF module implements several versions of the union-find data structure (also known as the disjoint-sets data type). It supports the union and find operations, along with a connected operation for determining whether two sites are in the same component and a count operation that returns the total number of components.

The union-find data type models connectivity among a set of n sites, named 0 through n-1. The is-connected-to relation must be an equivalence relation:

• Reflexive: p is connected to p.
• Symmetric: If p is connected to q, then q is connected to p.

• Transitive: If p is connected to q and q is connected to r, then

  p is connected to r.

class itu.algs4.fundamentals.uf.QuickFindUF(n: int)

Bases: object

This is an implementation of the union-find data structure - see module documentation for more info.

This implementation uses quick find. Initializing a data structure with n sites takes linear time. Afterwards, the find, connected, and count operations take constant time but the union operation takes linear time.

For additional documentation, see Section 1.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

connected(p: int, q: int) → bool

Returns true if the two sites are in the same component.

Parameters:

• p – the integer representing one site
• q – the integer representing the other site

Returns:

true if the two sites p and q are in the same component; false otherwise

count()

find(p: int) → int

Returns the component identifier for the component containing site p.

Parameters:p – the integer representing one site Returns:the component identifier for the component containing site p

union(p: int, q: int) → None

Merges the component containing site p with the component containing site q.

Parameters:

• p – the integer representing one site
• q – the integer representing the other site

class itu.algs4.fundamentals.uf.QuickUnionUF(n: int)

Bases: object

This is an implementation of the union-find data structure - see module documentation for more info.

This implementation uses quick union. Initializing a data structure with n sites takes linear time. Afterwards, the union, find, and connected operations take linear time (in the worst case) and the count operation takes constant time. For alternate implementations of the same API, see UF, QuickFindUF, and WeightedQuickUnionUF.

For additional documentation, see Section 1.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

connected(p: int, q: int) → bool

Returns true if the two sites are in the same component.

Parameters:

• p – the integer representing one site
• q – the integer representing the other site

Returns:

true if the two sites p and q are in the same component; false otherwise

count() → int

find(p: int) → int

Returns the component identifier for the component containing site p.

Parameters:p – the integer representing one site Returns:the component identifier for the component containing site p

union(p: int, q: int) → None

Merges the component containing site p with the component containing site q.

Parameters:

• p – the integer representing one site
• q – the integer representing the other site

class itu.algs4.fundamentals.uf.UF(n: int)

Bases: object

This is an implementation of the union-find data structure - see module documentation for more info.

This implementation uses weighted quick union by rank with path compression by halving. Initializing a data structure with n sites takes linear time. Afterwards, the union, find, and connected operations take logarithmic time (in the worst case) and the count operation takes constant time. Moreover, the amortized time per union, find, and connected operation has inverse Ackermann complexity.

For additional documentation, see Section 1.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

connected(p: int, q: int) → bool

Returns true if the two sites are in the same component.

Parameters:

• p – the integer representing one site
• q – the integer representing the other site

Returns:

true if the two sites p and q are in the same component; false otherwise

count() → int

find(p: int) → int

Returns the component identifier for the component containing site p.

Parameters:p – the integer representing one site Returns:the component identifier for the component containing site p

union(p: int, q: int) → None

Merges the component containing site p with the component containing site q.

Parameters:

• p – the integer representing one site
• q – the integer representing the other site

class itu.algs4.fundamentals.uf.WeightedQuickUnionUF(n: int)

Bases: object

This is an implementation of the union-find data structure - see module documentation for more info.

This implementation uses weighted quick union by size (without path compression). Initializing a data structure with n sites takes linear time. Afterwards, the union, find, and connected operations take logarithmic time (in the worst case) and the count operation takes constant time. For alternate implementations of the same API, see UF, QuickFindUF, and QuickUnionUF.

For additional documentation, see Section 1.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

connected(p: int, q: int) → bool

Returns true if the two sites are in the same component.

Parameters:

• p – the integer representing one site
• q – the integer representing the other site

Returns:

true if the two sites p and q are in the same component; false otherwise

count() → int

find(p: int) → int

Returns the component identifier for the component containing site p.

Parameters:p – the integer representing one site Returns:the component identifier for the component containing site p

union(p: int, q: int) → None

Merges the component containing site p with the component containing site q.

Parameters:

• p – the integer representing one site
• q – the integer representing the other site

Module contents