Course: CSCE 310H-001 Honors: Data Structures and Algorithms
Days, Times, and Locations: MWF (Monday, Wednesday, and Friday) 12:30 pm - 1:20 pm, Avery 119
Instructor: Hau Chan
Contact: (office) Avery 363, (email) hchan3@unl.edu, (phone) 402-472-5091
Office Hours: MWF 12:00 - 12:30 pm and/or by appointment (please email me directly)
Homework Submission Email: Email me directly before midnight or hand it to me in classes by the due date
Submission Format: [assignment]_firstname_lastname.pdf and/or .zip (HW1_Hau_Chan.pdf)
[I would recommend you use LaTeX or Overleaf to generate your pdf document]
Grades of "Pass" or "C" or better in CSCE 156/156H or SOFT 161 and CSCE 235/235H.
In our everyday life, we (perhaps, unknowingly) encounter problems involving taking input and returning output that satisfies some (possibly optimization) objective. For example, finding the cheapest priced product among hundreds or thousands of identical products (e.g., cars or tablets) online (e.g., cars or eBay), finding a matching sequence of two nucleotide sequences, or finding the shortest path/route (among all of the possible paths) to go from a given location to a given destination (e.g., home to campus).
Off-the-shelf computational tools have made our life much more convenient. Many of these above problems can be solved at your fingertips (e.g., sorting from the lowest to highest prices or using google maps to obtain the quickest route) effortlessly. For many of these problems, solving them would not have been possible without the help of carefully designed algorithms (and possibly the appropriate data structures).
What is an algorithm? What is the central role of data structures in algorithmic designs? How can we leverage data structures to solve problems more efficiently?
In this class, we will embark on a journey to understand the interplay between algorithms and data structures as well as obtain fundamental background and knowledge in various algorithmic techniques for solving (real-world) problems. In particular, the class will start by reviewing algorithm analysis, asymptotic notation, and solving recurrence relations. We will then discuss some advanced data structures and their associated algorithms, heaps, priority queues, hash tables, trees, binary search trees, and graphs. Some algorithmic techniques such as divide and conquer, transform and conquer, space-time trade-offs, greedy algorithms, dynamic programming, randomization, and distributed algorithms will be covered in this course (subject to the discretion of the instructor). Finally, the class will provide a basic introduction to computability and NP-completeness to discuss the limitation of computational power.
Techniques:
Complexity Notations, Summation, Induction, and Recursion, Brute Force and Exhaustive Search, Divide and Conquer, Greedy, Iterative Improvement, Dynamic Programming, Reductions, and Approximation Algorithms
Data Structures:
Binary Trees, Balanced Binary Trees, AVL Trees, B-Trees, Hashing, Graphs, and Heaps
Problems:
Sorting and Searching, Closest-Pair (Points), Convex-Hull (Points), Traversal and Shortest Paths on Graphs, Topological Sort on Graphs, Matrix Multiplication, Linear Programming, Maximum-Flow, Knapsack, String Matching, TSP, Vertex Cover, Maximum Subgraph, Set cover, Maximum Matching in Bipartite Graph, and Stable Marriage
The class consists of lectures (by the instructor), textbook and paper readings, (student) presentations, homework, exams, and projects. We expect the students to have Grades of "Pass" or "C" or better in CSCE 156/156H or SOFT 161 and CSCE 235/235H. The students should have some background in algorithms and basic mathematical maturity. Any other necessary and required material will be covered in the course.
In this course, you will
(1) Understand the key concepts and basic algorithmic techniques or approaches for solving algorithmic problems
(2) Understand the interplay between advanced data structures and algorithms
(3) Understand some classical algorithmic problems and their complexities, solutions, and applications
(4) Understand the limitation of computational power
Readings from the books are assigned for each class — see the lecture list for details. Please do the readings before the class. I will be using the following books for the class.
Introduction to The Design and Analysis of Algorithms (3rd Edition). This is the main textbook of the course and is the standard textbook used by other 310 courses/instructors at UNL in recent years.
The Algorithm Design Manual (2nd Edition). We will use this textbook periodically throughout the course (especially Chapter 9, which we will use it in November). I would highly recommend this book to anyone who is interested in getting an internship with Google or Facebook or any tech company.
All of them are freely available on the Internet. For additional readings, I will provide pdf copies of the readings.
Reading, homework, and presentation assignments would be available from the lecture list. There will be two major exams in this course (midterm + final). The midterm will cover the first part of the course, while the final will cover the second part of the course (and possibly the first part of the course). You will be working on a class project/presentation in this class.
Your grade is determined by the following:
Participation 10% (in-class and out-of-class off/online activities/discussions)
Midterm 15%
Final 15%
Class Project/Presentation 10% (see the below description)
Homework Assignment 50% (Late homework will deduct 10% of your homework grade per day.)
(Note: schedule periodic meetings with me to discuss your project and presentation)
Your participation and presentation grades include instructor discretion, particularly if the instructor feels your grades do not accurately reflect your true understanding of the materials. If the instructor does not know who you are, this will not reflect well on your participation and presentation grades.
Class Project/Presentation: Your class project should (1) identify a non-trivial problem of your interest, (2) introduce and analyze algorithms for solving your problem, and (3) implement algorithms and conduct simulations (e.g., running time on various input sizes and instances).
At the end of the semester, you will submit a write-up report of (1), (2), and (3) and present your problems/results in class. You are free to work in a group of 2-3 on this assignment.
Please schedule a bi-monthly meeting with me to discuss your project/idea.
Finally, your final letter grade will be determined as follow:
A+ [100, 97]
A (97, 94]
A- (94, 90]
B+ (90, 87]
B (87, 84]
B- (84, 80]
C+ (80, 75]
C (75, 67]
C- (67, 60]
D+ (60, 57]
D (57, 54]
D- (54, 51]
F (51, 0]
FACE COVERINGS SYLLABUS STATEMENT
Required Use of Face Coverings for On-Campus Shared Learning Environments*
As of July 17, 2020 and until further notice, all University of Nebraska–Lincoln (UNL) faculty, staff, students, and visitors (including contractors, service providers, and others) are required to use a facial covering at all times when indoors except under specific conditions outlined in the COVID 19 face covering policy found at: https://covid19.unl.edu/face-covering-policy. This statement is meant to clarify classroom policies for face coverings: To protect the health and well-being of the University and wider community, UNL has implemented a policy requiring all people, including students, faculty, and staff, to wear a face covering that covers the mouth and nose while on campus. The classroom is a community, and as a community, we seek to maintain the health and safety of all members by wearing face coverings when in the classroom. Failure to comply with this policy is interpreted as a disruption of the classroom and may be a violation of UNL’s Student Code of Conduct. Individuals who have health or medical reasons for not wearing face coverings should work with the Office of Services for Students with Disabilities (for students) or the Office of Faculty/Staff Disability Services (for faculty and staff) to establish accommodations to address the health concern. Students who prefer not to wear a face covering should work with their advisor to arrange a fully online course schedule that does not require their presence on campus.
Students in the classroom:
1. If a student is not properly wearing a face covering, the instructor will remind the student of the policy and ask them to comply with it.
2. If the student will not comply with the face covering policy, the instructor will ask the student to leave the classroom, and the student may only return when they are properly wearing a face covering.
3. If the student refuses to properly wear a face covering or leave the classroom, the instructor will dismiss the class and will report the student to Student Conduct & Community Standards for misconduct, where the student will be subject to disciplinary action.
Instructors in the classroom:
1. If an instructor is not properly wearing a face covering, students will remind the instructor of the policy and ask them to comply with it.
2. If an instructor will not properly wear a face covering, students may leave the classroom and should report the misconduct to the department chair or via the TIPS system for disciplinary action through faculty governance processes.
*Courses that have been granted an exception to the Face Covering Policy for pedagogical reasons are excluded. Exceptions to the Face Covering Policy are only granted after an approved health safety plan is developed.
The University's Inclement Weather Policy
Beginning Jan. 3, all instructors should include a statement on syllabi to explain the mode of communication they will use (e.g., @huskers.unl.edu email or Canvas) if in-person classes are canceled and the campus follows instructional continuity plans:
If in-person classes are canceled, you will be notified of the instructional continuity plan for this class by email or Canvas.
Students will be expected to be responsible for checking these notifications for instructional continuity assignments or virtual class meetings.
Attendance Policy
Attendance at all officially scheduled class meetings (class and lab sections) is expected. Students are responsible for knowing all the material discussed in class meetings. Changes to class and lab schedules and assignments will be announced in class or lab.
SoC's Anonymous Contact Form
The SoC has an anonymous contact form that you may use to voice your concerns about any problems in the course or SoC if you do not wish to be identified.
SoC's Email Policy
All students in SoC courses are expected to regularly check their email so they do not miss important announcements.
SoC's Academic Integrity Policy
All homework assignments, quizzes, exams, etc. must be your own work. No direct collaboration with fellow students, past or current, is allowed unless otherwise stated. The SoC has an Academic Integrity Policy. All students enrolled in any computer science course are bound by this policy. You are expected to read, understand, and follow this policy. Violations will be dealt with on a case-by-case basis and may result in a failing assignment or a failing grade for the course itself.
SoC's Resource Center
There is a Student Resource Center in Avery 12: http://cse.unl.edu/src. (UPDATE for Fall 2020)
The Computer Science Resource Center (SRC) is committed to continuing to provide support for students enrolled in Computer Science and Software engineering courses. For the fall of 2023, the SRC will be operated in person and online via Canvas.
The SRC will be staffed M-F from 10:00 a.m. – 5:00 p.m.
Students will have access to the SRC via Canvas. Students must be logged into Canvas.
SRC front-desk tutors will do their best to help students.
SRC tutors can help with some content questions, general questions, and SoC account questions
SRC tutors will direct students to the appropriate resources for specific courses when those course TAs are available for office hours.
Services for Students with Disabilities
The University strives to make all learning experiences as accessible as possible. If you anticipate or experience barriers based on your disability (including mental health, chronic or temporary medical conditions), please let me know immediately so that we can discuss options privately. To establish reasonable accommodations, I may request that you register with Services for Students with Disabilities (SSD). If you are eligible for services and register with their office, make arrangements with me as soon as possible to discuss your accommodations so they can be implemented in a timely manner. SSD contact information: 232 Canfield Admin. Bldg.; 402-472-3787; acontreras3@unl.edu.
Writing Center
The Writing Center, located at 102 Andrews Hall and satellite locations from 5-7 pm in Adele Hall , is a free service for all UNL students, faculty, and staff. You can work with an individual writing consultant on any type of writing at any stage in your writing process. For an appointment, call 472-8803 or schedule online.
Academic Support Services
You can schedule free appointments for individual academic coaching with First-Year Experience and Transition Program staff through MyPLAN. You can also take advantage of study stops--which provide individual and group study with learning consultants in a variety of disciplines--and free group workshops on topics such as time management, goal setting, test preparation, and reading strategies. See success.unl.edu for schedules and more information.
Counseling and Psychological Services
UNL offers a variety of options to students to aid them in dealing with stress and adversity. Counseling and Psychological & Services (CAPS); is a multidisciplinary team of psychologists and counselors that works collaboratively with Nebraska students to help them explore their feelings and thoughts and learn helpful ways to improve their mental, psychological and emotional well-being when issues arise. CAPS can be reached by calling 402-472-7450. Big Red Resilience & Well-Being (BRRWB) provides one-on-one well-being coaching to any student who wants to enhance their well-being. Trained well-being coaches help students create and be grateful for positive experiences, practice resilience and self-compassion, and find support as they need it. BRRWB can be reached by calling 402-472-8770.
Classroom Climate
Because the topics in this course may be emotionally charged or challenging for class members, I hope we can create an environment that is both intellectually productive and supportive for all. I realize there might be days when class members may choose to be silent. Beyond verbal participation, your active and supportive listening is also an important and valuable form of participation. I hope that we will continuously reflect upon our class processes so that we can build an inclusive intellectual community where all feel valued and supported in their learning.
Discussing Controversial Topics
Some of the topics we will discuss over the semester are likely to be sensitive and/or controversial. A variety of opinions, beliefs, and statements may surface during class discussions, some of which may be experienced as “racist,” or “anti-Semitic,” or “homophobic,” or “sexist,” or “fascist,” or “Islamophobic,” etc. You will be encouraged to express your opinions and beliefs, and to do so with respect for the opinions of other students who may hold different beliefs. In the event that controversial claims are made, you will be discouraged from labeling any classmate as “a racist,” or “an anti-Semite,” or “a fascist,” or “a bigot,” etc. Instead, you will be encouraged to respond to opinions with which you disagree by saying, “I disagree with the statement you just made and I experience it [i.e., the statement] as racist (or homophobic, or anti-Semitic, etc.) because...,” and then share your opinion with your classmates and me. All of you are encouraged to express your views and beliefs even when those views may be considered unpopular. If you have any concerns that you will have difficulty with voicing your opinions/beliefs in insensitive language, feel free to consult with me during office hours. I will be happy to assist you.
Video or Audiotaping Class Sessions
Due to the sensitive and controversial nature of some of the topics that will be discussed over the duration of the semester, all classes are closed to the Press/Media. No video or audio taping of class sessions is allowed unless you obtain my permission to do so.
Academic Honesty
Academic honesty is essential to the existence and integrity of an academic institution. The responsibility for maintaining that integrity is shared by all members of the academic community. The University's Student Code of Conduct addresses academic dishonesty. Students who commit acts of academic dishonesty are subject to disciplinary action and are granted due process and the right to appeal any decision.
Diversity & Inclusion
The University of Nebraska-Lincoln does not discriminate on the basis of race, ethnicity, color, national origin, sex (including pregnancy), religion, age, disability, sexual orientation, gender identity, genetic information, veteran status, marital status, and/or political affiliation.
Trespass Policy (Regents’ Policy 6.4.7)
The areas of University academic, research, public service, and administrative buildings of the University used for classrooms, laboratories, faculty and staff offices, and the areas of University student residence buildings used for student living quarters are not open to the general public. Any person not authorized to be or remain in any such building area will be deemed to be trespassing on University property and may be cited and subject to prosecution for criminal trespass in violation of Neb. Rev. Stat., § 28-520 or § 28-521.