CSC3120 - Algorithm Design and Analysis
Contents
- 1 General Information
- 2 Textbooks and Materials
- 3 Prerequisites
- 4 Catalog Description
- 5 Goals
- 6 Methods of Instruction
- 7 Grading
- 8 Schedule
- 9 Classroom Policies and Expectations
- 10 Attendance
- 11 Getting Help
- 12 Due Dates and Late Work
- 13 Collaboration
- 14 Academic Honesty
- 15 Inclement Weather
- 16 Students with Disabilities
General Information
Spring 2019
Robert Lowe robert.lowe@maryvillecollege.edu
Office: SSC 214
Office Hours
MWF | 2:00-3:00 |
TR | 10:00-11:00 |
Textbooks and Materials
- Introduction to Algorithms. 3rd Edition. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 2009. ISBN 978-0262033848
Prerequisites
- CSC241 - Data Structures
- A modicum of courage
Catalog Description
A study of algorithms and their complexity, including sorting, searching, pattern matching, combinatorics, backtracking, dynamic programming, and approximations and heuristics for NP-complete problems.
Goals
Upon completion, a successful student will:
- Be familiar with standard algorithms.
- Understand algorithm analysis.
- Understand algorithm design.
- Have a greater understanding of proof writing.
- Understand time complexity of algorithms.
- Have a firm foothold in theory, which will help with the transition to theory of computation.
Methods of Instruction
Traditional lecture, discussions, homework, and exams.
Grading
- Homework 25%
- Exam I 25%
- Exam II 25%
- Final Exam 25%
Schedule
Day | Topic | Reading |
---|---|---|
R 1/10 | Introduction and Background | Chapters 1 & 2 |
T 1/15 | Asymptotic Notation | Chapter 3 |
R 1/17 | Standard Notations and Common Functions | |
T 1/22 | Divide and Conquer | Chapter 4 |
R 1/24 | Divide and Conquer | |
T 1/29 | Substitution Method for Solving Recurrences | |
R 1/31 | Tree Method for Solving Recurrences | |
T 2/5 | The Master Method | |
R 2/7 | Proof of the Master Theorem | |
T 2/12 | Sorting Algorithms | Chapters 6, 7, 8 |
R 2/14 | No Class | |
T 2/19 | Exam 1 | |
R 2/21 | Dynamic Programming - Rod Cutting | Chapter 15 |
T 2/26 | Dynamic Programming - Matrix-Chain Multiplication | |
R 2/28 | Dynamic Programming - Longest Common Subsequence | |
T 3/5 | Greedy Algorithms | Chapter 16.1-16.3 |
R 3/7 | Greedy Algorithms | |
T 3/12 | Spring Break | |
R 3/14 | Spring Break | |
T 3/19 | Elementary Graph Algorithms | Chapter 22 |
R 3/21 | Elementary Graph Algorithms | |
T 3/26 | Exam 2 | |
R 3/28 | Minimum Spanning Trees | Chapter 23 |
T 4/2 | Single-Source Shortest Paths | Chapter 24 |
R 4/4 | Single-Source Shortest Paths | |
T 4/9 | NP-Completeness | Chapter 34 |
R 4/11 | NP-Completeness | |
T 4/16 | Approximation Algorithms | Chapter 35 |
R 4/18 | Approximation Algorithms | |
T 4/23 | Review and Wrapup |
Classroom Policies and Expectations
In order to ensure a happy and successful semester, I request that you:
- Silence all cell phones during class. Texting and driving is deadly. Texting and learning is worse. I know when you are texting, and it distracts me. Worse, it will distract students around you. Please be courteous to each other and refrain from surfing the web and texting during class.
- Come to class well rested, well fed, and ready to work and learn.
- Be courteous and respectful of your classmates. Try to make everyone sitting around you happy to see you. A community of happy learners is far more successful than a collection of embittered individuals.
- Always bring required materials to class.
- Ask lots of questions! I understand that you like the sound of my voice. I’ve always enjoyed it, but you will get much more out of this course if you ask questions. If you are confused about a topic, I guarantee you that at least one other person in the room is as well, so don’t be shy about speaking up. Learning is best done as a dialog, your professors love answering questions!
Of course, these guidelines are not quite specific enough for some questions. More detailed and legalistic policies follow.
Attendance
You should strive for perfect attendance! Many of the concepts we will cover can be quite confusing without proper context and guidance. If you are absent, you will miss out on this, and so you will easily fall behind. Of course, sometimes life happens and you may need to miss class. My policy is that you must attend at least 80% of class meetings in order to pass the class. If you miss more than 20% of the class meetings, unless you have been granted an exception, you will receive an automatic “F” for the course. Also, note the days of the exams in the schedule. If these dates change, I will notify you at least week in advance; however, they are not likely to change. If you must miss an exam period, you will need to make arrangements to take the exam before the scheduled day. Failure to take an exam on or before an exam period will result in a grade of zero for that exam.
Getting Help
I will do my best to make sure help is readily available to you. You can come see me during my scheduled office hours. If you see me in my office and it is not an office hour (a very common occurrence) feel free to come in and ask any question you like. The same goes for when you see me around campus. Feel free to approach me and chat with me at any time! Also, I am available by email and will typically respond within one business day. I typically do not check my email after 6:00PM or on weekends, however, so there may be a delay during those times.
Due Dates and Late Work
Due dates will be provided with each assignment. Except in very rare emergencies, no individual extensions will be granted. Late work will receive a grade of zero. This means that “getting help” is all the more important! I never grant individual extensions to assignments, but if lots of people express confusion to me, I am much more likely to extend the assignment’s due date for the entire class. If no one asks me questions about an assignment, I will assume everything is going fine and will act accordingly.
Collaboration
I encourage you to form study groups and consult with each other. However, each individual in that group must do their own work. I realize that this can be a tricky dynamic to work with. If you ever think you may be getting too much help from another student, then you probably are.
Acceptable collaboration would include:
- Asking for help on the approach to a problem.
- Asking for help in locating references in books and/or on the internet.
- Reading texts together or forming study groups for exams.
Unacceptable levels of collaboration include:
- Showing completed solutions to each other.
- Asking another student what a specific answer is.
- Allowing another student to copy an assignment.
Any wholesale copying will result in a grade of zero on the assignment for all students involved. This policy is, of course, different for group projects. Unless otherwise instructed, I expect you to submit only your own work for grading.
Academic Honesty
Academic honesty is a very serious issue. All work that you present as your own must be your own work. Copying someone else’s work in any way shape or form is unacceptable unless proper attribution is given. I am,
of course, referring to plagiarism. Plagiarism is not always a blatant act. In fact, most of the time it takes very subtle forms such as:
- Presenting an idea that you have read without citing a source.
- Copying code from a website.
- Copying steps for a mathematical problem from a website.
- Using pictures and/or clipart without attribution.
As a rule, plagiarism is unspeakably ugly to academic professionals. Copying without attribution is, in short, a great way to get on your professor’s bad side. Also, the Maryville College policy is that after 3 instances of plagiarism, you are referred to an academic honesty board for disciplinary action. So please, do not commit this heinous deed!
If I catch you in an act of plagiarism, the first offence will result in a grade of zero and a report will be written and filed with academic affairs (not to mention a rather unpleasant conversation for both of us). The second offence will result in a failing grade for the course along with a second report.
Inclement Weather
Ah, East Tennessee. Normally pleasant and temperate, but at other times we are in the midst of a raging whirlpool of blizzards and tornadoes! Should Maryville College close, an announcement will be made on the website, in the local media, and via text message (if you’ve signed up for the alerts). So long as the college is open, we will meet and have class. If the college is closed, I will revise our schedule upon our return.
Students with Disabilities
Students with a disability requiring accommodations or any student who believes that they will require accommodations should contact Kim Ochsenbein in the Academic Support Center located in the lower level of Thaw Hall (865) 981-8124. Students are encouraged to make contact before or during the first week of classes.