Category Archives: Lesson

Hash Tables – Hash Attack

Classwork:
1. At classroomSalon.com:
Video 11.3 has questions.
Please type “done” in edmodo.com when you are finished.

2. At edmodo.com:
Hash Attack

Homework:
Bad Hash Function
Parking Problem

NOTE: Classroomsalom.com has gone mobil now!!!!

Hash Tables – Uniform hashing

Classwork:
1. At classroomSalon.com:
Video 11.1 has questions.
Please type “done” in edmodo.com when you are finished.

2. At edmodo.com:
Uniform hashing assumptions:
From Video 11.1:

Coupon collector. Suppose that you have a shuffled deck of cards and you turn them face up, one by one. How many cards do you need to turn up before you have seen one of each suit? This is an example of the famous coupon collector problem. In general, suppose that a trading card company issues trading cards with N different possible cards: how many do you have to collect before you have all N possibilities, assuming that each possibility is equally likely for each card that you collect?

Illustrate the assumption made in the video either mathematically or with program YI_CouponCollector.
NOTE: Be clear and concise

Homework:
At classroomSalon.com:
Video 11.2 has questions.
Please type “done” in edmodo.com when you are finished.

NOTE: Classroomsalom.com has gone mobil now!!!!

K-d Trees Programming Project

Welcome Back from Spring Break

springbee

HT – K-d Trees Checklist

Screen Shot 2015-03-17 at 8.31.58 AM

Checklist

Due date: 3/24/15

Project: HT – K-d Trees Project

Programming Assignment: Kd-Trees

Intro

Worksheet

Coding Tips

HT – Tree Structures Applications

Classwork:
Tree Structures Applications
Videos 9.6, 10.1 and 10.2

Homework:
Look into the next project. Tomorrow we will look at the lesson and video for the project.

Undirected Graphs – Glossary

February 16th, 2016

Glossary. Here are some definitions that we use.
1. A self-loop is an edge that connects a vertex to itself.
2. Two edges are parallel if they connect the same pair of vertices.
3. When an edge connects two vertices, we say that the vertices are adjacent to one another and that the edge is incident on both vertices.
4. The degree of a vertex is the number of edges incident on it.
5. A subgraph is a subset of a graph’s edges (and associated vertices) that constitutes a graph.
6. A path in a graph is a sequence of vertices connected by edges. A simple path is one with no repeated vertices.
7. A cycle is a path (with at least one edge) whose first and last vertices are the same. A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
8. The length of a path or a cycle is its number of edges.
9. We say that one vertex is connected to another if there exists a path that contains both of them.
10. A graph is connected if there is a path from every vertex to every other vertex.
11. A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.
12. An acyclic graph is a graph with no cycles.
13. A tree is an acyclic connected graph.
14. A forest is a disjoint set of trees.
15. A spanning tree of a connected graph is a subgraph that contains all of that graph’s vertices and is a single tree.
16. A spanning forest of a graph is the union of the spanning trees of its connected components.
17. A bipartite graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.