Scribd
Upload
8 views2 pages

Binary Search Trees and Graphs in CS 211

This document covers Binary Search Trees (BSTs) and their properties, including efficient insertion, deletion, and search operations. It also introduces graphs using adjacency lists and presents a problem related to graph algorithms, specifically the Muddy City problem, which involves determining the minimum number of paving stones needed for connectivity. Students are prompted to analyze a given tree and graph, and to strategize solutions for the graph problem.

Uploaded by

musabilal098
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

Binary Search Trees and Graphs in CS 211

This document covers Binary Search Trees (BSTs) and their properties, including efficient insertion, deletion, and search operations. It also introduces graphs using adjacency lists and presents a problem related to graph algorithms, specifically the Muddy City problem, which involves determining the minimum number of paving stones needed for connectivity. Students are prompted to analyze a given tree and graph, and to strategize solutions for the graph problem.

Uploaded by

musabilal098
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CS 211 - Programming Practicum

Module 10b Lecture Activity

Name: __________________________________________ UIN: ________________________

Intro to Trees – Binary Search Trees (BSTs)


A Binary Search Tree is a data structure that
provides efficient insertion/deletion (better than
arrays) AND search (better than linked lists). Each
node has up to two children (i.e. binary).
Additionally, the elements are guaranteed to have a
certain order: for an arbitrary node with value X, all
values in its left subtree are less than X and all
values in its right subtree are greater than X. For the
tree shown…
How many nodes are there? N =
Is it a BST? If not, which two nodes must be swapped?
Once the tree is a BST, describe how it can efficiently be used for searching. Ex: is 61 in
the tree? Is 49 in the tree? What is the max # of comparisons for the search process?

Intro to Graphs – Adjacency Lists


Sketch the graph, provided with this
Adjacency List representation:

1
CS 211 - Programming Practicum
Module 10b Lecture Activity

Name: __________________________________________ UIN: ________________________

Graph – Adjacency List (continued): Once the graph is drawn, label the vertices as follows: 0 = “Grass”, 1 =
“Grasshopper”, 2 = “Hawk”, 3 = “Lizard”, 4 = “Rabbit”, 5 = “Snake”, 6 = Mouse. Does this look familiar? Did you
realize you had already worked with Graphs and Adjacency Lists in this course!?!

Intro to Graph Algorithms


The Muddy City problem can be represented by a graph. Each house is a node, and each
possible road is an edge. The weight of the edges represents the cost of paving that road.
We seek to determine the minimum number of paving stones needed to make each home
reachable through some path. Come up with a strategy for this problem. Describe your
approach in the space below. Using diagrams if helpful. You may want to detail only a few steps
of the process. What number did you get for the minimum number of paving stones?

You might also like