1.5: Units

Last updated
Save as PDF

Page ID: 49357

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Unit 1: Fundamental Design and Analysis Techniques

This unit introduces the basic concepts of algorithm design and analysis and associated techniques. The need for analyzing the time and space complexity of algorithms is articulated and the notations for describing algorithm complexity are presented. Also the fundamental solution design methods are discussed as well as demonstrated including the iteration, recursion, recursive backtracking and dynamic programming.

Unit 2: Searching, Binary Search Trees and Heaps

This unit presents the search problem which is one of the most fundamental problems in computer science and presents the searching algorithms. It further discusses the tree based advanced data structures, the binary search tree and the heaps.

Unit 3: Sorting Algorithms

Efficient sorting is important to optimizing the use of other algorithms, such as a search algorithm which may require a sorted input. This unit explores various sorting algorithms based on their sorting method category, that is, the selection, insertion, merging and partitioning methods.

Unit 4: Hash Tables, Graphs and Graph Algorithms

This unit explores more advanced data structures, the hash tables and graphs, and presents some of their associated algorithms. The hash table data structure stores key / value pairs and uses a hash function to compute an index into an array where the element is being inserted or searched. Graphs can be used to model an arbitrary network with nodes representing network items and edges connecting pairs of nodes to represent a relationship.