CSC373

Q: I want to write real Java (C++, C#, python, etc.) code on some questions. Do you allow that?

A: I do not allow real code. Writing pseudocode is a skill and it needs to be practiced and developed. It is part of this course. Later in your career you will come to appreciate the ability to write good pseudocode. If you need to present an algorithm to diverse audience, and you are interested in carrying across the key ideas of the algorithm rather than its implementational challenges, then pseudocode is essentially your best option. By using pseudocode, you don't need to assume particular background of your audience and you abstract away quirkiness of a particular language.

Q: Do we have to type our solutions to assignments or is it also ok to scan hand-written ones?

A: It's okay to scan hand-written notes; however, I encourage you to type up your solutions. You are responsible for making your writeup clearly readable. If I can't read your solution due to poor handwriting, the solution gets a grade of 0.

Q: Would it be possible to provide a more structured reading schedule for the semester? I find it helpful to be able to see what readings are required for each week and to do the readings ahead of lectures.

A: I have updated the tentative course schedule on the "Course Contents" website to reflect suggested readings based on CLRS, DPV, and KT books. The lectures are structured around algorithmic paradigms. For a particular algorithmic paradigm I choose problems and algorithms based on how famous a problem is and how likely the students are to encounter the same or a similar problem in their professional or academic careers in the future. Unfortunately, there is not a single source that covers all the algorithms that fit these criteria. If you read all the recommended readings you will cover 95% of the material covered during the lectures and even much more. This would definitely prepare you for the lectures, but you might find that it is a lot of reading, but not too much - the same material is often repeated in CLRS/DPV/KT with different presentation. I do not commit to a more fine-grained reading schedule ahead of time, because I often decide on exact algorithms to cover on the evening before the lecture and it is adaptive - I adapt the material to past lectures.

Q: What exercises do you suggest for extra practice?

A: After a lecture I post a short description of the lecture together with relevant materials on the "Course Contents" webpage. Exercises following the relevant chapters are suggested for extra practice.

Q: We were given loop invariants that we informally summarized as correct. I'm wondering if we would ever have to formally prove this, and if we could have an example of a proof posted on the course website for reference.

A: Generally speaking, it is hard to come up with a correct and useful loop invariant, but once you have it, it should be relatively easy to prove the loop invariant. It is nothing more than an exercise in induction and amounts to tracing steps of the algorithm and observing that loop invariant is maintained. To prove it formally and correctly you should treat it as an exercise in induction: you should state the base case and analyze the inductive step. These are sometimes referred to as initialization and maintenance in the context of algorithm analysis. You should be comfortable with filling in such details if needed - it is a prerequisite for this course. Such formalizm is seldom warranted in this course, but I reserve the right to ask you to state and formally prove a loop invariant using mathematical induction. For an example of such a proof see CLRS section 2.1 on insertion sort.

Q: Will material be covered in tutorial that will not be covered during the lecture time? If so, would it be possible to make alternate arrangements to at least have a summary of the material (or to know the textbook sections in which it is covered)?

A: The attendnace is not taken and does not directly affect the grade. Tutorials will consist of more examples of types of problems (and their solutions) covered in lectures. You are responsible for knowing the tutorial material, so the tutorial material is a fair game for assignments and tests.

I will post couple-of-senteces descriptions of tutorials similar to those of lectures (see the news section from Jan 6 from the course website).

Another important point: term tests will be held during tutorial time slots. Make sure you are available.