CS 235 Data Structures
Syllabus, Spring 2023
|
Instructor: Paul Roper Email: proper@cs.byu.edu |
Section
001 2:00-3:50 am MWF B092 JFSB |
|
|
Learning Outcomes
CS 235 provides a hands-on
introduction to data structures and algorithms. Through programming projects
and exams, you learn how to select and implement suitable data structures for
various problems, how and when to use recursion, and how to analyze the cost of
algorithms, especially sorting and searching algorithms.
·
Data Computing
Fundamentals - Implement the fundamental data types of computing
(lists, stacks, queues, heaps, priority queues, sets, maps, and binary search trees).
·
Select Data
Structures - Properly use and select data structures from language-provided
data-structure libraries.
·
Analysis - Apply basic
algorithm analysis.
·
Recursion - Understand how
recursion works and write programs using recursion to solve problems.
·
Choice of Algorithms - Make informed decisions
about which sorting and searching algorithms to use in specific circumstances.
·
Program Writing - Write larger,
multi-file programs using an IDE (+500 lines).
Pre-requisites
- Students must
have completed CS 111 (or an equivalent) with a passing grade before
taking CS 235.
- If you have
not satisfied any of the above pre-requisites, you may be dropped from the
course.
Course Materials
·
All course content including course syllabus,
schedule, PowerPoint slides, lab
descriptions/submission, code reviews, quizzes, video
links, and help queue are available on the course website
(https://students.cs.byu.edu/~cs235ta).
·
Email, on-line exams, and course grades/scores (BYU Grades tab.)
will be managed by Learning Suite.
·
We will use Elliot B. Koffnam
and Paul A. T. Wolfgang’s Objects, Abstraction, Data Structures and
Design Using C++ for our course of study and follow
the order of the book chapters.
·
Microsoft’s Visual Studio Community C++ IDE will be used for class
demos.
Note: C++ is a standard, not a program. Within the functionality and syntax
defined by C++17 standards committees, your source code should compile and
execute independent of your compiler or IDE (gcc,
g++, MSVC, LLVM, etc.) All CS
department machines have Visual Studio installed. You can find Visual Studio’s C++
language references here: https://msdn.microsoft.com/en-us/library/3bstk3k5.aspx. (A free install is available for
all Windows machines at http://www.visualstudio.com/en-us/downloads/download-visual-studio-vs#DownloadFamilies_2.)
·
Linux g++ for will be used to unzip, compile, and
execute your lab submissions.
·
Finally, make www.stackoverflow.com,
http://www.cplusplus.com/reference and www.google.com your closest
friends. If you have any questions
about C++, consult them first before seeking TA help.
Course Format
·
Spring 2023, Section 001 will be CLASSROOM (in-person,
on-campus) instruction and not recorded. Class time will be used to answer
questions concerning the assigned reading, video presentations, and/or lab
specifications. Coding example
programs and topic reviews will be part of the class instruction.
·
Before each class meeting:
o Complete the assigned
reading.
o
In addition, work on lab programming assignments will
help in making class discussions beneficial.
o
If needed, view the PowerPoint lecture video (available on
the class schedule).
·
There will be times when information given in lectures is
not found in the textbook, video, or class website. It is very important that students
attend each class. You will be
held responsible for class session material as well as the course text readings.
·
To encourage class attendance and to help prepare for
exams, an on-line quiz will be available after each class. Codes for the attendance quizzes will be
announced during class and expire at the end of the following day.
·
Exams will be administered using Learning Suite.
·
Programming assignments will be web submitted and peer
reviewed. Auto-graded results of
web submissions will be immediately returned via email and later recorded in
BYU Grades (Learning Suite).
Course Assessments
Student evaluation and grading will be three-fold,
namely performance-based, formal, and summative assessments.
1.
Programming Assignments. (Performance-based assessment) 40%
·
Hands-on application of section concepts.
·
Improve programming skills.
·
Solve practical problems.
·
Develop critical/analytical thinking.
2.
Peer Evaluations / Quizzes. (Formal assessment) 20% + 5% quiz
bonus
·
Target areas needing work.
·
Help preparation for exams.
·
Provide immediate feedback.
·
Gage progress with other peers.
·
Motivate study.
·
Identify strengths/weaknesses.
3.
Exams. (Summative assessment) 40%
·
Compare student knowledge against standard.
·
Guide efforts and activities in subsequent courses.
·
Fulfill accreditation requirements.
Computer Programming Assignments
Programming assignments consist of 9 required
labs plus two bonus labs and are designed to emphasize topics and objectives
discussed during class.
·
Lab 1: Grades.
Output the average score for all students on each exam followed by a
list of student's score and grades.
·
Lab 2: SNAP. Design classes for a school database and
output course and student schedules.
·
Lab 3: Linked List.
Develop a Linked List container that implements standard list operations.
·
Lab 4: Iterator (linked
list). Implement a nested iterator class for
Lab 3’s linked list container.
·
Lab 6: Railroad (stacks, queues, deques). Manage the Greater Provo Railroad
Station storage facility as directed.
·
Lab 7: Maze (recursion). Two SCUBA divers need to find a path
through the storage facility maze.
·
Lab 8: BST (trees).
Add and remove nodes from a binary search tree.
·
Lab 9: Pokémon (maps and sets). Add and remove nodes from map and set
data structures.
·
Lab 10: Quicksort (sorting). Implement a quicksort algorithm and sort
a data set.
·
Bonus Lab 5: Expressions (infix, postfix, prefix, balance). Performs operations on infix, postfix,
and prefix expressions.
·
Bonus Lab 11: AVL (balanced tree). Use AVL algorithm to self-balance a
binary search tree.
Please pay careful attention to the following
programming assignments guidelines:
1.
Zip together all your lab source files (.cpp, .hpp, .h) – do not
include any IDE folders or files.
2.
Submit your zipped lab source folder using the “Labs”
tab on the class website.
3.
The auto-grader will immediately:
a.
Unzip and compile your submitted source using the Linux g++
compiler.
b.
If there are no compilation errors, the resulting
executable will be run using command line arguments to select both input and
output files.
c.
The resulting output file(s) from your program will be graded
and the results reported immediately on the submission web page.
d.
Points will be deducted for any detected memory leaks,
warnings, and/or out-of-bounds array references.
4.
You may re-submit your zipped source as many times as you
like throughout the semester. (Late
penalties may apply.) Your highest
score will be used for your final lab grade.
5.
Anonymous peer review assignments will be made
immediately after the lab submission deadline and must be completed before the
next lab due date.
6.
Only on-time zipped solutions of more than 10
points will participate in the peer review process.
7.
Lab and peer review scores will be recorded weekly in BYU
grades (found on Learning Suite).
8.
Lab assignments submitted after
the due date will receive a 50% penalty on
portions of the lab not submitted on time.
9.
It is the
student’s responsibility to ensure all relevant files are included in the
zipped submission - submissions that don’t compile or are from the
wrong lab will result in a lower grade.
10.
Lab grades are calculated from auto-grader scores, peer
reviews, and assigned reviews. Lab scoring
is calculated as follows:
a.
40-50 points – Lab requirements assessed by
auto-grader.
b.
10-20 points – Coding style and additional
requirements assessed by peer reviewers.
c.
2 points – Completion of two assigned peer reviews.
Note:
·
If you want your work to remain anonymous during peer
reviews (FERPA), use a unique coding pseudo-name (e.g.
Cody Coder III, Franky Forloop, Doesy
Dowhile) on source headers comments. Using identifying comments serves as
your permission for your peers to know your work’s identity.
·
Peer review scores that significantly differ will
automatically be arbitrated by a TA.
Submitting inaccurate peer reviews will result in loss of your review
points.
Exams
A pre-exam is
required of all students and is administered at the beginning of the semester
thru Learning Suite. Full credit
will be given for those taking the exam. Your score on the exam will not affect
your final grade. There is no makeup for the pre-exam.
Two midterms will be
administered during the semester on Learning Suite as scheduled. You should plan at least 1-2 hours for each
exam. Any exam taken after the
scheduled exam days will be worth (maximum) half credit unless prior
arrangements are made with the instructor.
The final exam is
comprehensive and will also be administered using Learning Suite, during finals
week (not during LS assigned time in class.) There is no makeup for the final exam.
Quizzes
(5% Extra credit)
Attendance quizzes are available on the class
website after each class instruction.
The quiz code will be given out during the class and expire at the
end of the next day. Quizzes
assess material covered in class and the book and help prepare students for the
exams. There is no makeup
for missed quizzes. Sharing of quiz codes is considered cheating.
Grades
Your grade will be
based on programming assignments (60% + 10% extra credit), exams (40%), and
attendance quizzes (5% extra credit) as follows:
|
·
Programming assignments (60%) § Lab 1: Grades
– 6% § Lab 2: SNAP – 6% § Lab 3: Linked List
– 6% § Lab 4: Iterator
– 6% § Lab 6: Railroad
– 7% § Lab 7: Maze – 7% § Lab 8: BST – 7% § Lab 9: Pokémon – 8% § Lab 10: Quicksort
– 7% § Bonus Lab 5: Expressions
– 5% § Bonus Lab 11: AVL
– (5% Extra credit) ·
Pre-exam – 2% ·
Midterm I + II – 20% ·
Final – 18% ·
Attendance Quizzes – (5% Extra credit) |
Grading Scale:
|
Miscellaneous
Do’s:
·
Do have a valid
email address and check your email often.
·
Do complete your
work on time. Partial credit will
be awarded.
·
Do discuss labs
and course material with your classmates and study groups but submit your own
work.
·
Do use TA time
for specific questions.
·
Do break out the
pencil and paper and come prepared to participate in class.
Don’ts:
·
DO NOT post your work on a public repository (e.g. github, Learning Suite,
Bitbucket, etc.)! We troll often
– posting lab solutions, exam preps, and quiz answers will result in a
failing grade for the course.
Private repositories are encouraged.
·
DO NOT share your work or submit someone else’s
work. Submitting others’ work
is considered cheating for which you will receive an E grade for the class and
be reported to the Honor Code Office.
Your source submissions will be compared with past and current submissions. No grade is worth the consequences of
dishonesty!
Grading Verification and Appeal Policy
It is the student’s responsibility to verify
that lab, homework, and exam scores have been correctly recorded in Gradebook before the last day of
class. Please disregard
Gradebook’s grading system (ie, final grade,
maximum points, etc.) until further notice.
Academic Honesty
The Honor Code includes a statement of standards
regarding academic honesty.
Academic honesty includes completing your own homework, programming
assignments, midterms, and final.
Students should work together to help each other understand material but
should always turn in their own work.
Examples of academic dishonesty include sharing code for assignments
with other students, turning in someone else’s code as your own, sharing
exam material with other students, and cheating on an exam. Any violation of academic honesty
standards will result in failing the class. All violations of academic honesty are
documented and reported to the Honor Code office.
Posting,
downloading, or viewing any classwork on a public repository such as GitHub is considered
cheating. This policy applies even after this class ends – grades can be
changed at any time!
Preventing Sexual Harassment and Discrimination
Title IX of the Education Amendments of 1972 prohibits
sex discrimination against any participant in an educational program or
activity that receives federal funds.
The act is intended to eliminate sex discrimination in education. Title IX covers discrimination in programs,
admissions, activities, and student-to-student sexual harassment. The BYU policy against sexual harassment
extends not only to employees of the university but to students as well. If you encounter unlawful sexual
harassment or gender based discrimination, please talk
to your professor; contact the Equal Employment Office at 378-5895 or 367-5689
(24-hours); or contact the Honor Code Office at 378-2847.
Students with Disabilities
Brigham Young University is committed to providing a
working and learning atmosphere which reasonably accommodates qualified persons
with disabilities. If you have any
disability which may impair your ability to complete this course successfully,
please contact the Services for Students with Disabilities Office
(378-2767). Reasonable academic
accommodations are reviewed for all students who have qualified documented
disabilities. Services are
coordinated with the student and instructor by the SSD Office. If you need assistance or if you feel
you have been unlawfully discriminated against on the basis
of disability, you may seek resolution through established grievance
policy and procedures. You should
contact the Equal Employment Office at 378-5895, D-282 ASB.
Disclaimer
This syllabus is subject to change during the semester
in favor of the student as deemed necessary by the instructor. It is the student’s
responsibility to stay current with class policies and check the class
website, Learning Suite, and their email often during the week.