**Ground Rule Index:**

Contacts | Feedback/Questions | Exams and Quizzes |

Prerequisites | Learning Outcomes | Academic Dishonesty |

Textbook | Grading | Class/study Approach |

Communication | Homework/Piazza | Cell Phones |

Course Materials |

- Professor: Dr. Andrew Harrington
**Lakeshore Office**:**104 Loyola Hall (in the Math Dept., 1110 W Loyola Ave.) 773-508-3783**- For office hours see http://anh.cs.luc.edu/officehrs.html
- aharrin AT luc DOT edu

- Discrete Structures 163 (induction, formal logic, Boolean algebra, proof techniques, functions and relations, combinations, permutations)
- Data Structures 271, very important! (ADT's, insertion sort, selection sort, merge sort, quicksort, binary search, linked lists, binary trees, binary search trees, heaps, hash tables, finite graph basics, basic run-time analysis, big Oh notation, considerable experience with recursion)
- Calculus 130 or 161 – Limits make order estimates somewhat easier, and some of our standard bounds on sums are based on integrals, but even if your calculus is foggy or missing, you should be able to just use the collected results we have, based on calculus. Still, the logical, symbolic thinking practiced in calculus (and Comp 163) is very important.

All of the above should give you some mathematical sophistication. That is the hardest part, and many of you may need more. Please see me when you have trouble.

**The Design & Analysis of Algorithms**, Third edition, by Anany Levitin,
Pearson/Addison Wesley, ISBN 9780132316811. Note, the second edition is
mostly the same and may be used instead for almost everything. Second
edition users, see the
mapping between the two editions.

We should cover some of all but chapters 10 and 12, with a few sections dropped or added, depending on the time at the end. Levitin has a distinctive format, that works well some of the time, and not others. I adjust the order in many places. See the list of topics, and the schedule so far, with reading and writing assignments.

Piazza is a great new course-centered interaction site: social media for courses if you will. Make sure you log in and give it your preferred email address. I will generally send announcements through Piazza, so I strongly sugesst you set up Piazza for frequent updates via email. I may occasionally add important notes and override your email preferences, so you get notified immediately.

- The basic public course materials will all be posted directly on the web under http://anh.cs.luc.edu/363.
- Further announcements, comments, and question solutions will appear in Piazza.
- Some private information between professor/TA and individual students will be handled through the University Sakai system. It will mostly be used for grades and class-wide individual submisisons, like the Math pretest and take-home quiz submissions.

Please let me know, in person or via a message to me in Piazza, when you need something from the course that I have not thought to include, or not included in sufficient detail for you, or not presented from a point of view that you can follow. We are in this together. For me to succeed, I need you to succeed.

For course content questions that are not addressed in person, please post them on Piazza, not email.

You should be looking to help others, too: besides being good for the community, it is good for your grade. You are NOT graded down for expressing needs for help: to be clear about where the holes are in our preparation and to be proactive are positive. Lots of people have lots of questions about this course. Lots of topics need to be spiraled through, with more questions and a bit more understanding in each pass. Do not be shy with questions!

Piazza is an experiment for us at Loyola, though it has been used enthusiastically by tens of thousands of students in other universities. Suggestions for optimizing its use in our learning community are highly encouraged. More detailed information on the use of Piazza with this course is below in Homework/Piazza.

Do not forget office hours; Look them up; make a separate appointment if that works better: Sitting down together and discussing an issue in depth, maybe pointing and drawing diagrams, is still very useful! Somtimes students need to loop through a topic many times, gaining a bit each time.

Foundation:

- Be able to use order estimates for run times
- in basic situations with loops and decisions
- in recursion (using the Master Recurence Relation Theorem)

- Use basic probability to calculate averages or expected values

Understand important data structures such as

- Graphs, directed graphs, directed acyclic graphs
- Priority queues, heaps
- B-trees

Understand important existing algorithms, such as:

- Merge sort
- Quicksort
- Bucket sort
- Depth-first search
- Breadth-first Search
- Dijikstra's Algorithm for shortest path
- Kruskal's and Prim's algorithms for minimum spanning trees
- Union-find algorithms

**Understand these algorithms at different levels (the central part):**

**Be able to follow the algorithms in simple concrete situations (play computer to illustrate results)****Calculate run times and resource needs****Recognize new scenarios where known algorithms are directly applicable****Given a somewhat novel situation, create solutions using variations or combinations of algorithms discussed**

Understand how many algorithms fit into a larger class of algorithms with common properties and strategies, for example

- All sorts using key comparisons
- Divide and Conquer algorithms
- Greedy algorithms
- Dynamic programming problems
- Classes of problems P, NP (an introduction)

- 20% Piazza and class contributions and edits to homework and other questions
- 24% Total for two take-home quizzes
- 24% Midterm exam
- 32% Final exam

I will enter your raw (not scaled) scores into the Sakai gradebook for you to confirm. I base your final grade on separate percentages for each part above.

I convert to course letter grades with the following minimum requirements:

A 93 A- 90 B+ 87 B 83 B- 80 C+ 77 C 73 C- 70 D+ 67 D 60.

It is hard to convert desired learning outcome straight into grades, with so many course components, but look at the boldface central outcome for different levels of understanding of algorithms: If you quite consistently succeed at the levels listed up through 2, 3 or 4, then it should roughly correspond to a grade of C, B or A, respectively.

Reading, following examples, and absorbing general concepts is a start,
but applying them by doing problems is essential.
The exercises are designed to give you experience *doing* and engaging with
all the course topics.

I will try to list problems just before or very shortly after the class where the subject is introduced. I may post a bit further than we get to, not knowing exactly how class will progress. Occasionally I may add an extra problem or two later. In that case I'll try to announce my intention in class, or at least in a later notice.

We are trying a new paradigm with Piazza for most all aspects of homework and general questions. Piazza tracks contributions, so I can give homework credit for all answers and edits.

Additions to Piazza come in several forms: general comments, questions, answers, discussion on an issue with a problem, edits to previous entries (this is a wiki), and polls. Entries can be directed privately to instructors (the TA and me) or to everyone. Entries for everyone can have your name shown or withheld from classmates. Polls that I put out can be completely anonymous.

I am adding some extra structure around assigned homework problems, which are only
*part* of the discussion on the site:

- Everyone should work on all the problems in the regular homework.
It is
*much*less helpful for learning to only look at completed solutions that others come up with. - For regular homework,
only one student, or small cooperating group, will be assigned to post a solution in
Piazza
to a given problem
*on*the Due Day (not the day before, not the day after). The solution must be original, not taken from any book or the internet. - Other students will be expected to read all solutions and edit solutions where they can
be clarified, corrected, or replaced with something both correct and simpler, or
*add*an alternate, substantially different solution that illuminates the idea of the problem from a different angle. These edits must also be original. - I am looking for early input on the best way to assign who composes and posts an initial solution, and how to get everyone a chance to respond with edits effectively. We will likely give different assigned students a first pass at edits, before opening it up.

The ways I would like you to handle Piazza entries vary with the situation:

- Before a problem is due
- Questions and comments posted for everyone that would help with a homework problem,
before an answer is posted, need to either be general or conceptual enough
not to give away solution details.
Do look early at the
homework, think, and post such questions, to get early help!
*If you have a question that is directly related to a solution you are thinking of,**it should be a private communication for instructors.* - Homework problem solutions and solution edits
- The problems are intended for your direct thinking and doing. Answers, and
edits to an earlier answer, should be from your
*personal work and thought*, not from somewhere else, not taken from another resource like the internet, not from old solutions to one of these homework problems from before this semester. If you were not the designated original solution poster, and you worked on homework in a study group, and your solution suggests an edit to the current posted version of a solution, be sure to give credit to all. Using other sources is dishonest. - General comments not addressing a particular problem
- These can be helpful in any way. If you found a good web site that addresses a course topic in a way that you like, post the URL with a comment. Of course you can always give your own direct comments!

Here are most suggestions on using the individual types of Piazza contribution:

- General Comments
- These can be anything useful to the general community. Requests for special emphasis in the next class make sense to go out to the whole class, too. After an initial request, "me, too!" additions are very helpful for me to plan how to make class time best support you!
- Questions
- Other than the restrictions around specific assigned problems, use this community for help. We will discover more ways as we go along! Do organize your materials so you know where to look first for resources. Be aware of the recent course reading and topics. Go to the community second.
- Answers
This is a wiki. One latest version appears directly, though the earlier wiki history can be viewed. Be helpful. It is particularly important in your learning to

*read critically*.*If you can improve an answer, edit it!*This will be a big plus in my grading if you show how you have read critically what others have written. (Including mine.)Some guidelines:

- Where an explanation or proof is required, show logic clearly, using full English and mathematical sentences. I will expect as much on quizzes and exams.
- In algorithms use indentation for blocks, as in the text.
- When you provide a counter example, show
*why*it serves as a counter example. - Piazza has a very nice mouse-based equation editor. We will discuss it. Learn to use it. For those who like to write LaTex directly, that is OK, too.

- Discussion on a question
- There is a provision for discussion of issues separate from answers. If the issue is resolved, the issue can be marked closed (but it is a wiki - it could be reopened by someone else).
- Polls
- If I want quick aggregated responses to multiple choice questions, I may post an anonymous poll. Timely responses are appreciated.

I have allowed and encouraged students to work in pairs on graded homework in the past. In the new paradigm, with results posted for all, and only a limited number of problems being your formal initial responsibility, we will need to discuss how to make this work well.

Always be mindful that particular answers are not the main point of the problems posed: The main thing is to develop the ability to understand and creatively combine and use the ideas behind the problems. If the answer falls in your lap from an outside source, you will likely learn very little. Make sure you are thinking about your process: how you are choosing initial approaches and why the next step is being tried. Students can be in denial, and think that following a solution is a substitute for creating a solution.

Remember,
exams and quizzes are *individual* work. You have to end up being capable yourself.
Make sure you are an active contributor to all parts of your work with any
allowed collaborator. Active collaboration for initial learning is great.
That is a reason for the great success of Piazza.

**Use my office hours!** A number of past students have indicated they
considered the course to be really hard before they started taking
advantage of office hours, and then they found the work much more
accessible. Take advantage of office hours, for sustained, one on one help!
Let me know if the posted hours do not work for you.

While some homework may be set up to be done collaboratively, the rest of the grading will be for individual work. Tentative In-class Exam Schedule (updated in the course schedule and assignments):

Midterm: Mar 11Final Exam: Apr 29

I am planning on
two take-home quizzes, tentatively due in class **Feb 25 and Apr 15**.

If I want to change this quiz timing, or add any, I will give at least a week's notice before sending out take-home quizzes. I will generally send take-home quizzes out at least 4 days before they are due at the beginning of a class. I am likely to give a 2-3 hour time limit on quizzes. Tentative due dates are listed in the course schedule and assignments. In particular I am planning to have quizzes before the Midterm and Final as lower-stakes preparation after you have initially absorbed material in homework.

Quizzes are not cumulative (except as the material is naturally
cumulative). Exams *are* cumulative. Exams and quizzes will not include
material that is new in the week immediately before the test.

You may prepare notes to use for this graded work. I will allow at least the following number of sides of 8.5 x 11" paper notes: quizzes: 2, midterm: 3, and final: 4. Other resources are not allowed.

**Exam Grading**: Do not write down things on exams that you can see are
incomplete or incorrect without making some comment acknowledging this
-- it is better to know you are wrong or incomplete than to be wrong and
think you are right.

**Missed Exams** : If you must miss an exam, let me know well in
advance. Then if you have a good reason we can possibly make other
arrangements. I have little sympathy for people who inform me after the
fact for no good reason. I may completely excuse you from an exam if you
were sick or unable to attend for long enough. Most often if you cannot
take an exam at the usual time, I will want you to take it a little
later, BUT I WILL NOT LET ANYONE TAKE A LATE EXAM AFTER THE NEXT CLASS
PERIOD. If you somehow fail to let me know in a timely fashion that you
have an excuse and want to take the exam late, appear at my office hours
before the NEXT class after the exam, and I may be able to give you the
exam.

**IMPORTANT POLICY**: If you have an excuse for not being prepared to
take an exam, but decide to take it anyway, you don't get to change your
mind after you see a poor grade. In certain circumstances I may allow
you to delay an exam due to illness, but I will not let you be
reexamined due to a poor grade.

The penalty for cheating may be anywhere from a 0 on an assignment to a grade of "F" in this course. The appropriate dean will be informed in writing of any cheating incidents.

Cheating consists of, but is not limited to the following for all graded work:

- Using or copying another person's work in any fashion (other than collaborative work with your partner on homework).
- Work includes outlines, algorithms, pseudocode, code, and analyses.
- Allowing your own work to be copied or used by another student.
- Submitting as your own work something that has been written by another person, and people write web pages, so that includes material on the Internet.
- Using any unauthorized reference on an exam or assignment.

Help from any source, particularly from others in Piazza, *is fine*
concerning

- Course prerequisites, necessary math
- The meaning of a problem (not the plan for the solution or the actual solution).
- The restrictions of programming language syntax.

I have unfortunately needed to give out 0's in past semesters, with accompanying referrals to the students' deans.

As a user of the campus network, you should be aware of your rights and responsibilities in

The class involves basic facts, processes, and analysis methods, plus creative combinations of solution ideas.

Please give me feedback on what constitutes the best use of your time
for the limited class hours we have.
(The Introductory Questionnaire
is a first step.) The more you can
read the text to get basic facts and process recipes *before* class, the
more time we can spend in class on things you cannot get easily from a
book: asking and answering questions you raise in reading and homework,
the analysis of problems, and creatively applying basic ideas you are
learning to somewhat novel situations. I have fairly complete
notes that supplement the text. I tend to go over them at
least briefly in class and like to use class time to think together
about how to use the material creatively. I will try to add later to the
notes extra things introduced in class.

The algorithms in the book are in pseudo-code. Runnable versions in convenient languages are good. I will supply some algorithms in Python 3.3 and perhaps some in Java or C#.

Only you know the relative importance of any particular cell phone call,
and whether it is important for you to answer a call immediately rather
than later. I *do want* you to be respectful of my class and disrupt it
as little as is practical. If you get cell phone calls with fair
frequency, be sure to have the ring muted before coming to class. If you
rarely get calls, you might not mute it ahead, and your cell phone may
happen to ring. Get rid of the noise as soon as possible, and do not get
flustered. (I'll probably do that at least once.) I assume you will move
outside the classroom for a conversation. If you get fairly frequent
calls that you are likely to consider important answering, sit in a
place where your exit and re-entrance are as unobtrusive as possible.