data structure

\documentclass[12pt]{article} \usepackage[letterpaper, margin=0.5in]{geometry} \geometry{letterpaper} \usepackage[parfill]{parskip} \usepackage{framed} \usepackage{graphicx} \usepackage{amsmath} \usepackage{amssymb} \usepackage{qtree} \usepackage{makecell} \usepackage{mathtools} \DeclarePairedDelimiter\ceil{\lceil}{\rceil} \DeclarePairedDelimiter\floor{\lfloor}{\rfloor} \DeclarePairedDelimiter\abs{\lvert}{\rvert}% \DeclarePairedDelimiter\norm{\lVert}{\rVert}% % \abs & \norm resizes brackets, starred version doesn’t \makeatletter \let\oldabs\abs \def\abs{\@ifstar{\oldabs}{\oldabs*}} % \let\oldnorm\norm \def\norm{\@ifstar{\oldnorm}{\oldnorm*}} \makeatother \newcommand\tab[1][0.25cm]{\hspace*{#1}} \newcommand\imp{\rightarrow} \newcommand\thfr{\tab \therefore \tab} \newcommand\sameas{\tab \equiv \tab} \title{CSC263 – Week 2, Lecture 1} \author{Cristyn Howard} \date{Monday, January 15, 2018} \begin{document} \maketitle \begin{center}

CSC263H Data Structures and Analysis Note on BFS University of Toronto BFS(s) Computes the Shortest Paths from s – Proof Sketch Recall that during the execution of a BFS started from s (denoted BFS(s)), if a node u discovers a node v, then d[v] is set to d[u] + 1. Initially, d[s] is set to

Disjoint sets Disjoint set ADT • Maintainsacollection!={S1,…,Sk}ofdisjointsets • Eachsetisidentifiedbyarepresentative,whichis an element of the set • Operations: – MAKE-SET(x): creates a new set containing only x, and makes x the representative – FIND-SET(x): returns the representative of x’s set – UNION(x, y): merges the sets containing x and y, and chooses a new representative • Note:Noduplicateelementsareallowed!