Reading and Homework Assignments CS 260-01
Note: check this page frequency as assignments will change over the course of the semester.
Readings in the "Basic Sections" and "Related Sections" should be done prior to coming to class on the date indicated. (The "Related Sections" give some examples of how the material will be used later in the course or refer you back to prior examples.) Reading means going over the sections until you feel that you have a good grasp on the material. This means reading with a paper and pencil and going over the examples given in the text. It also means developing specific questions for class discussion.
As we enter the second half of the semester, there are parts of chapters 6, 7, 8 and 10 that we have already covered. We have covered most of chapter 6 with the exception of sections 2, 4 and 6. I have indicated those sections that are closely related in the "Related Sections" column. There are also items that we need to go back and cover in sections 1-4 such as complexity of problems and recursion. I put these off as they are easier to explain with the examples from chapters 7, 8 and 10. Since Trees, Graphs, Relations and Automata are closely related, I will cover material from sections of two chapters at the same time -- particularly if presenting the material together helps to give a better understanding of both.
For some of the material on Graphs and Trees, I will be taking material from some of the sources listed in the bibliography as some of the examples show how graphs and trees are used.
| Date | Chapter | Basic Sections | Advanced Sections | Homework | Applications | Related Sections | |
| 4th ed. | 3rd ed. | ||||||
| 1/13/99 | 1. Logic, Sets and Functions, Big-O Notation | 1,2 | 8
|
1.11, 19 ,21, 23, 29 2.7, 13, 19, 20,33 |
1.7, 15,17 2.13,19,20, 33 |
Database queries | 9.1, 9.2,3.1 |
| 1/20/99 | 4,5 | 4.17, 23 5.1, 3, 11, 15, 19, 25 |
4.15,17,21 5.1,3,11,15,19 25 |
Database design | 6.1, 3.1, 5.5 | ||
| 1/25/99 | 6 | 6.1,7 10,11,15,17, 23, 47 | 6.1,,10,11, 24 |
Functions | 6.2,6.5 | ||
| 1/27/99 | 7 | 7.13, 15, 17, 21, 23,27 29 |
7.7,9,15,17, | Loops | 3.3 | ||
| 2/1/99 | 8 | 8.1, 3, 5, 19, 21 | 8.1,3,5,19,21 | Determining run times | 2.1, 2.2 | ||
| 2/3/99 | 2. Complexity of Algorithms, Number Theory, Matrices and Cryptology | 3 | 5
|
3:2,5,7,15,17,29,31, 41,43,45,47 project 1: Due 5/3/99, 5pts |
3:2,5,7,15,17,29,31, 41,43,45,47 |
Hashing Function, Psuedorandom number | 1.8 |
| 2/9/99 | 4 | 4:5,7,11,19,25 | 4:5,7,11,19,25 | Representation of integers | 6.5 | ||
| 2/10/99 | 5 | 5:3,7,11 | 5:3,7,11 | Public Key Cryptography | 7.3, 6.5 | ||
| 2/16/99 | 6 | 6:3,5,15,19,29, | 6:3,5,15,19,29, | Array representation of discrete structures and their operations. | 6.1,6.3,7.3,6.4 | ||
| 2/17/99 | 4. Counting, Combinatorial Analysis | 1,2,3,4 | 7
|
1:15,44,49,56 3:6,6,17,35,47,55 4:23,34 |
|
Counting | 8.2 |
| 2/22/99 | 5,6 |
5:23,33,35,37,43 6:15,35,41,47 7: 7,13 |
Probability Theory | 5.5,5.6 | |||
| 2/24/99 | 3. Mathematical Reasoning | 3.3, 3.4 |
|
3:1,3,7 |
|
Recursion | 5.1 |
| 3/1/99 | 3.2 | 2: 1,3,5 | Induction | 4.7 | |||
| 3/3/99 | MIDTERM |
||||||
| 3/15/99 | 6. Relations | 1,2,3,5(we have already covered most of 6.1,3 and 5; I am going to delay 6.4 until we talk about graphs.) | 6 | Project 2: Due 5/3/99,
5pts
|
6.1:1,3,34 6.2: 5,7,9,11 6.3: 1,7,9,17 6.5: 1,11 |
Database Queries, Database Design | 2.6,2.5,1.6,7.1 2,3,4,7.3,1.4 |
| 3/17/99 |
6 | 6.6: 3, 9,25,50 Develop
a Hasse Diagram showing all computer science courses with their prereqs. See Ch 6 Notes for discussion on how to get started. I will be adding
to these, so check them out periodically. After you do the diagram, do a topological sort to get a total ordering. Find the maximal and minimal elements, and the least upper bound and greatest lower bound for each course. Also find the greatest and least elements if they exist. If a courses is not needed for graduation, exclude it from the diagram. However you may need to keep a marker for an elective since you need some of these. When you get done, you should have a diagram that you can post in the Coach House that tells people the order in which they can take CS courses. You should also include an explanation of any things that could not be put on the chart because it does not fit the poset definition. I will collect these on Monday. |
Computer representations of relations, Networks | 1.6,7.1,2,3,4 | |||
| 3/22/99 | 7. Graph Theory |
1,2,3 | 6,7,8 |
1: 1,13,15,17,19 2:3,27 3:3,21,35,39 Writing project: do either 1 or 2 on page 527. These writing assignments should be 2 to 3 pages including graphs. The purpose is to look at some real examples of how graph theory is used and get you to do some independent work. The papers should be typed and well written. You need to do at least one of the Writing Projects in this chapter. |
same, do either 1 or 2 of the writing
projects at the end of the chapter. same
|
Networks | 1.8, 2.6,6.3, 10.2,6.4 |
| 3/24/99 | 4,5,6.4 | 4: 1,2,3 5: 1, 15,25,41 |
Computer representations of graphs: connectivity and paths | 2.6, 6.3 | |||
| 3/29/99 |
6,8.5,8.6 | 7:3,9,17,27 8.5: 17 8.6: 1 Writing Project: Do 9 or 10 in the writing projects at the end on the chapter (p.527) |
Shortest Path, Network Design,Path Optimization, Examples of P and NP problems.Minimal spanning trees. | 8.5,8.6,2.2 | |||
| 3/31/99 | 7,8 | 7:1,3,5,711,17,19 8: 3,5,9,15,17,21 Writing Project: Do number 11 of the writing
projects on p.527. |
Planar Graphs Graph Coloring |
8.4,2.2 8.5,2.2 |
|||
| 4/5/99 |
8. Trees
|
1,2 | 3 |
1:2 2:1,13
|
Recursion | 7.1, 10.1, 3.3,3.4 |
|
| 4/7/99 | 3 | 7,19,27 | Recursion, Searching Linked Lists |
4.1, 4.2, | |||
| 4/12/99 | 4 | 1,3,5 | Sorting | 2.1,2.2 | |||
| 4/14/99 | 10. Modeling Computations, Finite State Machines | 1 | 3,4 |
1,13,17, | Compiler Construction | 8.1 | |
| 4/19/99 | 2 | 3,5,9 | Finite State Machines | 7.1, 7.2 | |||
| 4/21/99 | 3 | 1,11,13, | |||||
| 4/26/99 | 4 | 1,3,9,11 | Language Recognition | 8.3 | |||
| 4/28/99 | 5 | 1,3,5,7 | Turing Machines | 8.2 | |||
| 5/3/98 | Final Exam 11:00-1:30 (Projects due) |
||||||
You are the visitor to this site.