Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 234: Data Types and Structures
Course Number and Title: CS 234, Data Types and Structures
Lecture Times, Building and Room Number: Tuesdays and Thursdays, 10:00-11:20 and 1:00-2:20, STC 0020
Instructor’s Name, Office Location, Contact Information, Office Hours: Naomi Nishimura, DC 2344, [email protected], Tuesdays and Thursdays 11:30-12:00 and 2:30-3:00
IA’s Names, Office Location, Contact Information, Office Hours:
Kaiyu (Kevin) Wu, DC 2305, [email protected] , Mondays 4:00-5:15, Tuesdays 3:00-4:00, Fridays 2:00-2:45
Xiang Fang, MC 4065, [email protected], Mondays 3:00-4:30
Course Description:
Top-down design of data structures. Using representation-independent data types. Introduction to commonly used data types, including lists, sets, mappings, and trees. Selection of data representation.
Course Objectives: At the end of the course you should be able to:
- Explain the benefits of using abstract data types (ADTs) and data structures, and more generally, the concepts of modularity and data hiding, in solving problems in a wide variety of application areas. Understand the differing points of view of the user and provider of an ADT and the use of an interface to communicate between views.
- Explain and use the concepts of asymptotic running time, order notation, worst-case, average-case, and best-case complexity, and lower and upper bounds. Given a simple algorithm written in pseudocode, determine and informally justify its asymptotic running time, as expressed in order notation.
- Explain the basic structure of memory, including the distinction between external and internal memory and the concept of paging.
- Explain the advantages and disadvantages of data structures using contiguous or linked memory.
- Explain common ADTs (e.g., Set, Stack, Queue, List, Dictionary, Priority Queue, Tree, Graph), and give a sample application for each. Explain the complexity of some common implementations of these ADTs.
- Explain the distinction between different types of data (e.g. arbitrary, orderable, distinct, digital) and the types of ADTs that can be used for each situation. Given a well-specified computational problem, determine which (if any) ADTs would be suitable.
- Explain how specialized data structures can lead to efficient solutions to specific real-world problems.
- Write, test, and debug Python programs using the material described above.
Optional Text: Rance D. Necaise Data Structures and Algorithms Using Python. This book is on reserve at the Davis Centre Library.
Readings: Supplementary reading material will be available on the course website.
Topics to be covered in lectures:
Module 1: Introduction
Topics: User and provider viewpoints, planning and coding stages, models, modularity and data hiding, abstract data types, implementations, recipes
Module 2: ADTs and pseudocode analysis
Topics: Choosing and modifying ADTs, compound and static data, ADT Multiset, types of ADTS, pseudocode, analysis, order notation
Module 3: Data structures
Topics: Memory, basic data structures, Python modules for data structures, ADT Set, types of data, bit vector
Module 4: Group B ADTs
Topics: ADT Stack, ADT Queue, linked data structures, ADT Indexed Sequence, ADT Ranking, ADT Grid
Module 5: Trees
Topics: Tree terminology, decision trees, ADT Binary Tree, ADT Ordered Tree, ADT Unordered Tree, implementations, tree traversals
Module 6: Graphs
Topics: Graph terminology, ADT Undirected Graph, ADT Directed Graph, implementations, breadth-first search, depth-first search
Module 7: Dictionaries
Topics: ADT Dictionary, searching, sorting, binary search tree, AVL tree, (2, 3) tree
Module 8: Priority queues
Topics: ADT Priority Queue, heap, heapsort
Module 9: Improvements
Topics: Comparison-based algorithms, decision-tree lower bound, average versus expected, interpolation search, search in a static array, self-organizing heuristics, hashing, bucket sort, radix sort
Module 10: Extensions
Topics: Skip list, graph problems, ADT Disjoint Sset, ADT Range, quadtree, k-d tree, strings and tries, other criteria and analysis, memory hierarchy and B-tree.
Evaluation:
Marks in the course will be calculated as follows:
§ Assignments: 30%§ Midterm: 25%§ Final exam: 45%
Students should periodically check recorded marks (using MarkUs) for accuracy.
Notes:§ You must pass the weighted exam average in order to pass the course.
§ Each assignment has the same weight towards the overall mark.
Assignment policies:
All assignments must be completed individually in this course. The solutions you submit must be entirely your own work. Do not look up full or partial solutions on the Internet or in printed sources.
No late assignments will be accepted.
Assignments consist of written and programming components.
Submit both types of components electronically using MarkUs.
Academic Integrity
In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. Check the Office of Academic Integrity's website for more information.
All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in — and out — of the classroom.
Intellectual Property
Students should be aware that this course contains the intellectual property of their instructor, TA, and/or the University of Waterloo. Intellectual property includes items such as:
• Lecture content, spoken and written (and any audio/video recording thereof)• Lecture handouts, presentations, and other materials prepared for the course (e.g., PowerPoint slides)• Questions or solution sets from various types of assessments (e.g., assignments, quizzes, tests, final exams)• Work protected by copyright (e.g., any work authored by the instructor or TA or used by the instructor or TA with permission of the copyright owner).
Course materials and the intellectual property contained therein, are used to enhance a student’s educational experience. However, sharing this Intellectual property without the intellectual property owner’s permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).
Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.
Grievance
A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 — Student Petitions and
Grievances, Section 4. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.
Discipline
A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. For information on categories of offenses and types of penalties, students should refer to Policy 71 — Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.
Avoiding Academic Offenses
Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy.
Appeals
A decision made or a penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72 — Student Appeals.
Note for students with disabilities
The AccessAbility office is located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.
• Mental Health: If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. On-campus Resources• Campus Wellness https://uwaterloo.ca/campus-wellness/• Counselling Services: [email protected] / 519-888-4567 ext 32655 / Needles Hall North 2nd floor, (NH 2401)• MATES: one-to-one peer support program offered by Federation of Students (FEDS) and Counselling Services: [email protected]• Health Services service: located across the creek from Student Life Centre, 519-888-4096. Off-campus Resources• Good2Talk (24/7): Free confidential help line for post-secondary students. Phone: 1-866-925-5454• Here 24/7: Mental Health and Crisis Service Team. Phone: 1-844-437-3247• OK2BME: set of support services for lesbian, gay, bisexual, transgender or questioning teens in Waterloo. Phone: 519-884-0000 extension 213
Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students’ learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:
• We will gladly honour your request to address you by an alternate/preferred name or gender pronoun.Please advise us of this preference early in the semester so we may make appropriate changes to our records.• W e wi ll honour your religious holidays and celebrations. Please inform of us these at the start of the course.• We will follow AccessAbility Services guidelines and protocols on how to best support students with different learning needs.