CSE 331 Advice from TAs
Where students who took CSE 331 and became TAs share their experiences of how to fully utilize the class to your advantage. (And no, Atri did not pay them to say these things.)
Under Construction
This is a living document that will get updated over time. However, all the advice below is valid and you should pay attention to them!
The class is structured to your advantage
Utilize the before, during and after aspects of the course to their fullest.
Do the assigned readings before coming to class and if you get time even watch lecture videos from previous years. Atri will give you plenty of time during lecture to ask questions about the readings or the lecture itself. And of course get the most out of the assignments (Explained further below).
The assignments are separated into different parts for your convenience.
Questions 1 and 2
For Q1 and Q2, think of the algorithm and proof ideas as things that go inside a header (.h) file. They are the high level overview of how you are approaching the problem; you don’t have to be very technical here. For example, listing out all the steps in your algorithm, what proof technique are you using, what property of the algorithm are you induction on, etc.
Algorithm and proof details are the implementation inside the source (.cc) file. They are simply the detailed technical algorithm/ proof of the idea that was outlined.
More on the idea vs details divide
Always start off with the ideas. Just smashing random keys on the keyboards won’t get you anywhere with writing code and certainly would not help with proofs. In the real world, a user of your library doesn’t care about the details; just wants to know how to use it. Similarly, in your proof and algorithm ideas, briefly explain what you’re doing, how it works and why it should work. For example, if you’re using contradiction in the proof details; just state that you use contradiction on a specific property (but do specify which property).
In the algorithm and proof details, be as detailed as you can be and try to avoid loopholes (more explained below).
Question 3
For the programming part (Q3), sketch out your algorithm first. Is there anything you know about the inputs and outputs that you can use to your advantage? What data structures are you going to use? Can you incorporate parts of the algorithm that Atri showed in class and what might be some changes you would need to make?
The homeworks are released on Wednesdays and all the recitations are scheduled on Thursdays and Fridays.
Use Wednesday to at least look through the problem descriptions and think through how you would solve them; trying to fully understand what the problems are asking of you takes longer than writing out the solutions. Then go to recitation to clear any doubts that you might have.
Proofs are not going to eat you!
There has always been a negative stigma about proofs in this class. It’s just a way you can show that your work actually, well works!
A lot of students seem to think that they are worse at proofs than they actually are. A lot of proofs that you read are from books and research papers. These proofs take months and even years. We do not expect these level of proofs! Just do your best.
While developing something you write unit tests for different scenarios that you code might run into. All you’re doing in your proofs is identifying different types of inputs you might get and showing that your algorithm/theorem works for all cases.
Contradiction
You negate your assumption and then keep going until you hit a roadblock. If you hit a roadblock, it means that the negated assumption is incorrect and the original one works. That's it!
Where can it go wrong?
Argument for contradiction should work for every possible counter example. The only thing about a counterexample you claim makes the problem statement false that you can use is that, well it makes the statement false. Don’t assume more than what you should.
Induction
Induction is simply finding patterns and making sure it works for all different cases.
You might be familiar with base case $i = 0$, inductive hypothesis $i = k$, and inductive step $i = k +1$. For certain problems, you can most certainly use this, but the pattern is dependent on the type of problem.
What if you are working with trees? What will be the base case, inductive hypothesis and inductive step in your proof?
Depending on the problem, these can be as simple as base case = “works for leaf node” (don’t forget to explain why),
A sanity check
Make sure that both your base case and inductive Step use something from the definition of the problem.
Just doing case analysis?
If you think there isn’t one specific pattern you can use in your proof, break them down into smaller pieces and prove them in ways best suited for them. Break down big theorems into smaller lemmas and combine them in the end. You can always use a lemma in the proof of another lemma.
What proof technique should you use?
Unfortunately, there is no set formula on how to choose a proof technique but there are some good "rule of thumb." Some basic pointers are:
- Try and re-use an existing proof that we have seen in class as a black-box.
- If that does not work, then try and see if you can modify an existing proof to make it work.
- If the above two do not work, then try and the basic proof techniques (proof by contradiction, proof by induction etc.) and see which one works. Though do start with proof of contradiction since that seems to work in "most" cases.
However, there are no general rules/pointers. In some sense for any problem any of the proof techniques can be made to work but the result proof won't be as "natural"-- the "best" proof technique is problem specific. After you do a bunch of proofs you start developing some intuition but unfortunately we do not have anything concrete other than what I said above.
Incorrect proofs?
Don’t try to prove something beyond what the problem is asking from you. Just make sure you’re not making any “extra” assumptions that are not in the problem definition.
Whenever you assume something, justify it. Any step in your argument has to be justified and make sure that at least one step uses a property of the problem.
Don’t reinvent the wheel (Reduce, Reuse, Recycle)
If something has already been done, just reuse it!
Think of them as library function calls that you are making. In every new piece of code that you write, do you want to define something like adding a new element to a list every time? You can save a lot of time doing this.
If you have seen something completed in recitation, just state something like “look at recitation notes for week X”. If it was actually solved in full during recitation, referencing this might be all you have to do to get full points on a problem!
If you have seen something done in the book, state “look at section X.Y of the book”. Similarly, do the same for anything from the lectures, course webpage or piazza.
Precision pays
Be as precise as you can be when you are referencing such resources. Don’t be like “it’s in the book somewhere”.
Don't give up!
Listen to a champion!
Take Lady Gaga’s speech at 2019 Academy Awards to heart - “It’s not about winning or losing, it’s about not giving up."
Actively work on improving yourself and your work!
It is inevitable that you are going to make mistakes. It’s OK, we are all humans!
But do make an honest effort to improve upon them. The structure of the problems you encounter in this class don’t change. The sooner you address how to answer them, the better off you are going to be from losing points due to simple things like not stating what technique you are using in your proofs.
You are going to have some breathing room in the course.
Although there is a lot of breathing room with dropped assignments (e.g. only your 6 best homework problems are taken into consideration and your quizzes and midterm grades might not matter), don’t stop working just because of this. The great Engineers are those who never stop learning new things and are always looking to make their improvements to their projects in any way that they can.
Do not drop the earlier HWs!
Even if you do have to drop any homework, please don’t drop the earlier ones. The earlier homework problems are far simpler than the ones you get at the end of the semester. At the same time remember that as the semester progresses, you will get more comfortable with proofs and approaching these problems in general. So, focus on the feedback that you get in your earlier assignments such that you can address these issues earlier on.
Relax
While we do stress that you don't give up, don't physically exhaust yourselves.
You might have the mentality of the Avengers’ “whatever it takes!”. That’s awesome! But please take care of yourselves as well.
Don’t power through 12 consecutive hours, do 2 hours each for 6 days. The problems you encounter in this class require you to have a cool and clear head.
If you are powering through consecutive hours, you might miss something that otherwise might have been clear if you were talking regular breaks to chill.
What not to do!
sanchitb@ (Fall 19 CSE 331 TA): “Definitely don't not sleep for 48 straight hours and head straight to your algos final #guilty”
Don't let the perfect be the enemy of the good!
Always start with a simple solution and work up from there.
Consider you are in a technical interview and you know a simple solution but not the optimal solution. Would you want to spend all the time trying to get to the most optimal solution and end up falling short? Or would you rather have a good solution to start off so that you can show that you know how to solve it and then make progress from there?
Similarly, if you think that your work might not help every single user, you don’t want to just stop working. Definitely address that later, but at present focus on how you can make an immediate impact and still help a lot of people.
Do the same things with the assignments – don’t aim too high too soon; work progressively. There is certainly a time crunch, but it is a part of life that you just have to get used to. Having something is always better than having nothing.
Don't worry about your grades!
Just looking at the how the final grade is assigned seems quite daunting (you have to get at least 90.0000000% to get an A in the class).
Even if you think you’re not going to be able to fully complete a problem and get the grade that you want, don’t stop. There is always a lesson to be learned from any problem you don’t fully answer correctly.
Again, just do your best and you'll be fine!
We are all in this together!
In the real world, if you are stuck, you don’t spend countless hours trying to impress your boss!
You ask for help from people with relevant experience so that you can move the project along in a timely manner. Ask questions during lecture, recitations and on piazza. Also, check if the question you have in your mind has already been answered. This will save you a lot of time! And obviously come to office hours! The one-on-one meetings might be really helpful if you are looking for something specific.
Once the HW has been graded, did you get enough feedback?
If you lost points, make sure you understand why you lost points. If you cannot, go talk with the TA who graded your submission to ask why.
If you did understand why you lost points, figure out how you could have changed your thought process (and hence your solution) to get a level 0? If you cannot, talk with a TA to get their thoughts on how they would change your solution to make it correct.
Did you ask the right questions in the office hours?
One common mistake students make is that they go from asking questions that are very general (and hence we cannot really give any meaningful answer) directly to asking something super-specific about their solution (and for 1(b), 2(b) and 3 we cannot really tell y'all if your solution is correct or not).
- Asking the same question over and over again in the hope of getting a different answer will only result in both you and the 331 staff getting frustrated.
- Please do ask for help in office hours in how to ask your question better. If you do not understand why the question you asked was not specific enough or was too specific, ask the 331 staff to explain to you why that was the case.
- If you think the answer given to you during an office hours is not helpful, then try and convey to the 331 staff why the answer was not helpful. While this might not change their answer in all cases (e.g. if your Q is "If my solution to Q1 (b) correct?" then our answer always will be a variant of "We cannot tell you that"), in most cases, this would help the 331 staff to perhaps re-state their answer in a way that is more helpful to you.
Some problems (especially part Q2 part b) are designed to be difficult even for a group of 3.
There is no one person in the world who can simply take a look at a new challenging problem and solve it instantaneously. Breaking down the problem into smaller parts that many people could work on is simply a better approach. You can certainly get together with two of your friends and discuss how to approach such problems.
But please be very mindful of academic integrity. Your boss might help you with different strategies that you can use to get yourself unstuck, but they’re not going to do the work for you. Certainly discuss ideas with two of your friends (and please limit them to two; you wouldn’t want other teams in you company to hear about your unfinished product) but the actual writing of algorithm ideas and proof details need to be of your own.