DOC PREVIEW
SJSU CS 146 - Midterm 2 Exam Study Guide

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Midterm 2 Exam Study GuideEulerian and Hamiltonian GraphsMidterm 2 Exam Study Guide The Midterm is on Thursday, April 4, 2002 at the regular lecture time and place. 1. Analysis of recursion o Recurrence relations  Finding a closed form by repeated substitution  Proving the closed form by induction 2. Linear data structures. Arrays, lists, stacks, queues. Array and linked structure implementations of lists, stacks, queues. Array of nodes and dynamic pointer implementations of linked structures. 3. Trees. General and binary trees. Representations and traversals. General trees as binarytrees. Binary search trees. Applications. - Trees o Definition and terminology  e.g. degree of a node, leaf, child, parent, sibling, path, length of a path, level or depth of a node, height of a node, height of a tree, ancestor vs. proper ancestor, descendent vs. proper descendent  Tree traversals  Breadth-first traversal  Depth-first traversal  Preorder, postorder, inorder  Expression trees 4. Algorithm design techniques. Greedy methods, priority queue search, exhaustive search, divide and conquer, dynamic programming. Recursion. The influence of data structure on algorithm performance. 5. Graphs and digraphs. Representions. Breadth and depth first searches. Connectivity algorithms. Shortest path. Minimal spanning tree. The union find problem. Hamiltonian path and travelling salesperson problems..-o Directed acyclic graphs (DAG's) o Undirected graphs o Terminology differences between undirected and directed graphs  Edges both emanate from and are incident on vertices  Degree = in-degree = out-degree o Vertex- and edge-weighted graphso Connectedness and how to test for it  Connectedness of an undirected graph  Strong connectedness of a directed graph  Weak connectedness of a directed graph  Underlying undirected graph of a directed graph o Graph implementation  Adjacency matrix  Adjacency lists  When matrix is better than list, when list is better than matrix o Graph traversal  Depth-first traversal  How algorithm works  Running time for adjacency lists, matrices  Breadth-first traversal  How algorithm works  Running time for adjacency lists, matrices - Cycle Detection using Depth-first Search - Spanning trees, and fact that DFS and BFS can be used to construct spanning treeso Topological order  How algorithm works  Running time for adjacency lists, matrices o Other applications of depth-first traversal  Testing for cycles in a directed graph  Testing for connectedness of an undirected graph  Testing for strong connectedness of a directed graph  Testing for weak connectedness of a directed graph - Given a problem, design an algorithm for solving it. For example, o Given a graph Gand a vertex ss find all vertices at distance k from s. o Given a graph G and two vertices s and t, find a path of length at most k between s and t. o Given an undirected graph G, decide whether G has a cycle. o Given a graph G, a set of vertices S, and a vertex t (t not in S), find the vertex in S that is closest to t. o Given a graph G and a vertex s, find the vertex that is farthest from s. o Given two binary trees, decide whether they are the same.- Compute the time complexity of an algorithm. For example, compute the time complexity of the above algorithms.- Dijkstra's algorithm builds shortest paths from a given vertex s to the other vertices in the graph. These paths are computed in increasing order of length. Why is it more difficult to build the paths in decreasing order of length? - Given a graph show how Dijkstra's algorithm finds shortest paths.Binary Tree ADT - Recursive Definition - Concept that this is a position-based ADT - Compare merits and simulate operations on both array-based and reference-based representations. - How to save and restore a binary tree to its original shape Binary Seach Tree ADT - Recursive Definition - Concept that this is a value-based ADT - What are the basic operations allowed (and which operations of the binary tree are NOT allowed)? - Why did we need KeyedItem? (What possible violation of the ADTdoes this solve.) - The BST Search Algorithm: be able to simulate it. - Insertion and how this uses the search algorithm. - Deletion: how it uses the search algorithm; handling the three cases. - Quantitative facts about Binary Seach Trees (height as a function of number of values in the tree). Memorize if you must, but you are safer being able to re-derive the formulas from diagrams (as in Figure 10-30). - Balancing, and problems that arise when data is inserted in nonrandom order - How to save and restore a binary search tree such that it becomes balanced Traversals - Pre-, In-, and Post-order traversals of binary trees, including expression trees and binary search trees, and what these produce. - Implementation of traversals using an iterator (just the basic concept) - Nonrecursive traversals will not be tested (though it's worth reading to see the relationship to stacks). Representation of General Trees as Binary Trees.Eulerian and Hamiltonian


View Full Document

SJSU CS 146 - Midterm 2 Exam Study Guide

Download Midterm 2 Exam Study Guide
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm 2 Exam Study Guide and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm 2 Exam Study Guide 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?