Algorithms and Data Structures - Getting Started

This page is part of Programming and CS - Getting Started

Reading

• TutorialsPoint - start with this, it covers the basic data structures and algorithms (material typically covered in CS 201 Programming Structures, CS 202 Data Structures and Algorithms, CS 500 Programming Fundamentals at ISU).
• Introduction to Algorithms - or start with this. This includes both basic data structures and algorithms and further material that is typically covered in CS 458 Algorithms and CS 420 Theory of Computation at ISU.
• Algorithm Design - these are slides to accompany the Algorithm Design textbook. This textbook leans more towards material that is typically covered in CS 458 Algorithms and CS 658 Algorithms II at ISU, and is a fairly modern treatment of algorithms.

Data Structures Basics

For each of the following basic data structures, you should have memorized the algorithms for insert, lookup, delete, the worst-case / average-case / best-case running times (including why the running time is what it is), uses of each data structure, and be able to use the data structure in your programs.

Note - this material is typically covered in CS 201 Programming Structures, CS 202 Data Structures and Algorithms, and CS 500 Programming Fundamentals at ISU.

• Array (unsorted) - O(1) insert, O(n) lookup using linear search, O(1) delete if you have an index to what is being deleted.
• Array (sorted) - O(n) insert, O(log(n)) lookup using binary search, O(n) delete because need to shift to keep in sorted order.
• Linked list - O(1) insert, O(n) lookup using linear search, O(1) delete.
• Arrays / linked lists - used when data is small enough that O(n) running time is acceptable. Code is very simple.
• Stack - stored using a linked list or array, one use is in keeping track of local variables in a running program, another is arithmetic using RPN.
• Queue - stored using a linked list, used when there is a "line" waiting for some resource where the first in the line gets the resource first.
• Binary search tree (not necessarily balanced) - operations are O(height of tree), which can be n in the worst-case of a completely unbalanced tree but is typically O(log(n)) on random data. Code for operations is very simple. BSTs used when data is large enough that array / linked list too slow, preferred over hash table if you might need to consider a range of values (e.g., all people with last name starting with Joh).
• Binary search tree (balanced) - operations are O(height of tree), tree height is kept O(log(n)) by rebalancing/shifting the tree if it becomes too unbalanced.
• Hash table (deal with collisions using chaining/buckets) - operations are O(size of linked list buckets), size of buckets is O(1) if size of hash table chosen appropriately and data is random, operations are n in worst case (all items collide and stay in one bucket). Hash table used when lookup/insert/delete need to be fast and having data stored in sorted order does not matter.
• Hash table (deal with collisions using probing) - performance similar to hash table with chaining/buckets but could be worse as the hash table fills up.
• Heap - operations are O(log(n)), used when need to have access to the largest or smallest item.

Asymptotic Analysis (Big O)

Note - this material is typically covered in CS 201 Programming Structures, CS 202 Data Structures and Algorithms, and CS 500 Programming Fundamentals at ISU.

Algorithms Basics

Note - this material is typically covered in CS 201 Programming Structures, CS 202 Data Structures and Algorithms, and CS 500 Programming Fundamentals at ISU.