8.4: Unit Summary

Last updated
Save as PDF

Page ID: 47929

\( \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}}\)

In this unit we presented the searching algorithm and two advanced data structures, the binary search tree and the heap. Two searching algorithms were presented, the sequential search and binary search. The binary search algorithm is generally more efficient than sequential search, although it requires that the input collection be sorted.

The binary search tree operations were presented. The binary search tree data structure is of practical interest due to the efficiency of its basic operations including search and insert that make it attractive for implementing dictionaries and priority queues.

The heap data structure was categorised into two main types, max heap and min heap. For each heap type the operations for building a heap from an array were presented. Heaps are generally useful in priority setting applications through exploiting smallest or largest node in the tree as we can extract these node very efficiently using heaps.

Unit Assessment

Check your understanding!

General Programming Exercises

Suppose you are given a sorted array with possible duplicate elements within it. Write a program that finds the last occurrence of a given input item (assuming the given item exists in the given array).

Write a program that reads strings (words) as command line arguments and inserts them into a binary search tree and outputs them in in-order fashion. (You should be able to use your program with files by running your program with the standard input redirected from a file)

Create a binary heap with a limited heap size. That is, the heap should keep track of a fixed number of most important items (say n). If the heap grows in size to more than n items the least important item should be dropped.

Answers

mailto:njulumi@gmail.com

Grading Scheme

As per the offering Institution grading policy.

Unit Readings and Other Resources

The readings in this unit are to be found at course level readings and other resources.