Content Calendar

CSE 21 Spring 2022

Mathematics for Algorithms and Systems

About the Course

Welcome to CSE21! 

This course will cover mathematical concepts used to model and analyze algorithms and computer systems. Topics include counting techniques (inclusion-exclusion; recursive counting; permutations and combinations), data representations, analysis of algorithms (order notation; time complexities; loop invariants), recurrence relations, graphs, trees (data structure representations; basic graph algorithms; special classes of graphs), and basic probability and its applications.

Prerequisites

The main prerequisite is CSE 20 or MATH 15A. It is sufficient to know basic propositional and predicate logic, basic proof techniques (including mathematical induction), basic mathematics (algebra, geometry, trigonometry, and calculus), a basic understanding of computer programming, 

Learning Outcomes

• Learn and use strategies to count sets of objects including strings over a finite alphabet, permutations, k-element subsets, fixed-density binary strings, etc.
• Learn how to solve recurrence relations and use them to help with applications such as counting.
• Understand how to encode information efficiently into binary strings.
• Analyze loop-based and recursive algorithms.
• Understand how to use Asymptotic notation when describing runtimes of algorithms.
• Learn basic graph terminology and model different problems using graphs and graph algorithms
• Learn basic discrete probability terminology and theory.

(Pandemic Resilience Instruction:)

Spring 2022 feels like the first quarter post-pandemic. We were all kind of blindsided with Omicron last quarter and so we should all be cautious about what we expect to happen. We will keep a close eye on university policies and will inform the class whenever there is a change to our class policy.

I will be giving lectures in-person. I will also offer remote support throughout the quarter. Throughout the quarter, the "in-person" lectures will be live-streamed through zoom and recorded via "podcast.ucsd.edu". The exams will be offered "in-person" or "remote" and each student can choose which type of exam they prefer. This way we can be ready for whatever lies ahead and also give students the option of how they want to interact with the class.

First and foremost is the health and safety of everyone.  Please do not come to class if you are sick or even think you might be sick.  It is likely that the university will be requiring masks and "symptom screeners" and/or "covid tests". We expect all students to follow the rules. With all of this in mind, we encourage all students to come to class when they can, but will also provide as much of the class materials as we can in a remotely viewable format. The lectures are designed to engage students in real time with opportunities for questions and discussions between instructor and students and also between students and other students.   We will also have some ways for students who participate remotely to engage in discussions with the instructors and other students, but cannot guarantee the full experience for remote students. 

(Personal note: Last quarter (Winter 2022), we started online and returned to campus mid-quarter. After that, I ran my classes in a similar way. I am hopeful to expect that Spring quarter will be fully in person but I am a bit wary. For that reason, I have decided to continue offering the remote option for Spring 2022 mainly due to the fact that I do not know what the future will hold. There are many things about teaching remotely that I found to be great and I will try to incorporate some lessons learned from my remote teaching experience. I am excited and hopeful to teach a quarter fully "in-person". I will try my best to bring a classroom experience that is the best of both worlds.
-Miles Jones) 

 

Instructor and Course Staff

name role email Miles Jones Instructor mej016@eng.ucsd.edu   Lecture zoom link: https://ucsd.zoom.us/j/98581709157 10-11:30 on Wednesday (zoom) 1-2 on Thursday (in person CSE 4208) (also on zoom starting week 2.) Anuj Ahuja TA aahuja@ucsd.edu Akhila Chekuri TA akchekur@ucsd.edu Rajeswari Mahapatra TA ramahapatra@ucsd.edu Madhav Nilesh Wagle TA mwagle@ucsd.edu Tianyi Yu TA tiy059@ucsd.edu Yifan Chen Tutor yic057@ucsd.edu Yilang He Tutor yih022@ucsd.edu Ruoyu Hou Tutor rhou@ucsd.edu Albert (Jiechen) Li Tutor ajl015@ucsd.edu Ruichen Li Tutor rul014@ucsd.edu Zhichao Liu Tutor z5liu@ucsd.edu Tyler Yu Tutor tiy008@ucsd.edu Zhaochen Zhu Tutor zhz049@ucsd.edu

For information of office hours, see below:

To make an appointment for a 1-on-1 with a TA/tutor, follow the instructions in this spreadsheet:

1-on-1 signup sheet

 

Course Resources

Piazza Signup Link: piazza.com/ucsd/spring2022/cse21

Gradescope Signup Code: 
https://www.gradescope.com/courses/381992
RW857Z

 

The main resource for this class will be the lecture slides. The textbook is a great resource to accompany the course but the course will not be following the textbook chronologically so be warned.

The textbook for this course is

Kenneth Rosen   Discrete Mathematics and its Applications, Kenneth Rosen, McGraw Hill, 7th edition.

The textbook's companion website has extra practice problems and resources. In particular, the Self Assessments and the Extra Examples for each chapter are great practice materials. Access the companion website here.  Earlier editions contain almost all of the material we will reference, and can be bought used often quite reasonably.  Just be sure to double-check locations for references  because we will use the  chapter and page numbers for 7th edition.  

You may also wish to look at the following textbook as a supplementary resource.

Jenkyns, Stephenson   Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer
The full pdf of this book is available for free download from a UCSD internet connection at:

http://link.springer.com/book/10.1007%2F978-1-4471-4069-6

Another helpful book is:  Daniel Solow's
How to Read and Do Proofs: An Introduction to Mathematical Thought Processes
While primarily for mathematics majors, it also is a general reference that can be used by anyone reading or doing proofs.

Typesetting (LaTeX) Resources

All submitted homework for this class must be typed. Diagrams may be hand-drawn and scanned and included in the typed document. You can use a word processing editor if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) but you might find it useful to take this opportunity to learn LaTeX. LaTeX is a markup language used widely in computer science and mathematics. The homework assignments are typed using LaTeX and you can use the source files as templates for typesetting your solutions.

If you have never used LaTeX, we recommend cloud resources that don't require you to download and install LaTeX on your local machine. A good example is Overleaf (Links to an external site.), which has lots of documentation (Links to an external site.). Overleaf works similar to Google Docs in that all members can edit the file in parallel and changes are updated in real time. There is a way to directly invite group members to your document, but the free version of Overleaf only allows two people to work at the same time. To get around this, turn on link sharing: Click on “Share” in the top right, Click “Turn on link sharing”, Copy the displayed link and share it with your group members. To export your work, click on the “Download PDF” button on the right-hand side If you want to export the raw source files, click on the “Menu” button in the top-left, then click on “Source”

This open source LaTeX reference (Links to an external site.) can be helpful when getting started, and you can use the .tex source of all the files we use in class as templates.

Alternatively, you can use Google Docs, which is available through your @ucsd.edu account. You can create documents and then share them with your group members with manual invites or a shareable link. Google Docs has a LaTex add-on that lets you type formulas in a math typesetting environment: search for "Auto-LaTeX Equations" if you want to try this option. You'll need to use the display environment (start and end with $) for all the portions you want rendered with LaTeX.

You will be deducted 1 point per handwritten question.

Time and Location

Date	Day	Time
Lecture	Tu/Th	8-9:20am	WLH 2001
Discussion Section	Fridays	10:00-10:50am (A01) 12:00-12:50pm (A02)	LEDDEN MOS
Final Exam	Thursday, June 9	Scheduled for 8:00am-11:00pm Details to come	TBD

• 
  

  Lectures and review quizzes:

  •  The lectures will be taught remotely for the first two weeks (Jan 4-Jan 14) and then in person for the rest of the quarter (unless otherwise specified.)
  • The lectures will also stream on zoom in real time.
  •  The lecture slides will be posted before class on the content calendar link.
  •  You may interrupt lecture to ask questions, make comments or express doubts (For those of you in class, you can raise your hand and for those via zoom, you can use the chat feature. There will be TAs monitoring the zoom chat.)
  •  All lectures will be recorded and posted for students to watch when they want.
  •  If you are in class via zoom, you are not required to have a webcam.
  •  There will be a short review quiz each lecture,  open until the Sunday of that week, with the same due date  for  both Tuesday and Thursday's lecture.  You will have unlimited attempts
  
  

Coursework and Grades

Assignments/Coursework

Your grade will be based on the following:

• Homework
• 1 Midterm
• 2 Tests
• Review Quizzes
• Final Exam

Homeworks

Homeworks can be downloaded from the content calendar.

Homework should be done in groups of 1-4 people. So you may do them on your own if you prefer not to work in a group. You are free to change group member at any time throughout the quarter. Problems should be solved together, not divided up between partners.

We will drop the lowest homework score.

Homework solutions should be typed (NOT HANDWRITTEN) and turned in through Gradescope by 11:59pm on the due date. No late homework will be accepted. You will be able to look at your scanned work before submitting it. Please ensure that your submission is legible or your homework may not be graded. You may resubmit updated versions of your homework up until the deadline. Only your most recent Gradescope submission will be graded.

Standards for evaluation

Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. This means that unless it says: "no justification necessary" then we expect a written justification.

Collaboration Guidelines for Homework

Students are encouraged to collaborate on homework assignments. You may work in groups of up to four students. Your group will submit one assignment and Gradescope will give you the opportunity to add all of your group members to the assignment. Groups do not have to be the same people for every assignment. You can change group members at any time.

If you are discussing problems with students outside of your group, please only share hints and basic techniques. DO NOT share your answers or allow other students to copy your written work. The bottom line is to submit YOUR OWN work. If we find that your work is too similar to another group's then you may be suspected of an academic integrity violation.  All students whose names are on the assignment must have participated in answering all questions, at the minimum by carefully proof-reading the submitted answers.  If there is a member of your group that did not participate, you cannot list them as a group member for this assignment.  If some other student or teaching staff gave you a tip that was particularly useful, please give them an acknowledgement in the assignment. That will help us avoid unnecessary accusations of academic integrity violations.

You may not collaborate with anyone outside of the class. You are not permitted to ask homework questions to message boards or websites such as Chegg.

You may use some materials not from class, such as other textbooks, notes from previous sections of the class, Khan Academy videos or something similar, but with some caution. If an outside source has something relevant to a particular homework or exam problem, you must give the source a reference when you submit your assignment.  We will review how similar the reference is to your answer.  If it is too similar, you may lose some points for the assignment, but as long as you give the reference, it will not be an Academic Integrity issue.  

Review Quizzes

There will be a review quiz for every lecture.

This adds up to 19 total review quizzes.

You will have until the following Sunday to complete the review quizzes of the preceding week.

You will have unlimited attempts on each quiz.

Each review quiz is worth 1 point. You will get whatever fraction of 1 based on how well you did on the review quiz.

In order to get the full 5% points for review quizzes, you must earn 16 points.

Each point less than 16, the percentage will go down by 1 percent:

16+:   5%

15:     4%

14:     3%

13:     2%

12:     1%

11-:    0%

Test

The tests will be administered on Canvas. The questions are randomly selected from a question bank. You will have 80 minutes to complete the test during the day of the test (24 hour window.) After the test results have been posted, you will have the option of doing a "re-test" where you can earn up to 1/3 the points you missed from the original test. You may openly ask for help for the "re-test" and you will have unlimited attempts throughout the weekend.

Midterm

There will be one midterm. 

It will be 15% of your grade.

The midterm will be administered during the scheduled classtime (80 minutes). You have the option of doing the midterm in person or remotely. The midterm is open-notes but it is forbidden to discuss the midterm while it is happening.

 

Final Examination:

The final examination will be held at the date and time stated in the course calendar. It is your responsibility to ensure that you do not have a schedule conflict involving the final examination. I will enable a remote exam for students unable to physically come to the exam room, but this will be only available during the exam time.

Grading 

Course Policies

Academic Integrity

In this course we expect students to adhere to the UC San Diego Integrity of Scholarship Policy.   This means that you will complete your work honestly, with integrity, and support an environment of integrity within the class for which you are tutoring.  Some examples of specific ways this policy applies to CSE 21  include:

• Do not discuss solutions to homework problems with people besides your homework partner (except during office hours, with the instructional team).
• Do not share written solutions with other groups.
• Do not collaborate or copy exams.
• Follow the golden rule for AI:  Always give credit for any outside help on any assignment, except for those whose job it is to help you (Instructors, TAs, tutors, the textbook, and class handouts)
• You should not attempt to search for homework solutions or exam solutions online or in sources outside of the course content. (Example: you should not consult content from CSE 21 of past quarters.) If you accidentally stumble upon a homework solution in such an outside source you should cite it in your homework solution. If your solution proves to be too similar to the cited one, you may lose credit on the problem, however failure to cite the other solution will be treated as academic dishonesty.

 

Collaboration Policy

For homework collaboration policy, see the paragraph above.

For the exams, you are not permitted to collaborate with anyone else (including people from outside of the class like message boards or Chegg). We will give you the opportunity to ask questions to the teaching staff during exams.

Regrade Policy

Please be prompt (three days) in reporting to your TA any errors in the grading of your work, or in the recording of your grade. All grades become permanent three days after they are recorded. Regrade requests for homework assignments must be made on Gradescope. Please note that by requesting a regrade for a problem, it will be completely regraded and your grade may go up or down.  When you make a regrade request, you should specify exactly what the mistake in grading is, i.e., the wrong rubric item was selected or the rubric itself is inaccurate.  Vague requests for more partial credit will not be granted.

Late or Missed Assignments/Missed Exam Policy

We will drop your lowest homework. Other than extenuating circumstances, there is no credit for late or missed assignments.

Technology Policy

For homework assignments and for exams, you are permitted to use calculators.

Outside Tutoring

Individuals are not permitted to approach students to offer services of any kind in exchange for pay,  including tutoring services.  This is considered solicitation for business and is strictly prohibited by University policy.

Resources for Students

Getting Help

We provide many office hours and 1-1 sessions. Please use them. This class can be challenging if you don't engage with the teaching staff.

 

The IDEA Engineering Student Center, located just off the lobby of Jacobs Hall, is a hub for student engagement, academic enrichment, personal/professional development, leadership, community involvement, and a respectful learning environment for all.  The Center offers a variety of programs, listed on the IDEA Center Facebook page at http://www.facebook.com/ucsdidea/ (you are welcome to Like this page!) and the Center website at http://idea.ucsd.edu/ .  The IDEA Center programs support both undergraduate students and graduate students.

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 an 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/ .  

Students with Disabilities

We aim to create an environment in which all students can succeed in this course.  If you have a disability, please contact the Office for Students with Disability (OSD), which is located in University Center 202 behind Center Hall, to discuss appropriate accommodations right away.  We will work to provide you with the accommodations you need, but you must first provide a current Authorization for Accommodation (AFA) letter issued by the OSD.  You are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance so that accommodations may be arranged.

Basic Needs/Food Insecurities

If you are experiencing any basic needs insecurities (food, housing, financial resources), there are resources available on campus to help, including The Hub and the Triton Food Pantry.  Please visit http://thehub.ucsd.edu/ for more information.