Colorado State University, Pueblo
Math 345 — Algorithms and Data Structures — Fall 2018

Here is a shortcut to the course schedule/homework page.

Here is a shortcut to the summary table below of components of the grades for this course.

Class meets: M-F 12:20-1:15pm in PM 221      Office Hours: M-F 11am-12pm in GCB314D, or by appointment

Instructor: Jonathan Poritz     Office: GCB 314D [& rarely PM 248]     E-mail: jonathan@poritz.net
Phone: 549-2044 (office — any time); 357-MATH (personal;please use sparingly)

Texts: Various free, open, on-line resources, including

• Open Data Structures
• Algorithms, Etc.
• Problem Solving with Algorithms and Data Structures using Python
• Python 3.7.1rc1 documentation

Prerequisites: A satisfactory grade (C or higher) in Math 224 (Calculus and Analytic Geometry II) and Math 242 (Introduction to Computation). The point of the first of these prerequisites is to ensure that you have started the process of becoming comfortable with a certain level of sophistication in mathematical reasoning, perhaps including some mathematical abstraction such reading and writing proofs. The idea of the second is that you should have [at least] moderate programming skills in some language.

Postrequisites: This course is required for the minor in computational mathematics.

Course Content/Objective: The Catalog entry for this course is:

Math 345 Algorithms and Data Structures 4(3-2) An introduction to data structures, sorting, searching, recurrence relations and performance measures. Algorithms will be studied analytically and through computer implementation.

Algorithms and data structures are the core of a computer science curriculum. The material in this class is an essential component of very theoretical areas such as complexity theory, scheduling theory, distributed computing, and many others, while also being, in a very real sense, the bread-and-butter of most real-world projects in applied computer science.

Correspondingly, we shall take both a theoretical approach which deals with the limits of algorithms and precise measures of their time and space efficiency, and also a practical approach in which we make trial implementations of all of the algorithms and structures we discuss in order to play with them, to understand them better, and to see their strengths and weaknesses.

Student Learning Outcomes: On successful completion of this course, students should be able to:

1. understand, explain, use, and apply basic ideas of algorithmic thinking for procedural computational tasks;
2. formally verify, and explain that verification, the correctness of algorithms in performing their intended tasks;
3. understand, explain, and compute measures of efficiency of algorithms, when that efficiency is measured and described in different ways;
4. read, write, evaluate the correctness and efficiency of, and translate into more discursive explanations and into running code in some language, pseudocode for various algorithms;
5. understand, explain, use, and apply basic ideas for the design of algorithms, such as divide-and-conquer, recursion, greedy algorithms, brute force, transform-and-conquer, dynamic programming, genetic programming, etc.;
6. understand, explain, and apply a range of sorting and searching algorithms, abstractly weighing their efficiencies and concretely creating and using implementations in appropriate situations;
7. understand, explain, use, and apply a range of data structures, including stacks, queues, trees, graphs, heaps, hash tables, etc., abstractly weighing their efficiencies and concretely creating and using implementations in appropriate situations;
8. read scientific literature on algorithms and data structures and on their own understand, explain, use, and apply the results therein;
9. research algorithms and data structures relevant to a particular problem of interest, develop a strategy to implement a solution, implement that strategy in running code, and describe in both written and oral form the strategy, solution, and examples of applications.

Class organization: Daily procedures:

1. Keep an eye on the course schedule page, at least as frequently as we have class.
2. Read the assigned material we will be discussing before the class in which we will discuss it and again after the first class discussion of that material).
   In fact, one way to read hard texts about technical subjects is to do it three times:
   • First, just to get an idea of the new terms which are used and the over-all shape of the reading — i.e., is it a long proof of a difficult theorem, or a definition and then several carefully worked-out examples, or whatever, and is there an important diagram after the discussion, or is there an informal proof followed by a statement "What we have just seen is: Theorem: ....", or is there pseudocode which is then explained or an explanation culminating in pseudocode (or even proper code in some language).
   • Second, read it through very carefully, following all the details of logic and calculation/code with a pen and paper in your hand or computer turned on in front of you, to check the calculations and code and see that you understand every single step in its full glory and how it works.
   • Third, skim a last time now that you understand the details, to reassess the over-all structure and even to think about connections you can make on your own to other things you know, other examples you make on your own of the definitions or theorems or algorithms under discussion, and how everything would change (if it would!) if some part were changed or omitted.
3. When noted in the course schedule page, every student must e-mail me (at jonathan@poritz.net) thoughts and/or questions that have come up during their reading and thinking about the assigned material, at least an hour before each class, and no earlier than 5pm of the previous business day. We'll call these your T&Qs. They are graded 0 or 1: almost anything which shows serious engagement with the material of the day is worth a 1. Your six lowest such scores will be dropped.
4. There will be regular homework assignments, roughly once a week, based on the topic of discussion for the week. They will have parts which are [running, hopefully] code and others which will be exercises to be worked out mostly without a computer. Please turn in the HW by email to your instructor (jonathan@poritz.net), if at all possible.
5. Some specifics about the homework:
   • Homework should be sent to me by email. Please do not use Windoze or other proprietary file formats (like .docx) -- plain text or PDF is fine. (If you have doubts about this, contact me beforehand.) In fact, it would be great to send your HW solutions, even the ones which have some calculations and special [mathematical] symbols to your instructor by e-mail. The way to include interesting typesetting in an email is to use the notation of the L^AT_EX mathematics typesetting system. Here is a nice introduction to L^AT_EX, while here is a reasonable tutorial — but there are many other free L^AT_EX resources, including the program itself and many thousands of additional packages to make it do additional, wonderful things.
   • Homework is assigned in sets but graded by problem. Each problem will typically be worth 5 points, meaning:
     0. problem entirely missing (or wrong problem done!)
     1. clearly the student knew what the problem was, but essentially no relevant work was done;
     2. the very beginnings of relevant work were done, but nothing was carried through beyond the start;
     3. some work present, but also several errors and/or important missing parts;
     4. most of the correct content is present, but there is at least one key idea or step which is missing, and/or there is a significant flaw in exposition (a variable used without definition, that kind of thing);
     5. all content is present, all notation is defined, all steps are explained and justified.
     Note that is is far better to be clear about a gap in your work than to pretend it doesn't exist: if you say "I think this next step is true but I cannot fully justify it" that will be worth much more than just stating the step as if it were obvious.
   • Homework problems will appear on the homework web page on a regular basis. Please get used to going to that page frequently — at least every other day, and certainly before starting your work on a homework set.
   • Late homework will count, but at a reduced value — generally, the score will be reduced by around two points for each day late.
   • Your lowest five HW problem scores will be dropped.
6. Regular attendance in class is a key to success. But more than merely attending, you are also expected to be engaged with the material in the class. In order for this to be possible, it is necessary to be current with required outside activities such as reading textbook sections, thinking about problems, doing the small writing assignments and larger problem sets. You are expected to spend 1.5-2.5 hours per hour of class on this outside work — this is not an exaggeration (or a joke!), in fact it is closer to a legal requirement.
7. If you absolutely have to miss a class, please inform me in advance and I will video (a part of) the class and post the video on the 'net. You can then watch the class you missed in the comfort of you home and (hopefully) not fall behind. Classes I have videoed will have the icon next to that day's entry on the schedule/homework page to remind you of the available video. (But you must e-mail me for a link to the video, you will not be able to search for it.)

Revision of work on homework and projects: A great learning opportunity is often missed by students who get back a piece of work graded by their instructor and simply shrug their shoulders and move on. In fact, painful though it may be, looking over the mistakes on those returned papers is often the best way to figure out exactly where you tend to make mistakes. If you correct that work, taking the time to make sure you really understand completely what was missing or incorrect, you will often truly master the technique in question, and never again make any similar mistake.

In order to encourage students to go through this learning experience, I will allow students to hand in revised solutions to all homeworks and projects (both midterm and final). There will be an expectation of slightly higher quality of exposition (more clear and complete explanations, all details shown, all theorems or results that you use carefully cited, etc.), but you will be able to earn a percentage of the points you originally lost, so long as you hand in the original, graded work and a new, better version at the very next class meeting. The percentage you can earn back is given in the "revision %" column of the table in the Grades section, below.

Projects/Exams We will have two larger projects, playing the role of midterm exams, due on dates to be determined (and announced at least a week in advance). There will also be a final project with an in-class portion (demonstration/presentation to the class) in place of a final exam.

Grades: In each grading category, the lowest n scores of that type will be dropped, where n is the value in the "# dropped" column. The total remaining points will be multiplied by a normalizing factor so as to make the maximum possible be 100. Then the different categories will be combined, each weighted by the "course %" from the following table, to compute your total course points out of 100. Your letter grade will then be computed in a manner not more strict than the traditional "90-100% is an A, 80-90% a B, etc." method.

Contact outside class: Over the years I have been teaching, I have noticed that the students who come to see me outside class are very often the ones who do well in my classes. Now correlation is not causation, but why not put yourself in the right statistical group and drop in sometime? I am always in my office, GCB 314D [or, rarely, PM 248], during official office hours. If you want to talk to me privately and/or cannot make those times, please mention it to me in class or by e-mail, and we can find another time. Please feel free to contact me for help also by e-mail at jonathan@poritz.net, to which I will try to respond quite quickly (usually within the day, often much more quickly); be aware, however, that it is hard to have very complex, technical discussions by e-mail, so if the issue you raise in an e-mail is too hard for me to answer in that form, it may well be better if we meet before the next class, or even talk on the telephone (in which case, include in your e-mail a number where I can reach you).

Academic Dishonesty: Academic dishonesty is any form of cheating which results in students giving or receiving unauthorized assistance in an academic exercise or receiving credit for work which is not their own. In cases of academic dishonesty, the instructor will inform the chair of the department prior to implementation of punitive action. Academic dishonesty is grounds for disciplinary action by both the instructor and the Dean of Student Services and Enrollment Management. Any student judged to have engaged in academic dishonesty may receive a failing grade for the work in question, a failing grade for the course, or any other lesser penalty which the instructor finds appropriate. To dispute an accusation of academic dishonest, the student should first consult with the instructor. If the dispute remains unresolved, the student may then state his or her case to the department chair (or the dean if the department chair is the instructor of the course).
Academic dishonesty is a behavioral issue, not an issue of academic performance. As such, it is considered an act of misconduct and is also subject to the University disciplinary process as defined in the CSU-Pueblo Student Code of Conduct Policies and Procedures Manual. Whether or not punitive action has been implemented by the faculty, a report of the infraction should be submitted to the Dean of Student Services and Enrollment Management who may initiate additional disciplinary action. A student may appeal a grade through the Academic Appeals Board. The Dean of Student Services and Enrollment Management's decision may be appealed through the process outlined in the Student Code of Conduct Policies and Procedures Manual.

Accommodations: Colorado State University-Pueblo abides by the Americans with Disabilities Act and Section 504 of the Rehabilitation Act of 1973, which stipulate that no student shall be denied the benefits of education "solely by reason of a handicap." If you have a documented disability that may impact your work in this class and for which you may require accommodations, please see the Disability Resource & Support Center as soon as possible to arrange accommodations. In order to receive accommodations, you must be registered with and provide documentation of your disability to the Disability Resource & Support Center, which is located in the Library and Academic Resources Center, Suite 169.

Mandatory Reporting: Colorado State University-Pueblo is committed to maintaining respectful, safe, and nonthreatening educational, working, and living environments. As part of this commitment, and in order to comply with federal law, the University has adopted a Policy on Discrimination, Protected Class Harassment, Sexual Misconduct, Intimate Partner Violence, Stalking, & Retaliation. You can find information regarding this policy, how to report violations of this policy, and resources available to you, on the Office of Institutional Equity's website (www.csupueblo.edu/institutional-equity).
Please familiarize yourself with the reporting requirements of this policy. Because I am a faculty member, I am a "Responsible Employee." That means I have to report to the Director of the Office of Institutional Equity if you tell me that your subjected to, or engaged in, any of the following acts: discrimination, protected class harassment, sexual misconduct, intimate partner violence, stalking, and retaliation.

Al-Kwarizmi

data

Structure(s)