CPSC 241, Summer Session II -- Assigned Reading

This website is preserved for historical and scholarly reference and is no longer actively maintained.

READING ASSIGNMENTS

CPSC 241

Textbooks:

C++ Primer (Third Edition)

by Stanley B. Lippman and Josee Lajoie

Addison Wesley

ISBN 0-201-82470-1

Data Structures and Algorithm Analysis in C++

by Mark Allen Weiss

Addison Wesley

ISBN 0-8053-5443-3

Week 1:

Chapters 1 and 2 of C++ Primer form a self-contained introduction and overview to the entire C++ language. The remainder of C++ Primer presents the details of the C++ language.

For July 2: Read to the bottom of page 41 in C++ Primer. Be able to work all problems encountered in the reading. Read pages 1 - 12 of Weiss and work exercises 1.9 a and 1.10 (both a and b) on pp 25-26.

For July 3: Finish reading Chapter 2 (through page 74) in C++ Primer. Attempt to work some problems in the reading. Read pp 29-43 (to Section 2.4.4) in Weiss and work problems 2.1 (omit nloglogn and nlog^2 n), 2.2, and 2.6 on pp 50-54.

Week 2:

For July 7: In C++ Primer, read pp 73-93 (to Section 3.4). In Weiss, finish reading Chapter 2. Look at some of the other problems on pp 50-54.

For July 8: No reading assignment -- Quiz I covers pages pp. 1-12 and 29-51 in Weiss, pp. 1-41 (including p. 41) in C++ Primer, and all material either assigned as problems and/or covered in lecture.

For July 9: Read pp. 57-79 of Weiss. Examine problems 3.1 - 3.5 on page 111 and develop algorithms for solving these problems. What is the running time, T(n), of each algorithm?

For July 10: Read page 88 to bottom of page 104 of Weiss. Consider problems 3.12 (page 112) and 3.18 (page 113). Also consider implementing a stack as a doubly linked list. If Insert_At_Front is equivalent to the Push operation, what operation would be equivalent to Pop.

For July 11: Read to end of Chapter 3 of Weiss. Consider problems 3.19, 3.20 (page 113) and 3.21 (page 114).

Week 3:

For July 13: Read page 115 to middle of page 137 of Weiss. Examine problems 4.1, 4.2, 4.3 (page 171) and 4.4, 4.5, 4.8, and 4.9 (page 172).

For July 14: Read from page 181 to top of page 189 of Weiss (open hashing). Work problem 5.1a on page 206.

For July 15: Read from page 189 to middle of page 200 of Weiss (closed hashing). Work problem 5.1 b, c, and d on page 206. Work problem 4.7 on page 172. Also read about the string type (page 93 to bottom of page 101, C++ Primer) and continue reading about pointers (page 88 - middle page 93, C++ Primer).

For July 16: Read from page 211 to middle of page 226 (Weiss). Work problems 6.1, 6.2, 6.3, 6.4 on page 247. Consider also problems 6.5 (except Decrease_Key and Increase.Key), 6.6, and 6.7 a, b.

For July 17: Read pages 253 - 256 and pages 260 to bottom of page 272 of Weiss. (i.e., read to bottom of page 262, skipping Shellsort) Work problems 7.1, 7.2, 7.3, 1.10, 7.11a on pages 290-291.

Week 4:

For July 20: Read pages 297 to middle of page 303 of Weiss.

July 21: Hour Quiz 2.

For July 22:

For July 23: Read pages 319 to bottom of page 325 (Topological Sort). Work problems 9.1 (page 374) and 9.2 (page 375).

For July 24: Read pages 326-345 (Breadth First Search, Dijkstra's Algorithm). Work problems 9.5a, 9.6, 9.7a, and 9.10.

Week 5:

For July 27: Read pages 345-350 (Network flows). Understand basic concepts, including slack.

For July 28: Read pages 350-356 (Minimum Spanning Trees, Prim's Algorithm, Kruskal's Algorithm). Know definition of minimum spanning tree. Know logic of both algorithms.

For July 29: Read pages 356-358 (Depth First Search), page 359-363 (Biconnectivity), pages 363-366 (Euler Circuits), pages 366-369 (Directed Graphs and Finding Strong Components). Be able to perform a depth first search when given a graph. Know what biconnectivity is and why it is important. Know what at Euler circuit is and what a Hamiltonian circuit is. Scan pages 366-369.

For July 30: Read pages 369 to end of Chapter 9 (Introduction to NP-Completeness). Know what the halting problem is (not necessary to understand proof). Know what it means for a problem to be in class NP. Know what it is for a problem to be undecidable or NP-complete. Be able to give examples of each.

For July 31: Work problems 9.11, 9.15 (both a and b), 9.16, and 9.20.

Week 6:

For August 3: Read pages 262-267 (Merge Sort), 267-280 (Quick Sort), 280 (Sorting Large Objects). Work problems 7.12 and 7.16 (page 291). Examine problem 7.17, but do not code it and run it.

For August 4: Read pages 280-283 (A General Lower Bound for Sorting), 283 (Bucket Sort). Work problem 7.24 (page 292).

August 5: Final Exam. noon - 3 p.m.