Skip to Main Content
| Brooklyn College Library & Academic IT |CISC Department

CISC 3130 Data Structures: Algorithms

Professor Chuang Spring 2020 OER

What are algorithms?

Algorithms refer to the logistics in manipulating data in these structures, such as searching or sorting. It is a method for solving a problem expressed as a sequence of steps. It serves the role that recipe is used in cooking.

Main Points

  • We are interested in designing good algorithms, so we have to be able to measure the performance.
  • Good algorithms are measured by running time and space usage. This is to say we could measure the space or time complexity required.
  • Often, the metric is the maximum number of operations. The upper bound of possible operations, which is commonly called Big O where O is used to denote the order of growth. 

 

Algorithms

Sorting Algorithms

  • Simple Sorts
  • Divide & Conquer
  • Recursive

Searching Algorithms

  • Linear Search
  • Binary Search

Tree Traversals

  • Depth First Search
  • Binary Search

Suggested Reading

Algorithm Chapter
Linear Search,
Binary Search		 Lafore Ch 2
Bubble Sort,
Insertion Sort,
Selection Sort		 Lafore Ch 3
Quicksort Lafore Ch 7,
CLRS Ch 7
Mergesort Lafore Ch 6,
CLRS Ch
Heapsort

Lafore Ch 12,

CLRS Ch6
Tree Traversal Lafore Ch 8

 

Comparing Sorting Algorithms

Big O notation for algorithm efficiency

Sorting Algorithm Worst Case Best Case In Place? Stability
Bubble Sort O(n2) O(n) Yes Yes
Insertion Sort O(n2) O(n) Yes Yes
Selection Sort O(n2) O(n2) Yes No - When moving selected value,
it introduces a new index.
Mergesort O(nlogn) O(nlogn) No - Requires additional memory for
merge operation.		 Yes
Quicksort O(n2) O(nlogn) Yes No - partitioning based on pivot
values moves elements into
different locations
Heapsort O(nlogn) O(nlogn) Yes No - heapify reshifts nodes in the
heap

 

 

Creative Commons License NC SA 4.0 icon This OER resource is released under Creative Commons Attribution-Non Commercial-ShareAlike 4.0 International License. It was made for the Spring 2020 semester by Professor Katherine Chuang on Data Structures at Brooklyn College, Department of Computer and Information Science.