This course provides an introduction to 1) some fundamental mathematics for modeling computational problems, 2) data structures for storing and accessing information together with relationships between the items being stored, and 3) classic algorithms for efficiently finding solutions to real-world problems. The course emphasizes the relationship between theory and programming to ensure that students are able to use basic data structures and classic algorithms in practice, and to evaluate the cost of a particular data structure or algorithm. For programming, we use the C++ language.
Instructor: Hao Wang
Email: cs_scu@foxmail.com
Office: B316, Teaching Building B, Wangjiang Campus
Teaching Assistant (TA): Xiaomei Gong
Email: 2024326040001@stu.scu.edu.cn
Lecture time slot: 1:50pm - 4:25pm, Monday
Location: A105, 1st Teaching Building, Jiang'an Campus
Office hours (online): 10:00am - 11:00am Wed (or by appointment)
Tencent Meeting: Link
Password: binary code of the course number 311
Final Exam: 50%
You MUST pass the final to pass the course (IMPORTANT!!!).
Assignments (Hw): 20%
distributed on selected Monday during the regular class time.
Usually, no late submissions will be allowed for homework assignments.
Projects: 30%
conducted on selected Monday during the Lab class time (live demo + code submission in due time)
As for machine, you need to bring your laptop.
Discrete Mathematics
C, or C++ (this course used)
Required Textbook
References
Data Structures and Algorithm Analysis in C++, 4th Edition, by Mark A. Weiss, Addison-Wesley, 2013, ISBN 978-0132847377
Discrete Mathematics with Applications, 5th Edition, by Susanna S. Epp, CENGAGE Learning, 2019, ISBN 978-1337694193
Any C++ book or online resources (e.g., An online tutorial on C++ Language)
Course information
Set, relations, and functions theory
Algorithm analysis
Lists, stacks, and queues
C++ programming
Hash Tables
Trees and Graphs
Sorting
Searching
Indexing
Algorithm design
(no need to hand in, but two or three questions will appear in exams)
Exercise 1: I-1.6: 1.3, 1.12, 1.14
Exercise 2: I-2.9: 2.3, 2.5, 2.11, 2.16, 2.17, 2.30, 2.33
Exercise 3: I-3.13: 3.3, 3.8, 3.12, 3.23
Exercise 4: II-4.6: 4.2, 4.6, 4.7, 4.13, 4.18, 4.19
Exercise 5: II-5.8: 5.6, 5.10, 5.14, 5,16, 5.20, 5.26, 5.28
Exercise 6: III-7.11: 7.2, 7.3, 7.6, 7.11, 7.17
Exercise 7: III-9.6: 9.3, 9.6, 9.7, 9.13
Exercise 8: IV-11.7: 11.5, 11.9, 11.11, 11.15, 11.19, 11.24
Hw 1: download here (Due: 11:59pm, Sept. 22, 2024)
Hw 2: download here (Due: 11:59pm, Oct. 11, 2024)
Hw 3: download here (Due: 11:59pm, Nov. 03, 2024)
Hw 4: download here (Due: 11:59pm, Dec. 01, 2024)
Proj 1: download here (Due: 11:59pm, Oct. 20, 2024)
Proj 2: download here (Due: 11:59pm, Nov. 17, 2024)
Proj 3: download here (Due: 11:59pm, Dec. 15, 2024)
All deadlines are Beijing time (GMT+8).
| Week | Date | Topics | Readings | Notes |
| 1 | 02/09/24 | Syllabus, Intro | I.1 | |
| 2 | 09/09/24 | Set, relations, and functions theory | I.2 | |
| 3 | 14/09/24 | Algorithm Analysis | I.3 | Hw 1 |
| 4 | 23/09/24 | Lists, Stacks, and Queues (I) | II.4 | |
| 5 | 30/09/24 | Lists, Stacks, and Queues (II) | II.4 | Hw 2 |
| 6 | 12/10/24 | C++ Programming | Any C++ text | |
| 7 | 14/10/24 | Proj 1 | Lab class | |
| 8 | 21/10/24 | Trees | II.5, 6 | |
| 9 | 28/10/24 | Sorting | III.7, 8 | Hw 3 |
| 10 | 04/11/24 | Searching, Hashing | III.9 | |
| 11 | 11/11/24 | Proj 2 | Lab class | |
| 12 | 18/11/24 | Indexing & Advanced Trees | III.10, IV.13 | |
| 13 | 25/11/24 | Graphs | IV.11 | Hw 4 |
| 14 | 02/12/24 | Algorithm Design | Weiss: Ch. 10 | |
| 15 | 09/12/24 | Proj 3 | Lab class | |
| 16 | 16/12/24 | Course Wrap Up | ||
| Exam | 23/12/24 | 2pm-4pm, B405, 1st Teach. Build. |
This schedule is tentative and subject to change.
Statute of limitations: No grading questions or complaints, no matter how justified, will be listened to one week after the item in question has been returned.
Cheating: Cheating will not be tolerated. All work you submitted must be entirely your own. Any suspicious similarities between students’ work (this includes homework, exams and program) will be recorded and brought to the attention of the Dean. The MINIMUM penalty for any student found cheating will be to receive a 0 for the item in question, and dropping your final course grade one letter. The MAXIMUM penalty will be expulsion from the University.
MOSS: Sharing code with your classmates is not acceptable!!! All programs will be screened using the Moss (Measure of Software Similarity.) system.
Late submission: Late submission of assignment or code will not, in general, be accepted. They will never be accepted if the student has not made special arrangements with me at least one day before the assignment is due. If a late assignment is accepted it is subject to a reduction in score as a late penalty (10% per day).