CS 4004
Discrete Mathematics and Data Structures
Catalog Description
- Topics to be Covered
- Textbook
-
Grading
- Class Schedule
- Important Dates
- GTA
- FAQ
- Programming Assignments
- Exam
Lecture Slides
- Software
Catalog Description
Coursework covers logic, mathematical induction, recursion,
mathematics of algorithms, finite-state machines,
arrays, stacks, lists, trees, sorting, and searching
Textbook
Discrete Mathematics and Its Applications, 4th
Edition, Kenneth Rosen, WCB McGraw-Hill Publishing Co., 1999,
ISBN: 0-07-289905-0.
A Practical Introduction to Data Structures and Algorithm Analysis,
Java Edition,
Clifford A. Shaffer,
Prentice Hall, 1998, ISBN: 0-13-660911-2.
Book Chapters/Sections to be Covered (Tentative)
Discrete Mathematics: Rosen's book,
Sections 1.1-1.8, 2.2, 3.1-3.4, 4.1, 4.3, 5.1, 6.1, 6.5, 10.2, 10.3.
Practice Exercise Problems:
- Chapter 1
- Review questions: #1 - #20 (page 94)
- Supplementary exercises: odd-numbered questions #1 - #39 (page 95)
- Chapter 2
- 2.2: #3, #5, #7, #13 (page 111)
- Chapter 3
- Review questions: #1 - #11 (page 226)
- Supplementary exercises: #1, #3, #5, #7, #11, #13, #15, #17, #19, #21, #23, #31, #41, #43, #45, #47 (page 227)
- Chapter 4
- 4.1: #15, #17, #25, #29, #31, #33, #37, #39, #41, #45, #49 (page 242)
- 4.3: #9, #11, #15, #17, #21, #23, #27, #28, #29, #31, #32 (page 258)
- Chapter 5
- 5.1: #9, #11, #13, #15, #17, #19, #21, #23, #24, #35 (page 316)
- Chapter 6
- 6.1: #3, #5, #20, #21, #22 (page 382)
- 6.5: #1, #5, #11, #13, #23, #25, #31, #35, #36 (page 413)
- Chapter 10
- 10.2: #1, #2, #3, #5, #7, #8, #11, #13, #14 (page 645)
- 10.3: #9, #11, #12, #13, #14, #15, #16, #17, #18, #19, #20, #21, #27 (page 653)
Data Structures: Shaffer's book,
Chapters 1, 3, 4, 5, 6, 7, 8, 10 and 11.
Practice Exercise Problems:
- Chapter 1
- 1.3,
1.5,
1.13 (page 16)
- Chapter 3
- 3.5,
3.8, 3.9,
3.10,
3.11,
3.13,
3.14 (page 71)
- Chapter 4
-
4.1,
4.4,
4.6,
4.9,
4.10,
4.14,
4.15,
4.16 (page 115)
- Chapter 5
-
5.3,
5.4, 5.5,
5.6, 5.8,
5.12,
5.16,
5.17,
5.18,
5.19,
5.20,
5.21 (page 161)
- Chapter 6
-
6.3,
6.4,
6.6,
6.8,
6.9,
6.13,
6.14 (page 185)
- Chapter 7
- 7.3,
7.4,
7.5,
7.7,
7.9,
7.10,
7.14,
7.17,
7.18,
7.19 (page 220)
- Chapter 8
- 8.3,
8.4,
8.8,
8.10,
8.11,
8.15,
8.16 (page 262)
- Chapter 10
- 10.11,
10.12,
10.14,
10.16 (page 330)
- Chapter 11
- 11.11,
11.12,
11.13,
11.14,
11.15,
11.16 (page
360)
Grading
20% programming assignments (2)
25% exam 1
25% exam 2
25% exam 3
5% class participation
Class Schedule
| Date |
Exam/Assignment |
Source |
Subject |
| 1/17 |
|
DM 1.1-1.5 |
Logic and Sets |
| 1/24 |
|
DM 1.6-1.8, 2.2 |
Functions and Complexity |
| 1/31 |
|
DM 3.1-3.4 |
Mathematical Induction, Recursion |
| 2/7 |
|
DM 4.1, 4.3, 5.1 |
Counting, Recurrence Relations |
| 2/14 |
|
DM 6.1, 6.5, 10.2, 10.3 |
Relations and Finite State Machine |
| 2/21 |
exam 1 |
|
7:00 - 9:45 p.m. in class |
| 2/28 |
assignment 1 |
DS 1.1-1.4, 3.1-3.8 |
Introdution to Data Structures, Algorithm Analysis |
| 3/7 |
No Class |
|
Spring Break |
| 3/14 |
|
DS 4.1-4.3 |
Lists, Stacks, and Queues |
| 3/21 |
|
DS 5.1-5.6 |
Binary Trees |
| 3/28 |
|
DS 6.1-6.5 |
General Trees |
| 4/2 |
assignment 1 due |
|
midnight |
| 4/4 |
exam 2 |
|
6:00 - 8:45 p.m. in class |
| 4/11 |
assignment 2 |
DS 7.1-7.5 |
Graphs |
| 4/18 |
|
DS 8.1-8.9 |
Sorting |
| 4/25 |
|
DS 10.1-10.4, 11.1-11.5 |
Searching and Indexing |
| 5/2 |
exam 3 |
|
6:00 - 8:45 p.m. in class |
| 5/5 |
assignment 2 due |
|
midnight |
Important Dates
exam 1 (DM) on 2/21
exam 2 (first part of DS) on 4/4
exam 3 (second part of DS) on 5/2
Programming Assignment 1 due on 4/2
Programming Assignment 2 due on 5/5
GTA Names and Email Addresses
Class GTA: TBA
Systems GTA: Sapna George, Room NVC 421, (703) 538-8379, sgeorge@vt.edu
Frequently Asked Questions and Answers
DM questions on exam 1
FAQ questions on assignment 1
DS questions on exam 2
FAQ questions on assignment 2
DS questions on exam 3
Programming Assignments
Assignment 1
Assignment 2
Policy:
- A programming assignment turned in late
will be penalized 10% off for each day late.
After a week late, the late assignment will be 100% off.
- Any Java programs not passing the javac compiler will be counted 0.
- Any Java programs not able to generate any output on execution by
java will be counted 0.
- Partial credits will be given to programs which
generate partially correct outputs
-
All students must observe
the Graduate Honor Code. No cheating, plagiarism,
falsification, or
academic sabotage allowed in this class.
Violated students will be reported to Virginia Tech's
Graduate Honor System.
All assignments turned in should add a
Pledge for Assignment clause as follows at the beginning:
I pledge that this assignment has been completed in
compliance with the Graduate Honor Code and that I have
neither given nor received any unauthorized aid on this
assignment.
Signed ______________________________________________________
How to Turn in Your Assignment:
-
Your assignment should be emailed to the class GTA in a ZIP file by the
midnight of the specified due date.
The ZIP file should contain only the source file, data file
and a readme file explaining how to compile and execute the
program. Internal documentation of the source file is not required.
Exam
Sample Test 1 (DM) -- Skip Problems 14 and 15
Solution of Sample Test 1(DM) -- Skip Problems 14 and 15
Sample Test 2 and Solution (DS&A)
Sample Test 3 and Solution (DS&A)
Lecture Slides
Lecture 1 (DM)
Section 1.1
Section 1.2
Section 1.3
Section 1.4
Section 1.5
Lecture 2 (DM)
Section 1.6
Section 1.7
Section 1.8
Section 2.2
Lecture 3 (DM)
Section 3.1
Section 3.2
Section 3.3
Section 3.4
Lecture 4 (DM)
Section 4.1
Section 4.3
Section 5.1
Lecture 5 (DM)
Section 6.1
Section 6.5
Section 10.2
Section 10.3
Lecture 1 (DS)
Chapter 1
Chapter 3
Lecture 2 (DS)
Chapter 4
Lecture 3 (DS)
Chapter 5
Lecture 4 (DS)
Chapter 6
Lecture 5 (DS)
Chapter 7
Lecture 6 (DS)
Chapter 8
Lecture 7 (DS)
Chapter 10
Chapter 11
Software
Programming assignments should be implemented using Java.
You can apply for a department UNIX account and use
the standard "javac" and "java" commands to compile
and execute your programs.
You can also install the following (free) software yourself
under Windows:
TextPad is a nice tool allowing you to edit, compile and execute
Java programs.