COMPSCI 61B Lecture Notes - Lecture 25: 2D Computer Graphics, Quadtree, Iterative Deepening Depth-First Search
1 Jun 2017
School
Department
Course
Professor
Document Summary
Write a priority-queue based ai to solve a vast family of problems including. Covers all material up to today with a focus on hashing. 12-2 pm in 273 and 275 soda hall. We say that the nodes are visited" in the given order. Basic idea: traverse deep nodes before shallow ones preorder pseudocode: inorder pseudocode: postorder pseudocode: Preorder traversal: we walk the graph from top going counter-clockwise. Shout every time we pass the left of a node. Inorder traversal: shout when you cross the bottom. Postorder traversal: shout when you cross the right. Avoid rewriting traversal for every task of interest (print, sum lesizes, etc. Runtime of a preorder traversal in terms of n, the number of nodes. Runtime exponential in height of the tree, not number of items. Result of reading the nodes like a book , one level at a time. Goal: visit nodes on 0th level, then 1st, then 2nd, etc.
