CPSC 311, Section 502 Comprehensive Review, Test Order

Please let me know whether these notes have been of benefit. jpf@myriad.net Revised 6-January-98.

When using the following table to study for the Test, please see the table notes.

Chapter Dependencies

Mathematical Foundations -> Sorting ----------------\
1, 2, 4                     7, 8, 9, 10              > Graphs
                         -> Sets -------------------/  23, 24, 25
                            22
                         -> Hashing
                            12
                         -> Matrix Multiplication
                            16, 31

 

 

 

Test 1
Test 1 - Chapter 1			Introduction
Section	Pages	Points on Tests	Content
	xiii-xvii (5)
1.1	1-5 (5)	3(2)	Insertion-Sort
1.2	6-10 (5)		Insertion-Sort with timing review
1.3	11-15 (5)	6	Merge-Sort Divide-and-conquer algorithms.
1.4	16 (1) (21)
Test 1 - Chapter 2			Growth of Functions
2.1	21-31 (11)	40	Definitions of Theta, O, Omega, o, and little omega; comparison of functions; evaluation of algorithms
2.2	32-37 (6) (17)	14	Monotonicity, polynomially bounded, exponentials, logarithms, factorials, iterated logarithm, Fibonacci numbers
Test 1 - Chapter 4			Recurrences
4.1	53-57 (5)	5	substitution method
4.2	58-60 (3)	10	iteration method - recursion trees
4.3	61-64 (4) (12) (50)	5	master method
Test 2
Test 2 - Chapter 7			Heapsort
Section	Pages	Points on Tests	Content
7.1	140-142 (3)	10(1)	Parent, Left, Right
7.2	143-144 (2)	10(1)	Heapify
7.3	145-146 (2)	3	Build-Heap
7.4	147-148 (2)		Heapsort
7.5	149-150 (2) (11)		Insert, Maximum, Extract-Max, Minimum, Extract-Min, Heap-Extract-Max, Heap-Insert
Test 2 - Chapter 8			Quicksort
8.1	153-155 (3)	18	Quicksort, Partition, not stable
8.2	156-160 (5)		Boundary conditions
8.3	161-162 (2)	5	Random, Randomized-Partition, Randomized-Quicksort
8.4	163-167 (5) (15)
Test 2 - Chapter 9			Sorting in Linear Time
9.1	172-174 (3)	28	decision tree
9.2	175-177 (3)	5	Counting-Sort
9.3	178-179 (2) (8)	13	Radix-Sort, review 9.3-4
Test 2 - Chapter 31			Matrix Operations
31.1	730-737 (8)		reference Matrix-Multiply (section 16.1)
31.2	739-744 (6) (14)	5	Strassen's algorithm
Test 2 - Chapter 16			Dynamic Programming
16.1	301-308 (8)	25	Matrix-Multiply, Matrix-Chain-Order, Matrix-Chain-Multiply, optimal parenthesization
16.2	309-314 (6) (14) (62)	5	Recursive-Matrix-Chain, Memoized-Matrix-Chain, Lookup-Chain, optimal substructure and overlapping subproblems
Test 3
Test 3 - Chapter 22			Data Structures for Disjoint Sets
Section	Pages	Points on Tests	Content
22.1	440-442 (3)	15	Connected Components, Union, Linked List representation
22.2	443-445 (3) (6)	15	Make-Set, Find-Set, amortized cost of Union?, proof 445
Test 3 - Chapter 23			Elementary Graph Algorithms
23.1	463-468 (6)	15	Adjacency List, Adjacency Matrix, out-degree
23.2	469-476 (9)	15	Breadth First Search, O(V+E) Print-Path, didn't use color or predecessor
23.3	477-484 (8) (23)	15	Depth First Search Theta(V+E), didn't use predecessor, Types of Edges, parenthesis structure, Each vertex ends up in exactly one depth-first tree, so that these trees are disjoint.
Test 3 - Chapter 24			Minimum Spanning Trees
24.1	498-503 (6)	15	1-5 (445-446), Spanning Tree, Proof (501)
24.2	504-513 (10) (16) (45)	15+5(4)	Kruskal's, like Connected-Components, O(ElgE), Prim's, like breadth-first, O(ElgV), 24.2-1 understand
Review for Test 3 - Chapter 7			Heapsort
7	149-152 (4)		Heap Priority Queue
Review for Test 3 - Chapter 18			Amortized Analysis
18	356-378 (23)		Amortized Analysis Aggregate Method n ops take time T(n) avg cost of an op is T(n)/n Accounting Method Potential Method
Test 4
Test 4 - Chapter 10			Medians and Order Statistics
Section	Pages	Points on Tests	Content
10.1	185-186 (2)		Minimum
10.2	187-189 (3)	10	Randomized-Select
10.3	190-191 (2) (7)	5	Select
Test 4 - Chapter 12			Hash Tables
12.1	219-220 (2)		Direct-Address-Search, Direct-Address-Insert, Direct-Address-Delete
12.2	221-225 (5)	15	Chained-Hash-Insert, Chained-Hash-Search, Chained-Hash-Delete, plausibility?
12.3	226-231 (6)
12.4	232-239 (8) (21)		Hash-Insert, Hash-Search
Test 4 - Chapter 25			Single-Source Shortest Paths
25.Intro	514-518 (5)	5
25.1	519-526 (8)		Initialize-Single-Source, Relax
25.2	527-531 (5)	15	Dijkstra (528), like breadth-first, linear array O(V^2), binary heap O(ElgV)
25.3	532-535 (4) (22) (50)	10	Bellman-Ford (533), O(VE)

Table Notes

• Chapters and sections have been indicated according to my notes for tests 1-4.
• Paging is sometimes slightly inaccurate. (Usually when a section begins part-way through a page, that page is counted in either the previous section or the new section. Chapter introductions may be counted as part of the first section.) One main purpose of the paging is to indicate how much information needs to be reviewed.
• Chapter notes and questions from the book have not been indicated in the paging.
• Test and practice questions have been distributed in the section that seemed most appropriate. (There may be a note with the question identifying its use of information from another chapter.)
• Algorithms should be indicated in strong font type. Other notes may be indicated with the algorithms. Usually the notes have to do with information that the teacher has emphasized. These notes do not represent the overall content of the sections!
• The Test 1-4 & Pract. Quest. has data for total test points for questions from each section. (It's possible that some of the points could have been counted for another section.) The purpose is just seeing what information is emphasized on the tests.
• While reviewing the test questions, I've added comments about content based on what the test questions were.

Notes for test 3

• Review practice questions
• Algorithms
  • Copy
  • Time review

Questions from Chapter 24

• Practice 24.1 (445-446) 1, 2, 4, 5
• Turn in 24.1 (445-446) 3
• Practice 24.2 (510) 1, 6
• Turn in 24.2 (510) 2, 4 alpha(m,n) = O(lg*n) = o(lg n)

Spanning Tree

• Connected acyclic graph
• There is only one path between vertices
• Spanning tree cannot be the subset of any other tree

Edges in Directed Graphs

Tree

v white when (u,v) explored. Edge can be in Undirected Graphs as well.

Backward

v is ancestor of u in tree. Edge can be in Undirected Graphs as well.

Forward

v is a descendent of u in depth first search and (u,v) is not a tree edge

Cross

all other cases. Cross edges may connect two vertices in different trees or in the same tree

Time Review

• Depth First Search Theta(|V| + |E|) = Theta(max(|V|, |E|)
• Make Set O(1), Find Set O(1)

Comments

• 22.1-3 (442-443) may be useful
• see 79, 82, and 88
• Theorem 22.1 (22.1' in notes) may be useful
• Possible use of priority queue - smaller key items have higher priority
• O(n) method of finding sink

In copy center

• explanation for 24.2-1
• key for practice test

Additional information

• Inductive proofs (See response for second test, question 4)
• Matrix multiplication Cij = Summation from j=1 to n of Aij * Bjk