Advanced Data Structures (UCSD CSE 100)

Niema Moshiri (Instructor) Sander Valstar (Instructor) Joe Gibbs Politz (Instructor)

Basics - Schedule - Staff & Resources - Grading - Policies

This course will focus on high-performance data structures and supporting algorithms. You will use and implement of data structures like (un)balanced trees, graphs, priority queues, and hash tables. You will also learn how to make sophisticated use of memory management, pointers, and recursion in programs, and analyze them with theoretical and practical performance analysis.

We will explore these topics interactively in lecture, you will implement programs to practice your programming skills, and you will reflect on this learning through your own program designs.

This web page serves as the main source of announcements and resources for the course, as well as the syllabus.

Basics

• Q&A Forum: Discussions on https://piazza.com
• Gradescope: https://www.gradescope.com [an invitation will be sent in the first week]
• Readings/quizzes/drill assignments: Stepik class signup

Lecture Problem Solving Sessions

Content in the course will be mostly delivered via pre-recorded videos and the Stepik textbook.

We are splitting the normally-scheduled lecture sections into multiple problem-solving sessions, which occur both within the scheduled lecture time and at other times throughout the day. In these, you will work in groups to complete problems related to the homework and programming assignments, with Q&A and guidance from the instructors. The different sessions will mostly focus on the same problem-solving tasks – you are welcome to attend just one or as many as you would like. The Tuesday/Thursday sessions are 45 minutes, and the Mon/Wed/Fri sessions are 30 minutes.

The motivation for this is that most of our lectures are typically split between lecturing and intermittent discussion, Q&A, and peer instruction with clickers. Rather than try to replicate rich in-class interactions across time zones, physical distance, and electronic tools, we split the content delivery (lecture) part from the problem-solving/interaction part. So you should think of spending the same amount of time on “lecture” as you would normally (about 150 minutes per week), but about half will be spent on videos on your own time, and about half will be in problem-solving sessions.

(Virtual) attendance at the sessions is not required, but it is encouraged. You’re also encouraged to virtually attend sessions on the day in which you are enrolled, though you can attend any and all of them. The sessions are shown in the calendar below. Each entry has a link to a Zoom meeting that you can join at the specified time.

Slide decks can be found here.

Problem solving sessions will be recorded with recordings posted on the corresponding calendar items below.

Discussion Sections

Discussion sections will demo tools and answer questions about the programming assignment specifications. Starting Thursday of Week 1, a video on the relevant tools and programming assignment will be available on the course schedule. Discussion sections will 30 minutes long and allow you to ask clarifying questions on the programming assignments and tools. You are encouraged to watch the videos before attending discussion. The videos will be posted and linked in the Schedule below.

Attendance is highly recommended but not required. You can attend any of the sections. These discussion sections will all be held via Zoom and will be 30 minutes long where you can ask questions about tools and the programming assignments. The link will be the same for all discussion sections.

Discussion slides can be found here.

Zoom Link: https://ucsd.zoom.us/j/640188624
Meeting ID: 640 188 624
Find your local number to call in: https://ucsd.zoom.us/u/aph8Ilzn8

Discussion	Time
A01	Th 7-7:30pm
B01	Tu 7-7:30pm
C01	Mon 4-4:30pm

Exams

The course will have a midterm exam and a final exam, both of which will be given asynchronously and electronically. Exams will allow the use of notes, readings, and other online resources. You cannot collaborate with other students on exams, as they are individual assessments.

The midterm will be have its exam time centered on Wednesday, April 29. The final exam will have its exam time centered on Thursday, June 11. Detailed instructions will be released with the exams, but you should make sure that you have three hours free some time the day of the exam in which you can focus and complete an examination that may require fairly continuous internet access during that time. We’ll release more detailed hours as we get information about the time zones in the class and availability of students, but this is a good overall schedule you should plan for.

Exams will use Canvas or Gradescope test-taking features.

Schedule

The schedule below outlines topics, due dates, and links to assignments. In a typical week, by 5pm Monday before class all due dates, readings, and notable events in the course until the following week will be posted here. So if you check the schedule at the beginning of the week, you’ll know when all reading quizzes, programming assignments, etc. will be due. We will often have the schedule confirmed more than a week out, but we’ll always be at least a week ahead.

Staff & Resources

Staff

Joe Gibbs Politz (Instructor)

Niema Moshiri (Instructor)

Sander Valstar (Instructor)

There are dozens of staff to help with your learning, and a few kinds of help sessions you can attend.

The first is office hours, held by TAs and instructors at the times listed below. Office hours are a great place for any kind of question about the course, from help with your assignment to clarifications about material in lecture to questions beyond what we cover in the course.

Since we’re remote, there are some logistics to consider for office hours. We typically offer office hours as a group activity – more than one person can be in our office getting help and participating in discussion at a time. That will also be the case with remote hours. You can click on any of the Calendar events below to see a corresponding Zoom link that you can join. When you join you’ll initially be in a waiting room – think of this as like being outside the office right before we tell you to come in. We’ll usually admit you pretty quickly, and then you can ask any questions you have as they fit into the ongoing group discussion.

If you have a private question, you can send a chat message directly to the TA or instructor in the room that you have a question that needs to be asked privately. Examples of private questions are those about grades or a personal situation that requires a special accommodation. We will arrange for part of the time to be just you in the room (moving others to the waiting room as necessary). We would prefer that any questions about course content always be asked to the group so that everyone can benefit from the resulting discussion.

The second is open lab hours where tutors give one-on-one help with programming tasks and course content. For these sessions, you should submit a ticket on https://autograder.ucsd.edu to request help. There is an extra step since we are remote – along with your ticket, you should submit a link to a Zoom meeting that you create and start. The tutor will join that Zoom meeting, chat with you to help you with your issue, and then leave the meeting. You can, for example, start a screenshare with your code before the tutor arrives to help them immediately see your issue and present what you’re seeing. The student procedures for open lab hours can be accessed here.

The third is through Piazza. Online discussion and Q&A for the class will be available on Piazza: sign up to join the class here and view the discussion forum here. Important announcements from the course team will be pinned at the top of your feed. When you set up your account, you can select the frequency for email notifications of messages and discussions on Piazza.

For each programming assignment, we’ll make a frequently-asked questions discussion on Piazza. You should refer to that during the assignment if you get stuck or have questions come up; we’ll use it to aggregate common issues. You can feel free to comment publicly on those discussions, but do be conscious that other students can see what you post, so posting solution code for a project or an answer for a homework is an academic integrity violation.

The default is that posts are private to discourage accidentally over-sharing solution code. If your post is a question about content, lecture, course technology, logistics, etc, please do ask it publicly so others can benefit from the answer.

Finally, you can always send a private message on Piazza to ask any question about the course. Please don’t message individual course staff privately unless they’ve asked you to, and please don’t message only the instructor with a content question. The course staff as a whole works together to make sure these messages get prompt responses (often by adding to the frequently asked questions post).

Asking & Answering questions on Piazza

Piazza is an online discussion board where we can make announcements and students can ask questions. Both we (the course staff) and your classmates can answer your questions. There are a few kinds of questions you should ask on Piazza:

• Private questions about closed programming assignments for clarification
• Private questions about your grade / account
• Public questions about open programming assignments
• Public questions about the content of lecture, discussion, lab, and any readings

For each assignment, you will find a Frequently Asked Questions post, where we will answer all common questions we receive in office hours and via (private) Piazza posts. If you ask a question that’s already answered in that post, we’ll likely just send you a link to that post. That post will be updated as new important questions and answers come in.

When answering questions, be polite, be clear, and assume the best intentions of the person asking. If it turns out you make a mistake or were wrong, admit it with a smile (emoji are great for this 😊), and make sure the correct information is clear. Above all, keep in mind that the course is a community whose goal is to foster a positive learning environment for everyone. For public discussion, note that answers from your classmates are not official! They could be downright wrong or misleading, completely by accident. “My classmate said so on Piazza” is not a legitimate justification in most arguments, though they may indeed lead you in helpful directions.

Grading

Your grade will be calculated from:

• 44% homeworks (6-8 total)
• 16% engagement / quizzes (per-lecture/per-week)
• 20% programming projects (2 large projects)
• 20% exams (midterm and final exam combined)

Homeworks

Homeworks will be a mix of programming tasks and specific questions about data structures, and will be partially automatically graded and partially graded by course staff. These will be released on a weekly basis for the first part of the course.

After the deadline of each programming assignment, we’ll open up a new assignment where you can resubmit the autograded portion. You can earn back up to 50% of the missed credit on the autograded portion of the assignment by submitting to these. This includes the case where you didn’t submit to a particular assignment, and can still get half the credit on resubmission.

Engagement

Each lecture comes with some quiz/engagement material, either Gradescope online assignment or some steps to complete in Stepik. The required material will be clearly labelled with each lecture. You must engage with at least 8 weeks’ worth of the required engagement material for a full score, and engagement scores will be calculated on a week-by-week basis.

In terms of a formula if you want to count more precisely:

• Each quiz counts for credit if you submit and get at least 1/2 of the questions correct
• Each week counts for credit if you get credit for 2/3 of the quizzes
• Weeks are counted independently (we are not totalling all of the quizzes and dividing by some denominator)

Reading quizzes are open to collaboration, feel free to discuss them with your classmates!

Programming Projects

There will be two larger programming projects that are assigned in the later part of the course. These will combine data structures knowledge you acquire from class and homework with the pragmatics of writing a significant application that demands high performance. These will be completed in a C++ programming environment that you will gain some practice with through homeworks.

Exams

The midterm and final combined are worth 20% of your grade:

• If your final exam score is higher than your midterm exam score, the final counts for 15% and the midterm for 5%. This includes the case where you don’t complete the the midterm exam.
• If your final exam score is lower than your midterm exam score, the final counts for 10% and the midterm for 10%. This includes the case where you don’t take the final exam.

You must take and pass at least one of the two exams to pass the course.

Final Scoring

After your weighted average is calculated, letter grades will be assigned based on the following grading scale:

A+	A	A-	B+	B	B-	C+	C	C-	D, F
>97	93-96.99	90-92.99	87-89.99	83-86.99	80-82.99	77-79.99	73-76.99	65-72.99	Below 64.99

We may adjust the above scale to be more lenient (depending on the overall class performance), but we guarantee that we will not adjust the scale to make it harder to get a better grade.

Note that for Spring 2020, all students have the option to take the P/NP option for any or all of their courses, and can make the decision as late as week 10. More information is available in this memo from the CSE department so you can make the best decision for your situation.

Policies

Academic Integrity

We have a missive on academic integrity you must agree to that details some examples of what we expect in terms of collaboration in the course.

Note that with the course remote, one challenge we face as an instructional team is verifying that students are submitting their own work. We typically use exams to mitigate this particular challenge to academic integrity, since it requires an in-person, ID-checked assessment. Assignments and exams will come with specific policies for what types of collaboration is allowed, but we have one course-wide policy – we may reach out to students to schedule a check-in on their understanding of work they’ve submitted if we’re suspicious about an academic integrity violation. This would involve a videoconference with a TA or instructor to check that the student has the understanding demonstrated by their work.

We don’t expect to use this option much (certainly you are a student that acts with integrity!), but we state it clearly in the syllabus in case it becomes necessary so it isn’t a surprise to anyone.

You should be familiar with the UCSD guidelines on academic integrity as well.

Pair Programming Guidelines

Update from Professor Paul Cao’s CSE 100 Policy

In CSE 100 you may choose to do the projects either on your own, or with a partner. If you choose to work with a partner on programming assignments, we require that you engage in a true “Pair Programming” approach. In pair programming, two programmers share one computer. One person is the “driver,” who controls the keyboard and mouse. The other is the “navigator,” who observes, asks questions, suggests solutions, and thinks about slightly longer-term strategies. The two pair programmers switch roles every 20 minutes. We suggest you use a shareable online timer to keep track of when it is time to switch roles.

Please read this entire document, but the highlights are:

• Once you commit to working with a partner or working solo by starting the assignment, you are committed to either staying solo or staying with your partner. If you must split, you must contact your instructor immediately for permission.

• If you choose to work with a partner, you must engage in true pair programming. Splitting the work is a violation of the academic integrity agreement for this course and will result in an F and an academic integrity violation on your record.

• You may choose your own partner and your partner may be from any section of this term’s CSE 100.

• Due to everything being remote you MUST be on a zoom call or something similar where you can screen share and you are both able to look at the code at the same time.

The most important rule of pair programming is that you must work together, co-located, on the same part of the assignment at the same time. Splitting up the work on a project is considered cheating.

We recommend you use the Piazza feature “Search for Teammates!” to find a partner if you are having trouble. Working with a partner is always optional. You will need to arrange times to meet. We expect you will need at least 6 hours each week to work with your partner. We expect everyone to be flexible and professional in arranging those times as necessary; if your schedule is highly constrained, explore possible meeting times with your prospective partner before you commit to the partnership.

Choosing a Partner

You should try to pick a partner whose experience and skill level with programming is similar to your own. This may not always be possible and it is sometimes hard to compare skill levels, but students tell us (and other data support) that pairs are most productive when the partners start at about the same level.

Still, people often pair up with another whose skills are different. This happens more often than not, as no two people have an identical skill set. The differences may be great or small, but this is exactly like most real-world working situations. Part of accomplishing a task is to get the most out of each member and make each member stronger and more productive on subsequent tasks.

Students bring different strengths to the process, regardless of how much experience they have had with programming. Both experienced and inexperienced students will need to draw on their reasoning and problem solving skills. A more experienced partner may sometimes feel frustrated or slowed down by a less experienced partner, but the experienced partner still benefits from the teamwork in many ways. The less experienced partner’s requests for clarification often uncover flaws in an approach or solution; the exercise of providing a clear explanation solidifies and deepens the explainer’s own understanding and the teamwork and communication skills they gain have great value in both the academic realm and the job market.

It is each partner’s job to understand the whole task; that means asking questions when necessary and answering them when possible.

It may be instructive to read a selection of students’ partner evaluation comments from similar courses that have used pair programming; they give a picture of what good partnerships are like (and a few disasters, too). Read Pair Programming Evaluations from the University of California, Irvine Bren School of Information and Computer Sciences.

Dealing with Differences/Splitting from Your Partner

Once you begin your assignment, you are locked into working solo or with your partner. If you believe your partner is not participating appropriately in pair programming (e.g., she or he does not keep in touch, does not come prepared to work on the assignment, or does not seem to be engaged in the process) please first address your concerns to your partner, and try to agree on what should be done to make the pair programming experience work well for both of you. If that approach is not successful, explain the issues to your teaching assistant or the instructor, who will work with you and your partner to improve the situation. You must get permission from your instructor to split from your partner. You should never simply complete the assignment without an agreement from your partner and the instructor that this is the best course of action. Doing so is a violation of the academic integrity policy for this course.

How Pair Programming Affects Your Grade

On the Projects where you choose to partner, you and your partner will receive the same score on your code.

When in Doubt, Seek Clarification

Pair programming is shown to help, not hinder, your successful completion of a course. It is important that you understand the processes and expectations up front so you can gain the most benefit. If you are unsure of any of the aspects of pair programming and how it is implemented in the course, see your instructor right away.

Late Work

In general, late work is not accepted. However, most of the categories of submission for the course allow some missed submissions without having a large impact on your grade, and you only have to submit a subset of them for full credit.

Regrades

Mistakes sometimes occur in grading. Once grades are posted for an assignment, we will allow a short period for you to request a fix (announced along with grade release). If you don’t make a request in the given period, the grade you were initially given is final.

Diversity and Inclusion

We are committed to fostering a learning environment for this course that supports a diversity of thoughts, perspectives and experiences, and respects your identities (including race, ethnicity, heritage, gender, sex, class, sexuality, religion, ability, age, educational background, etc.). Our goal is to create a diverse and inclusive learning environment where all students feel comfortable and can thrive.

Our instructional staff will make a concerted effort to be welcoming and inclusive to the wide diversity of students in this course. If there is a way we can make you feel more included please let one of the course staff know, either in person, via email/discussion board, or even in a note under the door. Our learning about diverse perspectives and identities is an ongoing process, and we welcome your perspectives and input.

We also expect that you, as a student in this course, will honor and respect your classmates, abiding by the UCSD Principles of Community (https://ucsd.edu/about/principles.html). Please understand that others’ backgrounds, perspectives and experiences may be different than your own, and help us to build an environment where everyone is respected and feels comfortable.

If you experience any sort of harassment or discrimination, please contact the instructor as soon as possible. If you prefer to speak with someone outside of the course, please contact the Office of Prevention of Harassment and Discrimination: https://ophd.ucsd.edu/.

Consent to Participate in Educational Research

University of California, San Diego
Consent to Act as a Research Subject
Investigating the Impact of Pedagogical Choices on University Student Learning and Engagement

Who is conducting the study, why you have been asked to participate, how you were selected, and what is the approximate number of participants in the study?
Gabriele Wienhausen, Director of the Teaching and Learning Commons, together with her education research colleagues is conducting a research study to find out more about how pedagogical choices affect student learning and experience in the classroom. You have been asked to participate in this study because you are a student in a class that is being studied or used as a control. There will be approximately 500,000 participants in this study.

Why is this study being done?
The purpose of this study is to create knowledge that has the potential to improve the learning and educational experience of students at UC San Diego and beyond.

What will happen to you in this study and which procedures are standard of care and which are experimental?
If you agree to be in this study, the following will happen: Your data from this class including grades, homework and exam submissions, and survey responses will be included in the analysis to determine the effectiveness of the pedagogical techniques used in this course compared to other similar courses.

How much time will each study procedure take, what is your total time commitment, and how long will the study last?
Your participation involves only agreeing to let us use your data in our analysis. It will require no time on your part above the time you put into this course without agreeing to the study.

What risks are associated with this study?
Participation in this study may involve some added risks or discomforts. These include the following:

1. A potential for the loss of confidentiality. We will not share your personally identifying data with people outside our research team. Data will only be kept in anonymized form for research purposes. Course data will not be used for this research study until after final grades have been posted and will be rendered confidential by removing any identifiers before analysis. Your instructor will not know whether or not you are participating in this study until after final grades have been posted. Data from students who opt out of the study will be removed prior to data analysis. Research records will be kept confidential to the extent allowed by law. Research records may be reviewed by the UCSD Institutional Review Board.

Since this is an investigational study, there may be some unknown risks that are currently unforeseeable. You will be informed of any significant new findings.

What are the alternatives to participating in this study?
The alternatives to participation in this study are not to participate. If you choose to opt-out of participating in this research study, we will exclude your data from analysis. Whether you participate will have no impact on your experience or grade in the associated class as the professor will not know who is or is not participating in the study until after final grades are assigned.

What benefits can be reasonably expected?
There is no direct benefit to you for participating in the study. The investigator, however, may learn more about how to improve student learning, and society may benefit from this knowledge.

Can you choose to not participate or withdraw from the study without penalty or loss of benefits?
Participation in research is entirely voluntary. You may refuse to participate or withdraw or refuse to answer specific questions in an interview or on a questionnaire at any time without penalty or loss of benefits to which you are entitled. If you decide that you no longer wish to continue in this study before the end of the quarter, simply respond to the online opt-out form here: https://goo.gl/forms/JSBRjEmkES6W6xYc2. If you decide to opt out after the quarter has ended, you must contact Laurel Nelson (laureln@ucsd.edu) and give the quarter and the course from which you would like your data withdrawn. You will be told if any important new information is found during the course of this study that may affect your wanting to continue.

Can you be withdrawn from the study without your consent?
The PI may remove you from the study without your consent if the PI feels it is in your best interest or the best interest of the study. You may also be withdrawn from the study if you do not follow the instructions given you by the study personnel.

Will you be compensated for participating in this study?
You will not be compensated for participating in this study.

Are there any costs associated with participating in this study?
There will be no cost to you for participating in this study.

Who can you call if you have questions?
Gabriele Wienhausen and/or her colleague has explained this study to you and answered your questions. If you have other questions or research-related problems, you may reach Gabriele Wienhausen at gwienhausen@ucsd.edu or (858) 534-3958. You may call the Human Research Protections Program Office at 858-246-HRPP (858-246-4777) to inquire about your rights as a research subject or to report research-related problems.

Your Consent

If you consent to participate in this study and are at least 18 years old, no action is needed. If you DO NOT consent to participate in this study, or you choose to opt-out at any time during the quarter, please submit this form online at https://goo.gl/forms/JSBRjEmkES6W6xYc2. Your instructor will not have access to the list of students who opted out until after grades are posted. Note that you must separately opt-out of the study for each course involved in this study.